作者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/cn.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