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

问题与局部选择

给加权有向图和根 $r$ ，入树形图是以 $r$ 为根的有向生成结构：每个 $v\ne r$ 恰有一条选中入边， $r$ 没有选中入边，并且从 $r$ 可达所有顶点。它不是无向生成树加一个方向标签。若某顶点从 $r$ 不可达则无解。先为每个 $v\ne r$ 选最轻入边；若选边无有向环，它们已构成树形图，并因每个顶点独立达到最小入边下界而最优。

缩环与重赋权

若最轻入边形成环 $C$ ，任何根树形图必须舍弃环内恰一条入边，并用一条外部边 $(u,v)$ 进入 $C$ 。收缩 $C$ 为超点；进入 $v\in C$ 的边重赋费用

c'(u,C)=c(u,v)-c(e_v),

其中 $e_v$ 是原先为 $v$ 选的最轻入边。这记录“用外边替换 $e_v$ ”的额外成本。递归求缩图最优树形图，展开时保留进入环的外边并删除其目标 $v$ 的 $e_v$ ，其余环边保留。

局部贪心失败例子

三个非根顶点各自最便宜入边可能形成 $a\to b\to c\to a$ 。直接任选删除一边可能迫使使用极贵的外部入边；缩环把所有可能进入点的替换代价放在同一个超点上，让递归选择真正最便宜的破环方式。

边界与方向

这不是 Prim/Kruskal 的有向版，不能套无向 cut property。根、入树形图还是出树形图、最小还是最大版本会整体反转边方向或权重。平行边与负权可处理，但重赋权和展开映射必须保存原边身份；未指定根的 optimum branching 是不同问题。

收缩正确性图像

环 $C$ 内所有顶点已各付出最小入边成本 $\sum_{v\in C}c(e_v)$ 。任何可行树形图必须用一条外边进入某个 $v$ ，并删除 $e_v$ 破环；重赋权 $c(u,v)-c(e_v)$ 正是相对这份基准多付的成本。缩图最优选择哪个进入边，就等价于原图最优选择在哪个顶点破环。

展开时若递归树不选进入超点的边，说明收缩环所在分量对根不可达，输入不可行或前面处理有误。多层嵌套环需用栈保存每次环成员、选中入边和原边映射，按逆序展开。

缩环后怎样恢复入边

对环 $C$ 中每个顶点 $v$ ，记已选最轻入边费用为 $m(v)$ 。外部边 $(u,v)$ 进入收缩点时改权为 $w(u,v)-m(v)$ ；这表示若最终选它，需要替换掉环内指向 $v$ 的那条最轻入边，额外付出的正是两者差。

递归解若选择某条进入收缩点、原终点为 $v$ 的边，展开时保留这条外部边，并删除环内指向 $v$ 的已选边；环其余边保留，恰好打破一个环且让所有环顶点从根可达。若收缩点没有外部入边而又不含根，则原实例不可行。

一次实现需要保存：每轮各顶点所选入边、每个有向环的成员、重赋权边对应的原边，以及递归返回时被替换的环顶点。只在收缩图上保存端点和新费用，会在展开时无法还原原始边集合。

经典朴素实现为 $O(VE)$ ；更快版本依赖可合并堆等结构。无论实现哪一界，都要把根的入边排除，并在存在平行边时保留原边身份。

参考资料

Yoeng-Jin Chu, Tseng-Hong Liu, On the Shortest Arborescence of a Directed Graph, 1965.
Jack Edmonds, Optimum Branchings, J. Research NBS, 1967.
Robert Tarjan, Finding Optimum Branchings, Networks, 1977.

问题与局部选择 ​

缩环与重赋权 ​

局部贪心失败例子 ​

边界与方向 ​