证明寻找最小生成树的贪心算法一定会停止
Prove that a greedy algorithm for finding minimum spanning tree will definitely stop
这是一种在连通域中寻找最小生成树的算法
UN 有向图 G=(V,E):
初始化：B = ∅ - 算法将构建的边组
而|B| < |V| - 1 次：
一个。选择图 (S,V\S) 中没有属于 B 的边 e 穿过它的一些切割。
b。找到该切割的最轻边缘。
c。加入B组。
B = B ∪ {e}.
return T = (V,B)
cut的含义见附图：
Cut's meaning
顶点 s,u 在一组我们可以称为 S.
所有其他顶点都在组 V\S 中。
所以这就是(S,V\S)作为切的意义。
另外 - 边 (u,w) 是 交叉边
(u,v) 是该特定切割中 最轻的交叉边 。
(s,u)不是一个"crossing"边缘
我需要证明算法最终会停止。那|B| = |V| - 1
在某个时候。
我可以在证明中使用下面的说法：
'算法中任一点，都存在一棵最小生成树T=(V,Et)
包含算法选择的边组 B 的 G。'
假设我已经证明了这一点，我需要以某种方式证明图中总是有一些切割，他的交叉边的 none 已经被添加到 B 了。
而 |B|<|V|-1 。
但我不确定该怎么做
此算法的任何部分都不能永远循环。第 2 步循环的每次迭代都会增加 |B| 1.|B|将在恰好 |V|-1 次迭代后到达 |V|-1，此时循环终止。
如果你担心步骤2a不可行，G的(V, B)子图必须断开连接，因为它没有足够的边连接。我们总是可以将它的一些连接组件放在切口的一侧，而另一些放在另一侧。 （即使第 2a 步在某些时候是不可能的，这听起来也不像 non-termination 条件。）
让我们假设没有这样的切割并且|B| < |V| - 1. 由于树是连接的，这意味着所有的顶点都通过 B 中的一些边连接（因为如果一个顶点没有连接，将会有一个切割，其中没有边属于 B 将那个顶点和生成树分开)
作为，|V|顶点至少需要 |V| - 1条边被连接，我们推断|B| >= |V| - 1，因此与我们的假设相矛盾。
因此证明。
这是一种在连通域中寻找最小生成树的算法 UN 有向图 G=(V,E):
初始化：B = ∅ - 算法将构建的边组
而|B| < |V| - 1 次：
一个。选择图 (S,V\S) 中没有属于 B 的边 e 穿过它的一些切割。
b。找到该切割的最轻边缘。
c。加入B组。
B = B ∪ {e}.return T = (V,B)
cut的含义见附图： Cut's meaning 顶点 s,u 在一组我们可以称为 S.
所有其他顶点都在组 V\S 中。
所以这就是(S,V\S)作为切的意义。
另外 - 边 (u,w) 是 交叉边
(u,v) 是该特定切割中 最轻的交叉边 。
(s,u)不是一个"crossing"边缘
我需要证明算法最终会停止。那|B| = |V| - 1 在某个时候。
我可以在证明中使用下面的说法：
'算法中任一点，都存在一棵最小生成树T=(V,Et) 包含算法选择的边组 B 的 G。'
假设我已经证明了这一点，我需要以某种方式证明图中总是有一些切割，他的交叉边的 none 已经被添加到 B 了。 而 |B|<|V|-1 。 但我不确定该怎么做
此算法的任何部分都不能永远循环。第 2 步循环的每次迭代都会增加 |B| 1.|B|将在恰好 |V|-1 次迭代后到达 |V|-1，此时循环终止。
如果你担心步骤2a不可行，G的(V, B)子图必须断开连接，因为它没有足够的边连接。我们总是可以将它的一些连接组件放在切口的一侧，而另一些放在另一侧。 （即使第 2a 步在某些时候是不可能的，这听起来也不像 non-termination 条件。）
让我们假设没有这样的切割并且|B| < |V| - 1. 由于树是连接的，这意味着所有的顶点都通过 B 中的一些边连接（因为如果一个顶点没有连接，将会有一个切割，其中没有边属于 B 将那个顶点和生成树分开)
作为，|V|顶点至少需要 |V| - 1条边被连接，我们推断|B| >= |V| - 1，因此与我们的假设相矛盾。
因此证明。