问题的根源在于算法的引入练习。
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是唯一的最大权重边，则它不在唯一的生成树中，这是所有其他链接。如果有一个以上的最大权重的边缘，那么有许多不同的最小生成树，因为有最大权重的边，它们中的每一个都省去了最大权重的不同边并保持其他权重。
考虑当只有最大重量的一个边缘时的情况。假设有人给你一个使用这个边的最小生成树。从树中删除它，得到两个断开连接的组件现在尝试在循环中逐个添加其他边。如果边没有连接两个组件，请再次将其删除。如果任何边连接这两个组件，则生成树的权重比以前小，因此它不可能是最小生成树。是不是没有一条边连接这两个部件？添加一个不连接两个组件的边不会增加从任一组件到达的节点集，因此如果没有单个边缘连接两个组件，则同时添加所有组件不会。但是，我们知道添加所有这些边添加了连接由先前的最大权值边缘连接的两个节点的路径，因此其中一条边必须连接组件。所以我们原来的所谓最小生成树不是，并且在一个循环中具有唯一的最大权重的边不能是最小生成树的一部分。
关于algorithm - 在某个循环中是否存在包含最大权重边的最小生成树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40296852/