algorithm - Kruskal算法中增长的边缘集

Question

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
设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'，W（f） 只有当t'中的每一条边都已经在t中或与t–{e}形成一个循环时，才会发生这种情况。
…
注：这与Kruskal算法中的证明不同我们甚至不知道t'是否有联系。
我不知道下一步该怎么办。我非常感谢你的帮助，
提前谢谢

最佳答案

设T’为一个边集，以便|T| = |T’|证明W(T) <= W(T’)。
你很难做到这一点，因为这通常是错误的。
考虑

   1
 A---B
2 \ / 3
   C
   | 4
   D

kruskal的算法产生了边集 T = { (A,B), (A,C), (C,D) }，这是唯一的最小生成树。
但是边集 T' = { (A,B), (A,C), (B,C) }与 T具有相同的基数，并且

W(T') = 6 < W(T) = 7

在problem语句中缺少一些条件（比如 T'应该连接图形）。
你说得对我忘了提到 T'中没有循环
在这种情况下， T'跨越一棵树（1）。由于假定了 |T'| = |T|，所以 T'所跨的树连接图，即是一个生成树。
（1）由于没有循环，因此直接得出 T'的每个连接组件是一棵树具有 n顶点的树具有 n-1边因此，如果 T'具有 k连接的组件，则图中的顶点数为

V = |T'| + k

但是 T是一个生成树，因此

V = |T| + 1 = |T'| + 1

这意味着 |T| = |T'|。
因此，我们要求您简单地证明Kruskal算法的正确性你可以很容易地在文献中找到证据，例如 on wikipedia。
正确性证明（通过对顶点数的归纳）：
引理：设 k = 1为顶点为 G的连通图， N > 1为 T的最小生成树让 G成为 e中的边。
然后，通过识别 T的两个端点 T \ {e}和 G'投影到从 G获得的图的最小生成树。相反，如果 a是 b的一组边，投影到 e的最小生成树，则 T'是 G的最小生成树。
证明：让 G'作为识别 T' ∪ {e}和 G的投影。
则 p : G -> G'没有周期。
假设 a包含一个循环 b。那么 p(T \ {e})必须是连接 p(T \ {e})和 C的路径但随后 p^(-1)(C)将包含循环 a，这与 b是树的前提相矛盾。
因此 T是具有基数 p^(-1)(C) ∪ {e}的 T的无循环边集，这意味着（见上文）它是一个生成树。
设 p(T \ {e})为 G'和 N - 2的最小生成树。
则 T''没有周期。
如果 G'中有一个循环，则该循环将投射到 S = p^(-1)(T'')中的一个循环，因此 S ∪ {e}中的每个循环都必须包含 S假设 T''是 S ∪ {e}中的一个循环然后 e是连接 C和 S ∪ {e}的路径，因此 C \ {e}在 a中投射到一个循环，因为 b和 C \ {e}投射到 G'的同一顶点这与 a是树的前提相矛盾。
因此 b是没有循环的基数 G'的边集，因此（见上文）是 T''的生成树。
因为 S ∪ {e}是最小生成树，所以

W(p(T \ {e})) = W(T \ {e}) <= W(S) = W(T'')

由于 N - 1被假定为 G的最小生成树，因此等式成立， W(T) <= W(S ∪ {e})是 T的最小生成树， T''是 G'的最小生成树。
现在到归纳证明克鲁斯卡尔算法的正确性：
对于最多有两个顶点的图，很明显，该算法生成了一个最小生成树。
对于 p(T \ {e})，假设所有顶点最多 G'的连通图的算法是正确的（归纳假设）
设 S ∪ {e}为顶点为 G的连通图设 n >= 2为算法中选择的第一条边，其端点为 n和 G。
设 n+1为通过识别 e和 a从 b获得的图形，以及 G'投影。
设 G为算法选择的边集。
然后 a是Kruskal算法在 b上选择的边集因此，根据上面的引理， p :: G -> G'是 T的最小生成树。
（好吧，维基百科上的证据可能更简单，但我想换一个。）

关于algorithm - Kruskal算法中增长的边缘集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15054737/

上一篇：algorithm - boolean 函数密度的计算算法

下一篇：algorithm - BST 时间分析

Answer 1

设T’为一个边集，以便|T| = |T’|证明W(T) <= W(T’)。
你很难做到这一点，因为这通常是错误的。
考虑

   1
 A---B
2 \ / 3
   C
   | 4
   D

kruskal的算法产生了边集 T = { (A,B), (A,C), (C,D) }，这是唯一的最小生成树。
但是边集 T' = { (A,B), (A,C), (B,C) }与 T具有相同的基数，并且

W(T') = 6 < W(T) = 7

在problem语句中缺少一些条件（比如 T'应该连接图形）。
你说得对我忘了提到 T'中没有循环
在这种情况下， T'跨越一棵树（1）。由于假定了 |T'| = |T|，所以 T'所跨的树连接图，即是一个生成树。
（1）由于没有循环，因此直接得出 T'的每个连接组件是一棵树具有 n顶点的树具有 n-1边因此，如果 T'具有 k连接的组件，则图中的顶点数为

V = |T'| + k

但是 T是一个生成树，因此

V = |T| + 1 = |T'| + 1

这意味着 |T| = |T'|。
因此，我们要求您简单地证明Kruskal算法的正确性你可以很容易地在文献中找到证据，例如 on wikipedia。
正确性证明（通过对顶点数的归纳）：
引理：设 k = 1为顶点为 G的连通图， N > 1为 T的最小生成树让 G成为 e中的边。
然后，通过识别 T的两个端点 T \ {e}和 G'投影到从 G获得的图的最小生成树。相反，如果 a是 b的一组边，投影到 e的最小生成树，则 T'是 G的最小生成树。
证明：让 G'作为识别 T' ∪ {e}和 G的投影。
则 p : G -> G'没有周期。
假设 a包含一个循环 b。那么 p(T \ {e})必须是连接 p(T \ {e})和 C的路径但随后 p^(-1)(C)将包含循环 a，这与 b是树的前提相矛盾。
因此 T是具有基数 p^(-1)(C) ∪ {e}的 T的无循环边集，这意味着（见上文）它是一个生成树。
设 p(T \ {e})为 G'和 N - 2的最小生成树。
则 T''没有周期。
如果 G'中有一个循环，则该循环将投射到 S = p^(-1)(T'')中的一个循环，因此 S ∪ {e}中的每个循环都必须包含 S假设 T''是 S ∪ {e}中的一个循环然后 e是连接 C和 S ∪ {e}的路径，因此 C \ {e}在 a中投射到一个循环，因为 b和 C \ {e}投射到 G'的同一顶点这与 a是树的前提相矛盾。
因此 b是没有循环的基数 G'的边集，因此（见上文）是 T''的生成树。
因为 S ∪ {e}是最小生成树，所以

W(p(T \ {e})) = W(T \ {e}) <= W(S) = W(T'')

由于 N - 1被假定为 G的最小生成树，因此等式成立， W(T) <= W(S ∪ {e})是 T的最小生成树， T''是 G'的最小生成树。
现在到归纳证明克鲁斯卡尔算法的正确性：
对于最多有两个顶点的图，很明显，该算法生成了一个最小生成树。
对于 p(T \ {e})，假设所有顶点最多 G'的连通图的算法是正确的（归纳假设）
设 S ∪ {e}为顶点为 G的连通图设 n >= 2为算法中选择的第一条边，其端点为 n和 G。
设 n+1为通过识别 e和 a从 b获得的图形，以及 G'投影。
设 G为算法选择的边集。
然后 a是Kruskal算法在 b上选择的边集因此，根据上面的引理， p :: G -> G'是 T的最小生成树。
（好吧，维基百科上的证据可能更简单，但我想换一个。）