Minimum Spanning Tree

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

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

--
And that's exciting! :)