怎么证明权重不相同的加权无向图的最小生成树是唯一的 （图论）

怎么证明权重不相同的加权无向图的最小生成树是唯一的 （图论）

设G是所有边权均不相同的无向联通图。

证明一：

首先，易证图G中权值最小的边一定是最小生成树中的边。(否则最小生成树加上权值最小的边后构成一个环，去掉环中任意一条非此边则形成了另一个权值更小的生成树)。

之后用反证法，假设G存在俩个不同的最小生成树

①.设G的俩个不同的最小生成树T1 T2，设这俩颗生成树的并集为子图G1，G1为连通图且T1 T2显然为G1的最小生成树，由首先可得知俩颗生成树至少包含一条公共边，将G1中两颗生成树的公共边删去，得到子图G2。G2由一个或多个连通分量组成，其中至少有一个连通分量的最小生成树不唯一（否则若所有连通分量的最小生成树唯一，则将删掉的公共边加上，则T1等于T2，这与假设相矛盾）。

②.对其中一个最小生成树不唯一的连通分量设为H，若H中点数>2，重复①的操作。否则H中只有俩个点，由于所有边权值不同，显然最小生成树唯一，这与①中的最后一句相矛盾。

综上，所有边权均不相同的无向图最小生成树是唯一的。

证明二：

设T，T’为G的俩个最小生成树，设T的边集E(T)={e1,e2,...,em}，T'的边集E(T')={e'1,e'2,...,e'm}。

设ek满足ek≠e'k且k最小，由于所有边权值不同，不妨假设weight(ek)

还有一个更强的结论：同一个图不同最小生成树的边权重序列相同。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。