从局部选择到整棵树
网络可能有许多方法连接全部顶点。这与从单一起点找最短路径不同:一条选中边在树的成本中只计一次,不是每条使用它的路径都再计一次。
定义 4.1.1
(生成树、最小生成树与跨割边)
假设输入为有限、连通、无向且没有自环的多重图,有 个顶点及 条边。平行边彼此不同,也可有相同权重。边权可以是任意有限实数,包括零和负数。生成树连接每个顶点且没有环,所以有 条边;其权重是所选边的权重之和。最小生成树使这个总和最小。对顶点集 (),若一条边恰有一个端点在 中,就说它跨越割 。以下把权重比较计为常数成本运算。当 ,空边集是权重为零的生成树。
算法
把边按权重非递减排序;相同权重可按任一固定次序处理。从空集合 开始扫描:若当前边的两端位于 的不同连通分量,便加入它;否则跳过。扫描完后输出 。
命题 4.1.2
(输出是生成树)
对连通的输入,扫描所输出的 是一棵生成树。
证明
(没有环,分量之间也没有空隙)
所选边始终没有环,因为每条新边都连接两个不同分量。最后的森林必连接所有顶点:否则,由于输入连通,原图中连接两个最终分量的边路径上,必有一条边从一个最终分量跨到另一个,而该边被扫描时两端在不同分量,不可能被跳过。连通森林是树,因此有 条边。
引理 4.1.3
(割的交换)
设 包含于某棵最小生成树 ,并设 是顶点集(),使 中没有边跨越 。若 是所有跨越此割的边中最轻的一条,则 包含于某棵最小生成树。
证明
(以 e 换走较重的跨割边)
若 ,保留 。否则把 加入 会产生唯一的环。环跨越一个割的次数是偶数,而 是其中一次,所以环中还有另一条跨割边 ,且 。 中没有边跨越此割,所以 。由于 是跨割边中最轻的,。从 中移走 会破坏唯一的环,剩下一个有 条边的连通图,即生成树 。它包含 ,权重为 。由于 最小, 也是最小生成树。
定理 4.1.4
(Kruskal 的贪心保证)
对符合上述假设的每个连通输入,算法都输出最小权重生成树。相同权重和负权重均不影响此保证。
交换不变量
证明
(每条被选的边都是最轻的跨割边)
维持不变量:存在一棵最小生成树包含 中已选的每条边。起初成立,因为有限连通图有最小生成树。假设算法即将加入 ,其两端位于 的不同分量。令 为含有其中一个端点的分量。 是分量,所以 的边都不跨越 。
是最轻的跨割边。若另一条跨割边 在排序中较早出现,则它被扫描时两端已在不同分量,因为分量只会合并,且在加入 前仍然分开。算法便会选取它,与 没有跨割边矛盾。因此每条跨割边在排序中都在 之后或就是 ,权重至少为 ,相同权重也一样。由割的交换引理,不变量得以维持。被跳过的边不改变 。
结束时 本身是生成树,并包含于某棵最小生成树。相同顶点集上的两棵生成树均有 条边,所以二者相同。这证明输出最优,而不只是证明它是一棵树。
证明透视
为何下一条跨割边安全
不明显的一步是交换:不去讨论所有生成树,而是取一棵已包含 的最优树,再作局部修补。每个假设各有作用。输入连通,加上 中有边跨越该割,保证了 所产生的环含有第二条跨割边 。 是 的分量这一点,使 不属于 ,所以交换不会破坏已选的边。排序扫描使 成为跨割边中最轻的,而不等式 只需要 ,因此相同权重没有影响。
论证中没有对权重作加、减或缩放,只作比较,所以负权重也允许。证明得以完结,是因为每一步都保留一棵最优树,而最终的 恰有 条边,没有余地与那棵树不同。若 只是某条跨割边而不是最轻的,交换可能使权重增加,不变量便会失效。
扫描例子
例题 4.1.5
(相同权重与被跳过的边)
设 权重为 , 和 权重为 , 权重为 , 权重为 。若相同权重中先扫描 ,便选取 ;跳过会闭合三角形的 ;再选取 。所得树权重为 。若两条同权边次序相反,便选 、跳过 ,得到另一棵同权重的最小树。交换证明涵盖两种次序。
例题 4.1.6
(平行边与负权重)
取顶点 , 与 之间有两条平行边,权重分别为 和 ,另有权重 的边 与权重 的边 。排序后依次是权重 的边、、,然后是权重 的边。选取连接 的权重 的边;选取 ,把 接到该分量;跳过 ,因为 已连通;也跳过权重 的平行边。所得树有两条边,权重为 。其余四棵生成树的权重为 、、 和 ,都较大。
例题 4.1.7
(不连通的输入只得到森林)
取四个顶点 ,只有权重 的边 和权重 的边 。扫描把两条都选取,结束时只有 条边,而生成树需要 条。输出是权重为 的最小生成森林,但整个图不存在生成树,所以上面的保证并不适用。
反例模式
最便宜的边可能形成环
考虑 构成的三角形,三边权重均为 ,另有权重为 的边 。三条最便宜的边构成环,并使 没有连接,尽管四个顶点需要的边数正是三。生成树必须选 和两条三角形边,权重为 。按权重排序必须配合分量测试:它会跳过三角形的第三条边,然后选取 。
常见错误
(权重相同时以为答案唯一)
在第一个扫描例子中, 与 的两种次序给出两棵不同的最小生成树 与 ,权重同为 。决胜规则决定输出哪一棵,却不影响它是否最优。只有当所有权重互不相同时,最小生成树才是唯一的。
常见错误
(先去掉或平移负权重)
由于最短路径的方法可能需要非负权重,人们容易想到把每条边加上同一个常数。这里并不需要:证明只比较权重。对权重为 的三角形,算法直接选取 与 ,无须调整。对生成树而言,把每条边都加上同一个常数 ,每棵树的权重恰好改变 ,所以最优树不变,但这是关于生成树的观察,并不是算法的要求。
实现与边界
一种简单实现为每个顶点存储当前分量标签。合并两个标签时扫描所有顶点,把其中一个标签改为另一个。测试需 ,合并需 ,故在此比较模型下,排序与扫描共用 次运算。更快的分量数据结构需要另行分析;以上证明不依赖特定实现。
若输入不连通,同一扫描会得到森林,但整个图不存在生成树。在声称得到生成树前,应检查连通性,或检查最终森林是否有 条边: 个顶点上的森林若有 条边便连通。负边可以被选中,也不会使目标向下无界,因为有限图只有有限多棵生成树。
练习
快速检查
(在例子中先扫描 再扫描 ,列出所选边及总权重。)
跳过会闭合环的边。
解答 · 答案
选取 ,跳过 ,总权重为 。
快速检查
(一个三角形的边权为 ,求一棵最小生成树及其权重。)
三角形的生成树有两条边。
解答 · 答案
选权重为 和 的边,得到权重 的树。交换论证对负权重仍然有效。
快速检查
(为什么被选边与另一条相同权重的跨割边,都可能分别出现在某棵最优树中?)
看看交换证明需要哪个不等式。
解答 · 答案
交换证明只需要 ,不要求严格不等。交换同权边可以保持最优总权重;最优树不一定唯一。
快速检查
(一个图有四个顶点,扫描结束时选了两条边。它能有生成树吗?为什么?)
生成树有多少条边?连通的输入上扫描会得到什么?
解答 · 答案
不能。所选边构成森林;若输入连通,扫描会产生有三条边的生成树,因此只有两条边证明输入不连通。