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。