假设有一个图 G，它的所有边都具有对应于不同整数的权重。所以没有两条边具有相同的权重。 令 E 为 G 的所有边。令 emax 为 E 中具有最大权重的边。 图G的另一个性质是每条边e都属于图G中的某个圈。
我必须证明 G 中没有最小生成树包含边 emax。
我明白为什么这是真的了，因为所有的边都是不同的并且每条边都属于一个循环，所以最小生成树算法可以简单地选择包含 emax 的循环中权重较低的边。 但我不确定如何具体证明。
最佳答案
这与 the Cycle Property of the Minimum Spanning Tree 有关，这基本上是说给定图中的一个循环，权重最大的边不属于 MST(上面链接中的矛盾很容易证明)。因此，由于边 emax 属于一个循环，因此它一定不能在 MST 中。
关于algorithm - 证明没有最小生成树包含最大加权边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20249088/