algorithm - 证明子图是最小生成树

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' ？