algorithm - 最小生成树子图

Question

为了复习下周的类考试，我正在复习我书中的所有练习，我对这个子图问题真的很困惑。

目前我的想法使我相信，既然我们已经有了一个最小生成树 G，那么既然我们在那个最小生成树中有子节点，那么 G' 就必须存在。就条件而言，我有点不知所措。

A graph X′ is a sub-graph of graph X if the node and edge sets of X′ are subsets of the node and edge sets of X respectively. Let us have (V,T) as a minimum spanning tree of G and G′=(V′,E′) be a connected sub-graph of G.

(a) Prove that (V′,E′∩T) is a sub-graph of a minimum spanning tree of G′.

(b) Under what condition is (V′,E′∩T) a minimum spanning tree of G′? Prove your claim.

提前致谢!

Answer 1

(a)

我真的不明白这个问题......你能解释一下吗？

(b)

我认为是

对于 T 中的每个 e=(u,v) 如果 u in V' 和 v in V' 然后 E 中的 e

那么我们有(V′,E′∩T)是G'的最小生成树。

因为 :

1. 如果一些 e 在 T 中有 e=(u,v) if u 在 V'和 v in V' 但不是 in E'，然后 (V′,E′∩T) 根本没有连接。肯定不可能是G'
的生成树
2. 如果条件成立，但(V′,E′∩T)不是G'的生​​成树，则G' 有一个成本更低的生成树，假设它是 Tg。我们可以构造一棵 G 的生成树 T'，其成本低于 T，方法是:(i) 删除每个 e=( u,v) , u in V' and v in V' and e in T from T (ii) 添加每个 e=(u,v) , u in V ' 和 V 中的 v' 和 Tg 中的 e 。生成的图是 G 的生成树(因为它是连接的，同时具有与 T 相同数量的边)并且成本低于 T .所以它永远不会发生，因为我们已经知道 T 是 T 的最小生成树。