最小生成树正确性证明

_nosay

参考的《算法导论》，自己再总结一遍，巩固一下理解：

原始图信息：


一种最小生成树（红色部分）：

同一个图可能有多个最小生成树，比如cd=ef，则用ef替换cd就出现另一个最小生成树。

上述最小生成树中的一部分：

我们已经确定该图中的红色路径，为某一个最小生成树的一部分，现将已经经过的点和未经过的点，用一条黑线隔开，则ah、bd、cd、df、ef跨越了这条线，并假设cd是这5条路径中最短的一条。

到此为止，铺垫完毕，现要证明“下一步必须走跨越黑线的最短路径（cd）”。
证明：
1. 先证明“以下情况下走cd也可以生成最小生成树T’ ”：
   假设，图2画的最小生成树T中不包含cd。
   那么，想从c走到d，一定是“绕着”走的，比如cf→ef→ed，但无论如何都得穿过黑线，所以必须包含剩余4条路径中的一条，假设为ef。
   另外，最小生成树中，任意2点之间只可能有1条路径，否则就成环了，对于环中相邻的2点来说，直接相连的路径就可以省去
   ① T连接hgfci和abde只需要ef，现在T’改从cd走，仍然可以将内外两部分全部连通，所以T’仍然是生成树；
          
   ② 由于T为最小生成树，所以它的总权重小于等于任意其它生成树：w(T)≦w(T’)
        由于T’用cd替换了ef，cd为跨越黑线的最短路径，即cd≦ef，所以w(T’)≦w(T)
        所以w(T’)=w(T)，即T’ “也”最小。
   证毕。
2. 证明“必须”：
   如果不走跨越黑线的最短路径，就不能保证“w(T’)≦w(T)”，即证明过程1就无法证明T’ “也”最小。
证毕。

alwaysR9

加油

_nosay

alwaysR9 发表于 2016-01-29 23:43
加油

哇~ 谢谢鼓励 。

windoze

这个版是C/C++，下次如果你光贴算法不贴C/C++代码的话我就删帖了。

_nosay

windoze 发表于 2016-01-30 01:10
这个版是C/C++，下次如果你光贴算法不贴C/C++代码的话我就删帖了。

版主不喜欢无码是吧，那下次这种贴，我写在灌水区吧，那里对内容限制会少点吧。

windoze

回复 5# _nosay

nonono，我的意思是说你要把最小生成树的程序代码一块贴出来。

_nosay

windoze 发表于 2016-01-30 11:40
回复 5# _nosay

nonono，我的意思是说你要把最小生成树的程序代码一块贴出来。

prim，kruskal，网上已经有很多写的很漂亮的代码了，但是关于证明的文章比较少，而且不是很严格，所以我就只总结了证明过程 。

windoze

回复 7# _nosay

漂亮不漂亮没关系，关键是要自己写一遍。
编程就是这样，不动手看再多paper也没用。

_nosay

windoze 发表于 2016-01-30 18:44
回复 7# _nosay

漂亮不漂亮没关系，关键是要自己写一遍。

是的，版主教育的是 。

action08

版主神逻辑哦

老祖宗早就总结了，唯有读书才能使人进步
在不少公司生态，代码控是活得最苦逼的，不要写也罢