在某个循环上是否存在包含最大权重边的最小生成树？
Is there any minimum spanning tree that contains the maximum-weight edge on some cycle?
原题出自练习算法导论.
23.1-5 令 e 是连通图 G=(V, E) 的某个循环上的最大权重边。证明有一棵G'=(V, E - {e})的最小生成树也是一棵G的最小生成树。即有一棵G的最小生成树不包含e.
问题是：我认为命题所有G的最小生成树都不包含e是正确的。 e 是某个循环 上唯一的一条最大权重边。是吗？
更新: 2016-10-28 20:21
添加限制e是在某个循环上唯一的最大权重边。
一个测试用例是当有标记为 0..n-1 的节点并且仅在节点 i 和节点 (i + 1) mod n（即环）之间存在链接时。在这种情况下，最小生成树是通过只留下一个链接来创建的。如果 e 是唯一的最大权重边，则它不在唯一的生成树中，这是所有其他链接。如果最大权重的边不止一条，那么不同的最小生成树的数量与最大权重的边的数量一样多，每棵树都会留下一条不同的最大权重的边，而保留其他的。
考虑只有一条边具有最大权重的情况。假设有人给你一棵使用这条边的最小生成树。从树中删除它，给你两个断开连接的组件。现在尝试在循环中添加其他每条边，一次一个。如果边缘没有连接两个组件，请再次删除它。如果有任何边连接两个组件，则生成树的权重比以前小，因此它不可能是最小生成树。 none 的边连接这两个分量会不会是这种情况？添加不连接两个组件的边不会增加从任一组件可到达的节点集，因此如果没有单个边连接两个组件，则同时添加所有这些组件也不会。但是我们知道，添加所有这些边会添加一条路径，连接由先前最大权重边连接的两个节点，因此其中一条边必须连接组件。所以我们原来所谓的最小生成树不是，在一个循环中唯一最大权重的边不能成为最小生成树的一部分。
您猜对了：
所有G的最小生成树不包含e都是对的
首先我们需要证明：
e 不是与 G 的任何切割相交的光边。
设 C 是切割 e 的任何切割，因为 e 在一个循环中，所以 e 不是任何这些切割的轻边，并且所有其他切割都不会有边缘 e 穿过它，我们对于这些切割中的任何一个，边缘都不会有光。
那么我们需要证明：
如果e不是穿过G的任意割的轻边，则G的所有最小生成树都不包含e。
这正是23.1-3的逆命题
原题出自练习算法导论.
23.1-5 令 e 是连通图 G=(V, E) 的某个循环上的最大权重边。证明有一棵G'=(V, E - {e})的最小生成树也是一棵G的最小生成树。即有一棵G的最小生成树不包含e.
问题是：我认为命题所有G的最小生成树都不包含e是正确的。 e 是某个循环 上唯一的一条最大权重边。是吗？
更新: 2016-10-28 20:21
添加限制e是在某个循环上唯一的最大权重边。
一个测试用例是当有标记为 0..n-1 的节点并且仅在节点 i 和节点 (i + 1) mod n（即环）之间存在链接时。在这种情况下，最小生成树是通过只留下一个链接来创建的。如果 e 是唯一的最大权重边，则它不在唯一的生成树中，这是所有其他链接。如果最大权重的边不止一条，那么不同的最小生成树的数量与最大权重的边的数量一样多，每棵树都会留下一条不同的最大权重的边，而保留其他的。
考虑只有一条边具有最大权重的情况。假设有人给你一棵使用这条边的最小生成树。从树中删除它，给你两个断开连接的组件。现在尝试在循环中添加其他每条边，一次一个。如果边缘没有连接两个组件，请再次删除它。如果有任何边连接两个组件，则生成树的权重比以前小，因此它不可能是最小生成树。 none 的边连接这两个分量会不会是这种情况？添加不连接两个组件的边不会增加从任一组件可到达的节点集，因此如果没有单个边连接两个组件，则同时添加所有这些组件也不会。但是我们知道，添加所有这些边会添加一条路径，连接由先前最大权重边连接的两个节点，因此其中一条边必须连接组件。所以我们原来所谓的最小生成树不是，在一个循环中唯一最大权重的边不能成为最小生成树的一部分。
您猜对了： 所有G的最小生成树不包含e都是对的
首先我们需要证明： e 不是与 G 的任何切割相交的光边。
设 C 是切割 e 的任何切割，因为 e 在一个循环中，所以 e 不是任何这些切割的轻边，并且所有其他切割都不会有边缘 e 穿过它，我们对于这些切割中的任何一个，边缘都不会有光。
那么我们需要证明： 如果e不是穿过G的任意割的轻边，则G的所有最小生成树都不包含e。 这正是23.1-3的逆命题