证明子图是最小生成树

Question

鉴于：

G = (V,E)
T is an MST of G
G'=(V', E') ⊆ G
T' is an MST of G'

证明：

(V',E∩T) is a subgraph of T'

Under what conditions is E∩T an MST of G'?

边权重不需要不同。

我的做法：

通过将 Kruskal 算法应用于 E∩T 中的边，可以按权重的升序连接边，同时确保连接不会产生循环。这将产生一个 MST，但是我们可以证明这个MST是T'的子图吗？

这种方法有意义吗？由于我没有使用 T 是 G 的 MST 这一事实，我有一种预感，我忽略了一些重要的事情。

Answer 1

第一个观察：任何节点数为|V'|且边数为|V'|-1的图都不是树，因此一个必要条件是：|E∩T| = |V'|-1

第二个观察：如果T'是G'的MST，那么它的边之和在G'的所有其他可能生成树中是最小的。这意味着如果 (V', E∩T) 是 G' 的 MST，那么它的边之和必须等于 T'

的边之和

根据以上观察，(V', E∩T)成为G'的MST的充要条件是：
1. |E∩T| = |V'|-1
2. sumofweights((V', E∩T))=sumofweights(T')

所以，基本上你需要做的是计算E∩T中的边数并与|V'|-1进行比较，同时计算T'中的边权重之和，与 E∩T

中的边权重之和进行比较

但是我对这一行有些怀疑：(V',E∩T) is a subgraph of T'
由于 T' 也有 V' 个节点，T' 的任何子图除了 T' 本身，都不是树，如果它不是树，它就不可能是MST要么。可能是 (V',E∩T) is a subgraph of G' 或 (V',E∩T) is a subgraph of T，而不是 (V',E∩T) is a subgraph of T'?

证明子图是最小生成树

Prove that a subgraph is a minimum spanning tree

algorithm

graph-theory

minimum-spanning-tree