推 suhorng :Kruskal弄出來的會是一棵G的生成樹 既然是生成樹那加 07/23 20:33
→ suhorng :上任一條邊就會形成環了 07/23 20:33
→ mqazz1 :可以再請問為什麼第二頁最後兩行 會出現矛盾嗎? 07/23 20:53
推 suhorng :既然把e_k加入T*形成一個環,且環上又有比e_k大的邊e* 07/23 21:20
→ suhorng :(由之前的假設,倒數第四行),那麼,把e*拔掉之後,你會 07/23 21:21
→ suhorng :得到另一個生成樹,且此生成樹的 cost 是 cost(T*) + 07/23 21:21
→ suhorng :cost(e_k) - cost(e*) < cost(T*), 這與 T* 是一個最 07/23 21:22
→ suhorng :小生成樹的假設矛盾. 07/23 21:22