最小生成树

没有自环和多重边的图叫简单图

直觉觉得可能是唯一的,不过可以考虑用反证法证明一下,
分析中...

顶起

首先最小生成树是在n个节点构成的网中,选取n-1条边,可以建立一个连通图,现在假设,我们用普里姆算法或者是克鲁斯卡尔算法,计算出一棵最小生成树(记住你已经计算出了一个最小生成树了),现在你又有幸的到了一个最小生成树,和上一次计算出的权值和是一样的,但是要知道这棵最小生成树也只有n-1条边啊!也就是说第一次算出的最小生成树和第二次算出的生成树只有一条边不一样,那会发生什么事情呢?

当恰好有两条权值相同的边时，你要选择那条，这样就会出现不同的生成树。

小弟来解吧，
吹一点，很简单的。
简单连通图。意思就是
如
A----------B
|          |
|          |
C----------D
从任一点出好，能够通过深度优先和广度优先遍历所有结点。例子，从A点出发，深度的，就是ABDC所有结点都访问过了，就是简单连通图了。
所以最小生成树也就是唯一的了。

我有了个想法：
假定存在两棵不同的最小生成树A，B
对于两棵树A和B中任意相同点对（i,j）
一定是下面的情况：
1.A中有边相连，B中也有边相连，此时这两点之间的边一定是同一条（因为没有多重边）
2.A中无边相连，B中也无边相连
3.A中有边相连，B中无边相连
4.A中无边相连，B中有边相连

因为两棵树不同，所以3或者4的情况必然至少出现一次
（如果只是1，和2，那么两棵树就完全一样了）
假设存在点对（v,w）属于情况3，（4类似）
那么我们将A中点对（v,w）间的边e加到B中，
B中会形成唯一的一条包含边e的回路。
可以肯定e一定不是这个回路中权值最大的边，
（在各边权值都不等的情况下，回路中权值最大的边不会出现在任意一个最小生成树中）   ！！！ 有定理支持


显然A这棵最小生成树包含e,所以如果e的权值最大就会出现矛盾。
那么我们从B中形成的这个回路中去掉一个权值最大的边（一定不是e）
就会得到另一颗树C，显然树C的权值比最小生成树树B要小。
（因为去掉边的权值要比加入边e的权值大）

这就与B是最小生成树矛盾。

唯一