证明没有最小生成树包含最大权重的边

Question

假设有一个图G，所有边的权值都对应不同的整数。因此，没有两条边具有相同的权值。 让E成为G的所有边。让emax是E中具有最大权重的一条边。 Graph G的另一个属性是每个边缘e都属于G中的某个循环。

我必须证明G的任何最小生成树都不包含emax边。

我可以看到为什么这是真的，因为所有边都不同，并且每个边都属于一个循环，最小生成树算法可以简单地选择包含emax的循环中更低权重的边缘。 但我不确定如何具体证明它。

- user65663

---

http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property - Geobits

这种类型的参数在证明一般结构的最优性属性方面非常有用，称为剪切和粘贴参数。您可以在CLRS中阅读更多相关内容。 - sukunrt

谢谢大家，现在我知道了这个，它变得很简单。 - user65663

Answer 1

这与最小生成树的环属性相关 (点击查看)，基本上是说给定图中的一个环，权重最大的边不属于最小生成树 (可以通过上面的链接进行简单证明)。因此，由于边 emax 属于一个环，它 必须不 在最小生成树中。

- Dimitris

Answer 2

证明方法为反证法。假设您有一棵包括最大边的最小生成树。如果您删除该边，您将有两个不再连接在一起的组件。每个顶点都在其中一个组件中。包括最大边的一个环。从最大边的一侧的顶点开始沿着环移动。因为您最终会在另一个组件中的最大边的另一侧循环，所以在那之前，您会发现一个边，它在一个断开的组件中具有一个顶点，并在另一个断开的组件中具有另一个顶点。由于组件是断开的，该边不在最小生成树中。通过将其添加到树中，您重新连接了组件并创建了一个比原来更小权重的最小生成树，因此您最初的最小生成树不是最小的。

- mcdowella

Answer 3

一个最小生成树是否包含最大权重的边呢？

有时候会包含，这取决于图的类型。如果最大权重的边是连接图的各个部分的唯一桥梁，那么这条边也必须出现在最小生成树中。

- Prabhakar