作者woody3724 (woody)
站內Prob_Solve
標題[問題] 何謂 bottleneck spanning tree ?
時間Mon Dec 19 19:48:21 2011
何謂 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
1F：推 suhorng:無向、帶權圖G可能有很多個生成樹 每棵生成樹都會有權重最 12/19 19:59
2F：→ suhorng:大的邊 (可能一條, 可能很多條) 12/19 19:59
3F：→ suhorng:在這很多棵生成樹中 {權重最大的邊}最小的那棵 稱為MBST 12/19 19:59
4F：→ suhorng:對某棵生成樹而言, 權重最大的那條邊叫做bottleneck edge 12/19 20:00
5F：→ suhorng:維基之所以說MBST是"沒有bottleneck edge比它更小的生成樹 12/19 20:01
6F：→ suhorng:的spanning tree稱為MBST",是因為可能有很多棵MBST 12/19 20:01
7F：→ woody3724:意思是 瓶頸樹的所有權加起來是最小 12/19 22:52
8F：→ woody3724:但包含整個圖的最大邊！？ 12/19 22:52
9F：→ woody3724:這樣解釋有錯嗎 12/19 22:52
10F：推 springman:若 T 是 MBST 的話，其他 spanning tree 的最大邊都不會 12/20 04:35
11F：→ springman:比 T 的最大邊小。 12/20 04:35
12F：推 suhorng:**完全**沒有說權和加起來要最小 只要求最大邊最小 12/20 09:18
13F：→ suhorng:對於某一棵生成樹T 我們稱T中權最大的邊bottleneck edge 12/20 09:21
14F：→ suhorng:若對某棵T而言 不存在T' 使得T'的bottleneck edge的權 < 12/20 09:21
15F：→ suhorng:T的bottleneck edge的權 那就說T是一棵MBST 12/20 09:22
16F：→ suhorng:別把他跟MST弄混了~ 雖然一樣可以用修改的Kruskal's求MBST 12/20 09:22