作者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