我真的在为这个证明而苦苦挣扎，非常感谢详细的解释：
显示一个包含 n 个顶点的完整图，MST 的权重小于或等于通过所有顶点的循环的最小权重（也称为哈密顿循环）？
问问题
694 次
2 回答
2
假设最小生成树的权重大于哈密顿循环，选择循环中的任意一条边并将其删除，它将成为一个新的生成树（覆盖所有顶点），其权重小于最小生成树，因此矛盾。
于 2016-03-28T13:47:15.657 回答
1
由于每个顶点都连接到所有其他顶点，因此节点的所有排列都可以构成有效的哈密顿循环。在完整图的可能哈密顿循环中，让我们选择成本最低的一个。
对于 N 节点图，假设节点 v 1 v 2 ...v N的排列 P和如下定义的边集 E 构成成本最低的哈密顿循环。E={(v 1 , v 2 ), (v 2 , v 3 ), ..., (v (N-1) , v N ), (v N , v 1 )}
让我们通过矛盾来证明有问题的引理。
假设存在一个 MST T，其权重总和大于 E 中所有边的成本总和。让我们将该成本总和命名为 c E。如果是这种情况，将存在另一棵树 T'，其边缘成本之和为 c E - c (vi , v ( i +1) )。基本上，我们可以切断 v N和 v 1之间的边缘，并将其余成本最低的哈密顿循环视为一棵树。只要边 (v N , v 1 ) 具有非负成本，c E - c (v i , v (i+1) )将小于或等于 T 的成本，其成本高于 c E。因此，存在冲突，我们对存在这种 MS T T 的假设一定是不正确的。
请注意，无论您切割哪条边，只要它具有非负成本，上述证明都是有效的。
于 2016-03-28T13:52:11.143 回答