作者johnny94 (32767)
看板Prob_Solve
標題[問題] krsukal 跟 prim's algorithm
時間Tue Aug 23 00:07:56 2016
最近從線上課程複習 minimum spanning tree 時
不免俗地學到了這兩個 prim 跟 kruskal 這兩個著名的演算法
然後有課程有一題的題目是問 "maximum" spanning tree
其中一個方法是把兩個算法反過來用，就是我們不從權重最小的邊開始取
而是從權重最大的邊開始取，但這樣的方法不保證能做出最大生成樹
題目：
http://imgur.com/CB3ctOl
但是如果是如推文的方法，把所有邊的權重都乘上-1，然後一樣
求最小生成樹，就可以得到最大生成樹了
題目：
http://imgur.com/6NkoYEk
想請問一下有沒有可以參考的證明，或是有高手願意提示一下為什麼會
這樣呢？
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.46.159.162
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1471882079.A.924.html
1F：推 johnathan717: 不管什麼演算法，每條邊權重乘上-1求最小生成樹，就 08/23 01:29
2F：→ johnathan717: 會是最大生成樹。如果擔心負權重會有問題，可以同加 08/23 01:29
3F：→ johnathan717: 一夠大的正數，反正生成樹的邊數一定是點數減一 08/23 01:29
4F：→ johnny94: 原來如此，所以是利用求最小生成樹的方法，反求 08/23 01:45
5F：→ johnny94: 最大生成樹 08/23 01:45
6F：→ johnny94: 那我想問一下為什麼不能反過來做(查到的資料) 08/23 01:46
7F：→ johnny94: 例如 kruskal 直接把邊從大排到小，然後每次選最大權重 08/23 01:46
8F：→ johnny94: 的邊。這樣做的話生出來的不一定會是最大生成樹 08/23 01:47
9F：→ johnny94: 為什麼會這樣呢？實在是想不透... 08/23 01:48
10F：→ suhorng: 哪個資料啊? 然後內文說 Prim 不行推文卻說 Kruskal @@? 08/23 01:49
11F：→ johnny94: 我修正一下好了，不好意思我內文有講錯的 08/23 01:59
※ 編輯: johnny94 (114.46.159.162), 08/23/2016 02:05:21
12F：推 suhorng: 有問題的是 "有向" 不是最小變最大 08/23 02:20
13F：推 johnathan717: 有向圖中maximum acyclic graph不一定是樹 08/23 17:35
14F：→ johnathan717: 我以為你在說無向圖，所以才提出乘上-1 08/23 17:36
15F：→ johnny94: 原來如此，看來我從根本上就搞錯了，謝謝樓上幾位的說明 08/23 18:34
16F：→ johnny94: ！ 08/23 18:34