[理工] [資結] min spanning tree

[lightergogo (賴打葛葛)]

If graph G has a cycle with a unique lightest edge e, then e must

be part of some MST.

有人說是T

我覺得是F

原因是出在"some"

應該是for all吧?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.121.238.141
→ chris750630:some 再all 裏面吧 所以for all 就是 for some阿
推 sephen:kruskal for all
推 ie925155:for all對 for some 為什麼不對
推 assassin88:T
→ sephen:|T| < n-1 沒有mst 怎麼會是for all
→ sephen:kruskal去選 最小邊一定會有 問題是成不成MST要視清況
→ lightergogo:大概瞭解了
推 holik0123:T 去掉CYCLE中任一邊仍是MST
推 FRAXIS:假設MST存在 如果e不屬於MST 就把e加入 然後把cycle中
→ FRAXIS:最大的邊刪除  就可以得到另外的MST 此MST比原本的還好
→ FRAXIS:故不可能.. e一定屬於MST中 不過前提就是要有MST..
→ FRAXIS:如果G的邊數小於頂點數 那自然就沒有spanning tree了..
推 fef92:如果是第二小的邊呢? 怎麼說明會比較完備...
推 cansister:利用kruskal去選阿，第二小的邊加入一定不會造成迴圈阿