[理工] [資結] min spanning tree

看板Grad-ProbAsk作者 (賴打葛葛)時間14年前 (2010/03/18 17:20), 編輯推噓7(7推 0噓 7→)
留言14則, 9人參與, 最新討論串1/1
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
→
03/18 17:24, , 1F
some 再all 裏面吧 所以for all 就是 for some阿
03/18 17:24, 1F
推
03/18 17:25, , 2F
kruskal for all
03/18 17:25, 2F
推
03/18 17:26, , 3F
for all對 for some 為什麼不對
03/18 17:26, 3F
推
03/18 17:26, , 4F
T
03/18 17:26, 4F
→
03/18 17:27, , 5F
|T| < n-1 沒有mst 怎麼會是for all
03/18 17:27, 5F
→
03/18 17:29, , 6F
kruskal去選 最小邊一定會有 問題是成不成MST要視清況
03/18 17:29, 6F
→
03/18 17:33, , 7F
大概瞭解了
03/18 17:33, 7F
推
03/18 17:45, , 8F
T 去掉CYCLE中任一邊仍是MST
03/18 17:45, 8F
推
03/18 18:17, , 9F
假設MST存在 如果e不屬於MST 就把e加入 然後把cycle中
03/18 18:17, 9F
→
03/18 18:18, , 10F
最大的邊刪除 就可以得到另外的MST 此MST比原本的還好
03/18 18:18, 10F
→
03/18 18:18, , 11F
故不可能.. e一定屬於MST中 不過前提就是要有MST..
03/18 18:18, 11F
→
03/18 18:19, , 12F
如果G的邊數小於頂點數 那自然就沒有spanning tree了..
03/18 18:19, 12F
推
03/18 18:36, , 13F
如果是第二小的邊呢? 怎麼說明會比較完備...
03/18 18:36, 13F
推
03/18 18:46, , 14F
利用kruskal去選阿，第二小的邊加入一定不會造成迴圈阿
03/18 18:46, 14F
‣ 更多 lightergogo 的文章
文章代碼(AID): #1BeV1YvT (Grad-ProbAsk)