2007/03/20

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。

Labels:

<< 回到主頁