作者kraistlin (葱)
看板NTUGIEE_EDA
标题[研究] bottleneck spanning tree
时间Thu Aug 20 00:27:03 2009
定义:
(for undirected graph)
*bottleneck spanning tree (BST):
指的是拥有 最小的 最大cost edge之spanning tree
*minimum spanning tree (MST):
指的是cost总和最小的spanning tree
性质:
" T 为 MST " => " T 为 BST "
证明:
假设 T 是为 spanning tree 却不是 BST
令 T 中最大 cost edge 为 e
可看成 e 在 T 中连结 两颗 sub-tree, T1 与 T2
则 T1 与 T2 间必存在 e' (e'的cost小於e) 可以连接 T1 与 T2 行成 T'
很明显可以看出 T' 的总 cost 比 T 小 (因为 e' 换成 e)
既然 T 之外还能找到比它小总cost的 spanning tree
那 T 肯定 不是 MST
矛盾!
故得证 " T 为 MST " => " T 为 BST "
[reference]
http://www.fongboy.com/classes/cs180/hw8-2.pdf
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.166.151.43
※ 编辑: kraistlin 来自: 218.166.151.43 (08/20 00:40)
1F：推 reiyo:我昨天有想到过这样证 但总觉得还是有少了global view的错觉 08/20 12:27
2F：→ kraistlin:就是很不直观 08/20 13:20