[研究] bottleneck spanning tree

[kraistlin (蔥)]

定義:
(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)
推 reiyo:我昨天有想到過這樣証 但總覺得還是有少了global view的錯覺
→ kraistlin:就是很不直觀