[問題] krsukal 跟 prim's algorithm

[johnny94 (32767)]

最近從線上課程複習 minimum spanning tree 時
不免俗地學到了這兩個 prim 跟 kruskal 這兩個著名的演算法

然後有課程有一題的題目是問 "maximum" spanning tree
其中一個方法是把兩個算法反過來用，就是我們不從權重最小的邊開始取
而是從權重最大的邊開始取，但這樣的方法不保證能做出最大生成樹
題目：http://imgur.com/CB3ctOl

但是如果是如推文的方法，把所有邊的權重都乘上-1，然後一樣
求最小生成樹，就可以得到最大生成樹了
題目：http://imgur.com/6NkoYEk

想請問一下有沒有可以參考的證明，或是有高手願意提示一下為什麼會
這樣呢？

謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.46.159.162
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1471882079.A.924.html
推 johnathan717: 不管什麼演算法，每條邊權重乘上-1求最小生成樹，就
→ johnathan717: 會是最大生成樹。如果擔心負權重會有問題，可以同加
→ johnathan717: 一夠大的正數，反正生成樹的邊數一定是點數減一
→ johnny94: 原來如此，所以是利用求最小生成樹的方法，反求
→ johnny94: 最大生成樹
→ johnny94: 那我想問一下為什麼不能反過來做(查到的資料)
→ johnny94: 例如 kruskal 直接把邊從大排到小，然後每次選最大權重
→ johnny94: 的邊。這樣做的話生出來的不一定會是最大生成樹
→ johnny94: 為什麼會這樣呢？實在是想不透...
→ suhorng: 哪個資料啊? 然後內文說 Prim 不行推文卻說 Kruskal @@?
→ johnny94: 我修正一下好了，不好意思我內文有講錯的
※ 編輯: johnny94 (114.46.159.162), 08/23/2016 02:05:21
推 suhorng: 有問題的是 "有向" 不是最小變最大
推 johnathan717: 有向圖中maximum acyclic graph不一定是樹
→ johnathan717: 我以為你在說無向圖，所以才提出乘上-1
→ johnny94: 原來如此，看來我從根本上就搞錯了，謝謝樓上幾位的說明
→ johnny94: ！