我将在下周完成我书中的所有练习来修改课堂测试，我对这个子图问题感到非常困惑。
目前，我的想法使我相信，由于我们已经有一个最小生成树 G，因此由于我们在该最小生成树中存在子节点，因此 G' 必须存在。就条件而言，我有点茫然。
如果 X' 的节点集和边集分别是 X 的节点集和边集的子集，则图 X' 是图 X 的子图。让我们将 (V,T) 作为 G 的最小生成树，并且 G'=(V',E') 是 G 的连通子图。
(a)证明(V′,E′∩T)是G′的最小生成树的子图。
(b) 在什么条件下 (V′,E′∩T) 是 G′ 的最小生成树？证明你的主张。
提前致谢！
对于（一）
我真的不明白这个问题......你能解释一下吗？
对于(b)
我觉得如果
对于 if和thene=(u,v)中的每一个Tu in V'v in V'e in E
那么我们就有(V′,E′∩T)了 的最小生成树G'。
因为：
e有一些，则
根本没有连接。它当然不可能是一棵生成树e=(u,v)Tu in V'v in V'in E'(V′,E′∩T)G'(V′,E′∩T)不是 的生成树G'，则G'有一个成本较低的生成树，假设它是Tg。我们可以通过以下方式构建成本低于T'的生成树：（i）从（ii）添加每个中删除每个 。生成的图是 的生成树（因为它是连接的同时具有相同数量的边）并且成本低于。所以它永远不会发生，因为我们已经知道是 的最小生成树。GTe=(u,v) , u in V' and v in V' and e in TTe=(u,v) , u in V' and v in V' and e in TgGTTTT(a) 正如我在评论中提到的 (V', E' ∩ T) 可能包含多个组件。通常，G' 的最小生成树将需要更多边。问题是在 E' ∩ T 中是否已经给出了一些可以不用的边。因此，我们可以将问题改写为 G' 存在最小生成树 (V', T')，使得 E' ∩ T ⊂ T'。
这是使用Kruskal 算法的证明及其正确性证明。Kruskal 算法中按权重枚举边不是确定性的。尽管边是按权重排序的，但在权重相等的边上的枚举是不确定的。然而，对于每棵生成树，都有一些边的单调枚举产生最小生成树 (V,T)。令 E_x 为权重为 x 的所有边的集合。对于排序，选择任何顺序，使得 E_x ∩ T 中的所有边都排在 E_x \ T 中的边之前。E_x ∩ T 中的所有边都不会在 Kruskal 算法中检查它们的步骤中形成循环，因为它们出现在最终的最小生成树。它们出现的顺序也无关紧要，因为顺序不会改变循环的不存在。然后，E_x\T 中的所有边都被丢弃，因为它们会形成循环，
对于下一步，我们再次在 G' 上运行 Kruskal 算法，使用的排序将产生我们给定的 G 的最小生成树。将此树称为 (V', T')。这里的关键属性是，当我们这样做时，E' ∩ T 中的所有边都在任何其他边之前添加。相反，假设某个边 t ∈ E' ∩ T 在 G' 上的运行中会被拒绝，因为它形成了一个循环。这意味着某个链 C 已经在计算 (V,T) 时边 t 是第一个连接的两个组件之间形成了连接。如果是这样，同一条链将在原始运行中连接这些组件，而他们没有。现在考虑在将 E_x ∩ T 中的边添加到进行中的树之后立即在 G' 上的 Kruskal 算法的状态。克鲁斯卡尔的任何东西
(b) 这部分主要是 (a) 部分的推论，即观察到边集 E' ∩ T 在 Kruskal 算法运行的某个点始终是有效状态。因此，如果算法在该点完成，即边集已用尽，则 E' ∩ T 恰好是最小生成树的边。条件是算法在处于这种状态时结束，因此当 (V', E' ∩ T) 连接时，Kruskal 算法终止并且 (V', E' ∩ T) 是最小生成树。相反，如果 (V', E' ∩ T) 是最小生成树，那么它必然是连通的。
'a' 部分几乎立即从观察到最小生成树（例如(V,T)）确实是最小的！这是证明的一部分的草图：
假设矛盾(V′,E′∩T)不是最小的。这意味着e in E′∩T我们可以删除一些内容，同时仍保留其连接性。这意味着e也可以从 T 中删除，这显然不能，因为T它是最小的。
对于“b”部分，我认为 lavin 提供了一个不错的解决方案。希望这会有所帮助。
我为不耐烦的人提供了一个非正式的 tl;dr 版本 :) eh9 值得赏金
a - 存在由 T 与所有边 v' 可能具有的交点形成的 v' 的生成树。E' ∩ T 必然是这个的一个子集
b - 条件是 (V', E' ∩ T) 连接时。E'中的任何非最小边和环都被与T的交集丢弃，并且任何剩余的最小连通图都是MST