MST 基本定理

Theorem 對於任一點 v，其權重最輕的鄰邊必在 MST 上。

Proof 若不然，v 至少有兩個鄰邊，令 v 權重最輕的鄰邊為 e* = (v, x)，並令 MST 為 T*。T* 中唯一存在一條路徑 p: x ~> v，e* 不包含於 p。令 p 的最後一個邊為 e' = (y, v)。Claim：把 e' 從 T* 中去除，並加入 e* 形成一個新的 graph T，則 T 仍為 connected。欲證明此事，只需證明 y、v 仍然連通即可。此事顯然為真，因為 p 內含 x ~> y 的路徑，而 e* = (v, x) 已被加入 T，所以 v -> x ~> y 是連通的。T* 的邊數為 n - 1，T 的邊數亦為 n - 1，又 T 為 connected，依樹的刻劃定理，T 為 (spanning) tree。但 w(e') > w(e*) ==> w(T*) > w(T)，這與 T* 為 MST 的事實矛盾。

--
應該足夠嚴謹吧 XD。