Gomory–Hu 树 | Codeboy's Blog

形式陈述

割等价树

给定至少一个顶点的有限无向容量图 $G=(V,E,c)$ ，容量取有限非负实数。平行边可按端点对合并容量，自环不影响割并可删除。Gomory–Hu 树是同一顶点集上的带权树 $T$ ，满足对任意不同的 $u,v\in V$ ，

\lambda_G(u,v) =\min_{e\in P_T(u,v)}w_T(e),

其中 $P_T(u,v)$ 是树上唯一路径， $\lambda_G(u,v)$ 是图中的最小 $u$ - $v$ 割值。

进一步，若路径最轻边为 $e$ ，删掉 $e$ 后树的两个连通分量给出原图中一个值为 $w_T(e)$ 的 $u$ - $v$ 割。这棵树用 $n-1$ 条带权边压缩了 $\binom n2$ 个不同点对的割值。单顶点输入返回单顶点树，没有非平凡点对查询；空图不在该树表示接口内。

父数组构造

下面给出 Gusfield 的不收缩原图版本。编号为 $0,\ldots,n-1$ ，固定根 $0$ ，初始 $p[v]=0$ （ $v>0$ ），以 $f[v]$ 保存父边权。依次处理 $s=1,\ldots,n-1$ ，令 $t=p[s]$ 。把原无向边变成容量相同的两个反向有向弧，调用最大流；由残量可达侧得到一个最小 $s$ – $t$ 割 $S$ ，使 $s\in S,t\notin S$ ，并记其值为 $q$ 。

父数组更新如下；同一行中的赋值按所列次序执行， $a$ 暂存旋转前的父节点。

text

for v in {1,...,n-1} excluding s:
    if p[v] == t and v in S:
        p[v] = s
        # 若 f[v] 已确定，仍保留这个权值

if t != 0 and p[t] in S:
    a = p[t]
    p[s] = a
    p[t] = s
    f[s] = f[t]
    f[t] = q
else:
    f[s] = q

这里重新挂接的是所有满足条件的兄弟，包括已处理顶点。若只更新尚未处理者，可能仍得到编码点对数值的树，却丢失“删一条树边就得到原图最小割”的更强性质。旋转分支也必须同步搬移边权，不能只改父指针。

算法共调用 $n-1$ 次最大流，每次都在原容量图上求割。父树是正在构造的输出表示，不是要求后续流计算永久收缩的输入图。对不连通输入，分量间割值为零，相应零权树边仍可把所有原顶点组织成一棵输出树。

从父边证书到所有点对

Gusfield 的构造定理保证：终结时，每条父边 $e=xy$ 的删除分区是原图的一个最小 $x$ – $y$ 割，其容量为 $w_T(e)$ 。证明使用无向非负割的解交叉性质与上述完整挂接、旋转规则；旧边的最终删除分区可以随更新改变，不能把它始终等同于最早一次流计算返回的原始割侧。

有了这个逐边证书，全部点对结论可以直接推出。固定不同的 $u,v$ ，记树路径最小边权为 $a$ 。删掉达到 $a$ 的树边，其分区分开 $u,v$ ，故 $\lambda_G(u,v)\le a$ 。反过来，任意原图 $u$ – $v$ 割都会切开树路径上的某条边 $xy$ ；它也是一个 $x$ – $y$ 割，所以容量至少为 $\lambda_G(x,y)=w_T(xy)\ge a$ 。对全部 $u$ – $v$ 割取最小，即得 $\lambda_G(u,v)\ge a$ 。两界相合，同时得到割值和可输出分区。

直觉

无向最小割具有可 uncross 的层叠结构，使所有点对的数值不必各存一份。构造逐次把新割嵌进父树；查询时，一条树路径上的最轻边就是限制两端连通的最窄瓶颈，删掉它还直接给出原图中的一个相应割侧。

Gomory–Hu 树上两点路径的最轻边给出点对最小割值 — 路径最轻边编码点对最小割

例子与边界

四点查询例子

考虑无向图本身就是一棵容量树：

a\xleftrightarrow{3}b,\qquad b\xleftrightarrow{2}c,\qquad b\xleftrightarrow{5}d.

