2007/03/19

Minimum Spanning Tree

先前在離散數學弄得霧煞煞的 Kruskal 正確性證明,到隨機客手中只用一個簡單命題「每一點權重最小的鄰邊一定在 MST 之中」(*) 就解決了,而且連帶贈送 Borůvka 和 Prim 的正確性證明,全都是同一個核心!

(*) 在不失一般性的假設「所有邊的權重皆相異」之下,MST 唯一,故此命題用的是 "the" MST 而非 "some" MST。

--
And that's exciting! :)

Labels:

<< 回到主頁