[理工] [DS] min spanning tree

[marvintim77 (小銘)]

證明 在每個edge的weight都不同的情況下min spanning tree為唯一

http://tinyurl.com/4kcm2gg

上面網址是wiki的證法

我從第5步 As B is a MST, {e1}聯集 B  must contain a cycle C.

這句我就不懂了   為什麼一定會形成cycle?

有大大可以指點一下嗎?

謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.49.83
※ 編輯: marvintim77     來自: 114.39.49.83         (03/25 01:54)
※ 編輯: marvintim77     來自: 114.39.49.83         (03/25 01:54)
→ marvintim77:下去尿個尿突然被隱形的雷打到，自己懂了
推 cooper6334:假設e1是從va連到vb,因為MST連通,所以必有一path從a到b
→ marvintim77:因為e1是MSTA其中一個edge，且e1不存在於B
→ cooper6334:加入e1後就一定有va->vb(原MST path)-e1->va 的cycle
→ marvintim77:2F大大說的就是了  謝謝2F大大了XD