假设一个城镇要用电缆连接多个地点:每条电缆都有安装成本,任意两点都要能直接或经其他地点互通。若安装成本非负,删去环上的一条边仍保持连通且不增加成本,因此可在最便宜的连通网络中选择一棵生成树。目标是整个网络的总成本最小,这与只找两点之间的最短路不同。
模型与交换原理
令 为有限、连通、无向图,至少有一个顶点;每条边 有实数权重 。生成树是包含所有顶点且连通、无环的子图。它有 条边,任意两点之间恰有一条路。权重总和最小的生成树称为最小生成树(MST)。有限连通图至少有一棵生成树,边集的选择又只有有限个,因此最小值存在。权重不必互异,也不必为正。
对非空真子集 ,割 是一端在 、另一端在外的所有边。若森林 没有边横跨此割,称此割尊重 。割的轻边是横跨该割、权重最小的边;可以有多条并列轻边。
定理 25.1.1
(安全边定理)
若森林 包含于某棵 MST 内,而割尊重 ,则任取该割的一条轻边 ,都存在一棵 MST 包含 。
证明。 取包含 的 MST 。若 已在 ,结论成立。否则把 加到 ,便与 中连接其两端的唯一路径组成一个环。该路径必定横跨此割;取其中一条跨割边 。由于割尊重 ,故 。从环移去 得到生成树 ,它包含 。轻边性质给出 ,所以 。由 的最小性,必为等号, 也是 MST。
证明透视
交换步骤究竟保证什么?
移去的边横跨尊重 的割,所以不会破坏已选的边。结论是存在“某棵”包含新边的最优树;权重并列时,它并不断言每棵最优树都包含新边。若 是割上唯一最轻边,任何不含 的生成树经同样交换都会严格降低成本,因此每棵 MST 必含 。
环规则方向相反:若一条边比同一环上的其他每条边都严格重,则它不属于任何 MST。理由是从含它的树移去该边后,环上另一条边必能重新连接两部分,而且成本较低。若只是并列最重,便不能排除它出现在所有 MST:三角形三边权重均为 1 时,每条边都出现在其中两棵 MST。
Kruskal 算法
把所有边按权重非递减排列。由空森林开始,依次检查每条边:若两端处于目前森林的不同连通分量,就加入;否则跳过。选满 条边即可停止,也可以扫描完整个清单。只有一个顶点时,空树就是答案。
为什么每次加入都安全?加入前取其中一端所在的分量为 。目前选中的边不横跨此割,而新边横跨它。若有较轻的跨割边,它早已被检查;它当时不可能因两端已连通而被跳过,因为分量只会合并,这会令它现在也不跨割。因此新边是轻边。安全边定理保持“已选森林包含于某棵 MST”的不变量。扫描结束时不可能仍有两个分量:原图连通,必有一条边横跨两个现存分量,而它被检查时两端也不可能已连通。故结果是生成树,并由不变量知它是 MST。权重相同的边可任意排序。
反例模式
任意割上的轻边未必安全
错误说法:任何割上的轻边都可加入一个包含于 MST 的森林。取三角形 ,各边权重均为 ,并取 MST 森林 。割 不尊重 ,因为 横跨它。其中 是轻边,但 是整个三角形,即一个环,所以没有生成树包含它。修补就是定理的假设:割必须尊重 ;Kruskal 算法取 为当前的一个分量,恰好保证了这一点。
实现时可用不相交集合数据结构检查及合并分量;通常排序需要 次比较,其余集合操作接近线性。正确性不依赖特定实现,也不依赖平局时的处理规则。
例题 25.1.2
(四个地点的选边与证明)
设边为 、、、、、。算法先选 ,跳过两端已由 连接的 ,再选 ,得到总权重 。
依次用 、、 证明三次选择:各割尊重之前的边,而所选边分别是割上轻边。 是环 上唯一最重的边,故不属于任何 MST; 和 也分别由环 和 排除。
易混淆之处
从指定根出发的最短路树使每个根到顶点的路长最短;MST 最小化的是已安装边的总权重。两者可以不同: 时,从 出发的最短路树选 ,总重 4;选 加其中一条权重 2 的边,总重只有 3。反过来,MST 也未必保留从根出发的最短路。负权重不影响上述树问题的比较与证明;但若允许任意连通子图,额外的负权边可以降低总成本,例如全为负权的三角形,三条边一起使用比任何生成树便宜。若图不连通,则不存在覆盖全图的生成树;Kruskal 得到各连通分量的最小生成森林。
练习
快速检查
(边为 。依 的次序检查三角形边,执行算法,另找一棵 MST,并解释 为何不在任何 MST。)
解答 · 答案
选 ,跳过 ,再选 ,总重 4。用 替换 得到另一棵同重生成树。 在环 上严格最重,故被环规则排除。
快速检查
(证明所有边权互异时 MST 唯一,指出何处需要严格不等式。)
解答 · 答案
假设不同的 MST 存在,取两者对称差中最轻的边 。删除 把 分为两部分; 中连接 两端的路径必有跨这两部分的边 。因权重互异及 的选法,。在 用 换走 得到严格更便宜的生成树,矛盾。
快速检查
(举例反驳“割上每条轻边都属于每棵 MST”,再给出正确陈述。)
解答 · 答案
三边权重均为 1 的三角形,每条边都是某个割的轻边,但也有一棵 MST 不包含该边。正确说法:轻边属于某棵 MST;若它是割上唯一轻边,则属于每棵 MST。
快速检查
(图有两个分量: 的边为 , 的边为 。执行算法并说明结果。)
解答 · 答案
选 ,跳过 ,总重 。这是最小生成森林:每个分量内的树分别最优。两分量之间没有边,因此整个图没有生成树。