令 G = (V, E) 为加权、连通且无向图。令 T 为在 Kruskal 算法中增长并在 k 次迭代后停止的边集（因此 T 可能包含少于 |E|-1 条边）。令 W(T) 为该集合的加权和。令 T' 是一个无环边集，使得 |T| = |T'|。证明 W(T) <= W(T')
我理解算法的原始证明，我尝试了几种方法来解决这个问题，但都没有奏效。
例如：我想对 |T| 进行归纳。可能会奏效。对于 |T| = 1 很明显。
我们假设 |T|=k 的正确性并证明（或不……）k+1。通过矛盾假设存在一个边集 T' 使得 |T'|=k+1 并且 W(T') < W(T)。
设 e 为 Kruskal 算法添加的最后一条边。因此，对于 T' 中的任何边 f，W(f) < W(e)（否则我们从 2 个集合中删除边并得到矛盾）。
只有当 T' 中的每条边都已经在 T 中或与 T - {e} 形成一个循环时，才会发生这种情况。
…</p>
注意：这与 Kruskal 算法中的证明不同。我们甚至不知道 T' 是否连通。
我不知道下一步该做什么。我真的很感激任何帮助，在此先感谢