它的 Gomory–Hu 树可以就是这棵树。查询 $\lambda(c,d)$ 时，路径 $c-b-d$ 的边权为 2 与 5，答案为 2；删去边 $bc$ 给出割 $\{c\}\mid\{a,b,d\}$ 。

查询 $\lambda(a,d)$ 时，路径 $a-b-d$ 的最轻边为 3，答案为 3。查询 $\lambda(b,d)$ 只有一条权 5 的边，答案为 5。建树后，这三个查询都不再调用最大流。

为什么已经处理的兄弟也要改挂

取只有两条单位边 $0-2$ 、 $2-1$ 的三点路径。初始父树是以 $0$ 为中心的星形。处理 $s=1$ 时，可返回最小割侧 $S=\{1\}$ ，值为一，因此记录父边 $1-0$ 、权一。处理 $s=2,t=0$ 时，最小源侧为 $\{1,2\}$ ，值仍为一。

顶点 $1$ 虽已处理，却满足 $p[1]=0$ 且 $1\in S$ ，必须改挂到 $2$ ，保留权一。这样输出就是原路径，删掉 $2-0$ 得到容量一的割 $\{1,2\}\mid\{0\}$ 。若跳过已处理的 $1$ ，输出仍是单位星形 $0-1,0-2$ ；它的所有点对路径最小值确实都是一，但删掉 $0-2$ 得到的 $\{2\}$ 割在原图中容量为二，违反割树的分区承诺。

查询所用的树表示

可用二进制提升，为每个 $2^j$ 祖先同时保存路径最小边及其身份，以 $O(n\log(n+1))$ 预处理支持 $O(\log(n+1))$ 割值查询。保存边身份还能指出应删除哪条树边；有多个同权最轻边时任选其一。

若需要常数时间数值查询，可以再建一棵合并树：按割树边权从大到小处理，用并查集合并两端分量，每次创建一个以当前权为标签的父节点，连接两棵分量合并树。原顶点作为叶子。两叶首次相遇时，原路径上最轻边刚被处理，所以它们在合并树中的最近公共祖先标签正是点对割值。排序加构造需 $O(n\log(n+1))$ ，再配合静态常数时间 LCA 结构即可得到 $O(1)$ 查询；这项增强使用的是新的合并树，不是只在原割树上调用普通 LCA。

推论与应用

树编码了什么

树边权精确编码所有点对最小割值，并且每条树边的删除分量给出一个相应最小割。但它不枚举原图中所有不同的最小割边集：同一点对可能有多个等值割，树只选择其中一个层叠族来表示。

因此“查询值”和“列出原图割边”是两个接口。前者取路径最小权即可；后者先由树边得到顶点分区，再扫描原图找跨分区边，输出成本至少与所报告边数相关。

适用边界与复杂度

经典定理要求无向容量图。对有向图，点对割不对称，一棵无向树的路径最小边无法同时表达两个方向。负容量也不属于最大流最小割定理的标准输入。

总构造成本是 $n-1$ 次最大流，加上 $O(n^2)$ 的父数组与显式割侧更新；还须计入原图读取及所选流算法的初始化。实际时间取决于底层最大流算法与图规模；不能把“只有 $n-1$ 次”误写成近线性时间。树只保存 $O(n)$ 边，但若每次显式复制整张图，也会产生不必要的工程开销。

当 $n\ge2$ 时，若只需要一个全局最小割，取 Gomory–Hu 树的最轻边可以得到答案，但专用算法通常更直接。它的价值在于一次预处理后回答大量不同点对，而不是替代所有单次最大流。

参考资料

Ralph E. Gomory and T. C. Hu, Multi-Terminal Network Flows, Journal of the Society for Industrial and Applied Mathematics, 1961.
Dan Gusfield, Very Simple Methods for All Pairs Network Flow Analysis, SIAM Journal on Computing 19(1), 1990，pp. 143–155：区分数值等价树与带割分区证书的割树。
NetworkX，Gomory–Hu 的 Gusfield 实现，2026年10月查阅：全部适用兄弟的重新挂接、旧权保留与旋转。
Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.

形式陈述 ​

割等价树 ​

父数组构造 ​

从父边证书到所有点对 ​

四点查询例子 ​

为什么已经处理的兄弟也要改挂 ​

查询所用的树表示 ​

树编码了什么 ​

适用边界与复杂度 ​

反向链接