2007/04/17

MST 基本性質

以下三個性質全部要有不失一般性的假設「所有邊的權重皆相異」。剛剛和同學看隨機客投影片,在 cycle property 卡了好久(我記得隨機客也是說他很容易在 cycle property 卡住 XD),趕快記下來比較安全 XD。


Figure 1: Illustration of the Cut Property



Figure 2: Illustration of the Proof of the Uniqueness Property


示意圖取自隨機客的精美投影片 XD。嚴謹說來,必須要有 uniqueness property,才能用 MST 基本定理證明 Boruvka、Kruskal、Prim 三個演算法的正確性,所以上述三個性質不能忽略 XD。

--
其實 cut property 的證明可以寫 "Proof. Trivial." XD。

Labels:

<< 回到主頁