最小树形图与 Chu–Liu–Edmonds 算法

形式陈述 ​

问题与局部选择 ​

采用有限有向图的独立弧记录变体理路有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。 $D=(V,A,s,t)$，每条弧带有限实权理路实数系Real number system · Ordered complete field满足序域公理与上确界完备性的数系。 $c(a)$，并指定根 $r\in V$。允许原始输入有平行弧和自环，但先丢弃自环及指向根的弧；二者都不可能进入本页所求的结构。出树形图（out-arborescence）是从 $r$ 向外到达全部顶点的有向生成结构：每个 $v\ne r$ 恰有一条选中入弧，$r$ 没有选中入弧，并且从 $r$ 可沿选中弧到达所有顶点。目标是使选中弧总权最小。先检查根可达性；若某个顶点从 $r$ 不可达，则实例无解。单顶点实例返回空弧集，权重为零。

Chu–Liu–Edmonds 先选取各点的局部最小入弧：对每个 $v\ne r$ 选一条最轻入弧 $e_v$，并排除指向根的弧。若这些弧没有形成有向圈，它们已经让每个非根顶点恰有一个父弧，并且根可达所有顶点；每个顶点都达到独立的最轻入弧下界，所以所得树形图最优。

缩环、重赋权与展开 ​

若选中弧形成有向圈 $C$，根不在 $C$ 中，任何根树形图都必须有至少一条外部弧进入 $C$。下面的交换证明保证存在最优解只保留一个入口 $(u,v)$，并以它替换圈中指向 $v$ 的 $e_v$。把 $C$ 收缩为超点，对每条进入 $v\in C$ 的外部弧定义

圈内基准成本 $\sum _{x\in C}c(e_x)$ 已经统一支付，$c(u,v)-c(e_v)$ 正是选择外部弧、替换 $e_v$ 所增加的成本。离开 $C$ 的弧和圈外弧保持原权；圈内弧在缩图中删除，收缩产生的平行弧保留各自原弧身份。递归求缩图的最优树形图后，若递归解选择了原终点为 $v$ 的进入超点弧，就保留该外部弧、删除 $e_v$，并保留圈中其余选中弧。

正确性不变量 ​

一般可行树形图可以多次进入 $C$，所以不能直接把所有原解与缩图解声称为一一对应。正确的比较先将任意原树形图 $T$ 改成一种成本不增的规范形式。

从 $T$ 中取一条根到 $C$ 的路径，保留其第一次进入 $C$ 的弧 $a=(u,v)$；根到 $u$ 的这段路径完全在 $C$ 外。对每个 $x\in C\setminus \{v\}$，把 $T$ 中原来进入 $x$ 的弧替换为选定的最轻入弧 $e_x$，其余终点在圈外的弧保持不动。每次替换都不增加费用。得到的 $T_0$ 仍让每个非根点恰有一条入弧；从根先沿保留路径进入 $v$，再沿 $C\setminus \{e_v\}$ 到达全部圈点。任何圈外点也仍可达：沿它在原 $T$ 中的根路径，圈外终点的弧都保留，而遇到的圈点已经可达。因此 $T_0$ 是根树形图，且仅由 $a$ 从外部进入 $C$。

令 $B_C=\sum _{x\in C}c(e_x)$。上述规范树收缩后得到合法缩图树 $T^{\prime }$，满足

反过来，任意缩图根树形图在非根超点 $C$ 恰有一个入口；按记录的原终点 $v$ 展开，并补上所有 $e_x$（$x\in C\setminus \{v\}$），就得到同样成本等式的合法原树。因而

一边使用任意最优原解的成本不增规范化，另一边使用缩图最优解的精确展开；这里需要的是两个方向的最优值比较，而非每个原解的双射。每次收缩至少两个顶点，按顶点数作数学归纳理路数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。即可证明递归算法正确并终止。

多层收缩时，这个对应关系逐层嵌套。实现必须为每层保存圈成员、各顶点选中的 $e_v$、重赋权弧对应的原弧及其原终点，并按收缩的逆序展开；只保存新端点与新费用无法恢复原始弧集合。