展示一个有n个顶点的完全图，一个MST的权值小于或等于通过所有顶点的圈的最小权值
Show a complete graph with n vertices, the weight of a MST is less than or equal to the min weight of cycle that passes through all vertices
我真的在为这个证明而苦苦挣扎，非常感谢详细的解释：
显示一个n个顶点的完全图，一个MST的权值小于或等于通过所有顶点的圈（也叫哈密尔顿圈）的最小权值？
假设最小生成树的权重大于一个哈密顿环，选择环中的任意一条边去掉它，就会变成一棵新的权重小于哈密顿环的生成树（覆盖所有顶点）最小生成树，因此矛盾。
由于每个顶点都与所有其他顶点相连，因此节点的所有排列都可以构成有效的哈密顿循环。在完整图的可能的哈密顿圈中，我们选择成本最低的一个。
对于 N 节点图，假设节点的排列 P v1v2...vN和下面定义的边集E构成成本最低的哈密顿循环。
E={(v1, v2), (v2, v3), ..., (v(N-1), vN), (vN, v1)}
让我们用反证法证明被质疑的引理。
假设存在一个 MST T，其权重之和大于 E 中所有边的成本之和。让我们将该成本之和命名为 cE。如果是这样的话，就会存在另一棵树 T' 使得它的边成本之和为 cE - c(vi, v(i+1)).基本上我们可以切断 vN 和 v1 之间的边，并将最小成本哈密顿循环的其余部分视为一棵树。只要边 (vN, v1) 具有非负成本，cE - c(vi, v(i+1)) 将小于或等于到T的成本，其成本高于cE。因此，存在冲突，我们关于存在这样的 MST T 的假设一定是不正确的。
请注意，无论您切割哪条边，只要它具有非负成本，上述证明都是有效的。
我真的在为这个证明而苦苦挣扎，非常感谢详细的解释：
显示一个n个顶点的完全图，一个MST的权值小于或等于通过所有顶点的圈（也叫哈密尔顿圈）的最小权值？
假设最小生成树的权重大于一个哈密顿环，选择环中的任意一条边去掉它，就会变成一棵新的权重小于哈密顿环的生成树（覆盖所有顶点）最小生成树，因此矛盾。
由于每个顶点都与所有其他顶点相连，因此节点的所有排列都可以构成有效的哈密顿循环。在完整图的可能的哈密顿圈中，我们选择成本最低的一个。
对于 N 节点图，假设节点的排列 P v1v2...vN和下面定义的边集E构成成本最低的哈密顿循环。 E={(v1, v2), (v2, v3), ..., (v(N-1), vN), (vN, v1)}
让我们用反证法证明被质疑的引理。
假设存在一个 MST T，其权重之和大于 E 中所有边的成本之和。让我们将该成本之和命名为 cE。如果是这样的话，就会存在另一棵树 T' 使得它的边成本之和为 cE - c(vi, v(i+1)).基本上我们可以切断 vN 和 v1 之间的边，并将最小成本哈密顿循环的其余部分视为一棵树。只要边 (vN, v1) 具有非负成本，cE - c(vi, v(i+1)) 将小于或等于到T的成本，其成本高于cE。因此，存在冲突，我们关于存在这样的 MST T 的假设一定是不正确的。
请注意，无论您切割哪条边，只要它具有非负成本，上述证明都是有效的。