為什麼這篇bottleneck意思鄉民發文收入到精華區：因為在bottleneck意思這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者woody3724 (woody)站內Prob_Solve標題[問題] 何謂 bottlenec...
何謂 Bottleneck Spanning Tree ?
課本(Introduction to Algorithms , 3ed)給的定義看不懂
上頭說：A bottleneck spanning tree T of an undirected graph G is a
spanning tree of G whose largest edge weight is minimum over
all spanning trees of G. We say that the value of the
bottleneck spanning tree is the weight of the maximum-weight
edge in T.
上WIKI查也看不懂
WIKI說：A bottleneck edge is the highest weighted edge in a spanning tree.
A spanning tree is a minimum bottleneck spanning tree (or MBST)
if the graph does not contain a spanning tree with a smaller
bottleneck edge weight.
找了一些中文網頁 也還是看不懂
請高手解釋 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.5.236
推 suhorng:無向、帶權圖G可能有很多個生成樹 每棵生成樹都會有權重最 12/19 19:59
→ suhorng:大的邊 (可能一條, 可能很多條) 12/19 19:59
→ suhorng:在這很多棵生成樹中 {權重最大的邊}最小的那棵 稱為MBST 12/19 19:59
→ suhorng:對某棵生成樹而言, 權重最大的那條邊叫做bottleneck edge 12/19 20:00
→ suhorng:維基之所以說MBST是"沒有bottleneck edge比它更小的生成樹 12/19 20:01
→ suhorng:的spanning tree稱為MBST",是因為可能有很多棵MBST 12/19 20:01
→ woody3724:意思是 瓶頸樹的所有權加起來是最小 12/19 22:52
→ woody3724:但包含整個圖的最大邊！？ 12/19 22:52
→ woody3724:這樣解釋有錯嗎 12/19 22:52
推 springman:若 T 是 MBST 的話，其他 spanning tree 的最大邊都不會 12/20 04:35
→ springman:比 T 的最大邊小。 12/20 04:35
推 suhorng:**完全**沒有說權和加起來要最小 只要求最大邊最小 12/20 09:18
→ suhorng:對於某一棵生成樹T 我們稱T中權最大的邊bottleneck edge 12/20 09:21
→ suhorng:若對某棵T而言 不存在T' 使得T'的bottleneck edge的權 < 12/20 09:21
→ suhorng:T的bottleneck edge的權 那就說T是一棵MBST 12/20 09:22
→ suhorng:別把他跟MST弄混了~ 雖然一樣可以用修改的Kruskal's求MBST 12/20 09:22