最小生成树证明有关问题！
最小生成树证明问题！！！
如何证明贪心法求得的生成树为最小生成树?
------解决方案--------------------
关注一下最优子结构
------解决方案--------------------
以kruskal算法为例，kruskal算法的贪心规则是寻找当前连接图中两个子树的最
小边，直到第n-1条。证明方法来自wikipedia，
http://en.wikipedia.org/wiki/Kruskal's_algorithm
感觉不是很好懂，不过应该是正确的。应该注意到如下两点：第一，最小生成树是存在的，但由于可能存在等权重的边，所以它不唯一；第二，这里证明的是kruskal算法返回的结果是最小生成树。
1.首先证明kruskal算法能产生树。设P是完全连接的带权图。Y是由kruskal算法
产生的P的一个子图。则Y中不包含环路，因为这样的话就说明最后一条加入的边
在一个子树内部，而不是连接两个子树。Y也不可能是不连通的，因为搜索算法会
把遇到的第一个连接Y的个不同子树的边加入到Y中。所以，Y是生成树。
2.证明生成树的边权重最小性。采用归纳的方法证明如下理论W:如果F是kruskal算法在任意阶段选出的边集,则必有某个最小生成树必然包含F。
1）显然，W在开始时成立，因为F是空的。
2）现在假设W对于非最终结果的边集F成立，并且设T是包含F的某个最小生成树。如果算法选择的下一条边e属于T，则W对于F+e成立。否则，T+e将包含一个环路C,并且C包含一个不属于F的边f。T-f+e将是一个树，它具有与T一样的权重。（因为如果f<e,那么，算法就会选择f而不是e）。所以T-f+e是一个包含F+e的最小生成树，W依然成立。
3）最终，依照归纳准则，W在F成为生成树的时候成立，所以F是最小生成树。
ps:这里证明的思路是，如果边集F在长大的过程中始终属于某一个最小生成树，那么，F最终成长为最小生成树。
如何证明贪心法求得的生成树为最小生成树?
------解决方案--------------------
关注一下最优子结构
------解决方案--------------------
以kruskal算法为例，kruskal算法的贪心规则是寻找当前连接图中两个子树的最
小边，直到第n-1条。证明方法来自wikipedia，
http://en.wikipedia.org/wiki/Kruskal's_algorithm
感觉不是很好懂，不过应该是正确的。应该注意到如下两点：第一，最小生成树是存在的，但由于可能存在等权重的边，所以它不唯一；第二，这里证明的是kruskal算法返回的结果是最小生成树。
1.首先证明kruskal算法能产生树。设P是完全连接的带权图。Y是由kruskal算法
产生的P的一个子图。则Y中不包含环路，因为这样的话就说明最后一条加入的边
在一个子树内部，而不是连接两个子树。Y也不可能是不连通的，因为搜索算法会
把遇到的第一个连接Y的个不同子树的边加入到Y中。所以，Y是生成树。
2.证明生成树的边权重最小性。采用归纳的方法证明如下理论W:如果F是kruskal算法在任意阶段选出的边集,则必有某个最小生成树必然包含F。
1）显然，W在开始时成立，因为F是空的。
2）现在假设W对于非最终结果的边集F成立，并且设T是包含F的某个最小生成树。如果算法选择的下一条边e属于T，则W对于F+e成立。否则，T+e将包含一个环路C,并且C包含一个不属于F的边f。T-f+e将是一个树，它具有与T一样的权重。（因为如果f<e,那么，算法就会选择f而不是e）。所以T-f+e是一个包含F+e的最小生成树，W依然成立。
3）最终，依照归纳准则，W在F成为生成树的时候成立，所以F是最小生成树。
ps:这里证明的思路是，如果边集F在长大的过程中始终属于某一个最小生成树，那么，F最终成长为最小生成树。