Gomory–Hu 树

形式陈述 ​

割等价树 ​

给定无向容量图 $G=(V,E,c)$，容量非负。Gomory–Hu 树是同一顶点集上的带权树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。 $T$，满足对任意 $u,v\in V$，

$${\lambda }_G(u,v)=\underset{e\in P_T(u,v)}{min}{w}_T(e),$$

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

进一步，若路径最轻边为 $e$，删掉 $e$ 后树的两个连通分量给出原图中一个值为 $w_T(e)$ 的 $u$-$v$ 割。这棵树用 $n-1$ 条带权边压缩了 $(\genfrac{}{}{0ex}{}{n}{2})$ 个点对的割值。

父数组构造 ​

固定根 0，把树暂存为 parent 数组。初始令每个 $s>0$ 的 parent 都是 0。依次处理 $s=1,\dots ,n-1$，取 $t=\mathrm{parent}[s]$，在原容量图上计算一次 $s$-$t$ 最大流公理库最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。，由残量网络中从 $s$ 可达的顶点得到最小割侧 $S$。

把尚未处理且原本以 $t$ 为父、同时落在 $S$ 内的顶点改挂到 $s$ 下。这样，刚得到的割只改变跨越它的父边，不会破坏此前已编码的割关系。

若 $t$ 的父节点也落在 $S$，还要旋转父关系：让 $s$ 接到 $t$ 原父节点之下，再让 $t$ 成为 $s$ 的孩子，并把旧父边权与本次流值移动到对应的新边。否则直接把边 $(s,t)$ 的权设为本次最小割值。

这一“旋转并搬移权值”的分支是构造的一部分，不是实现优化。省略它会在割侧穿过祖父节点时生成错误的父树。算法总共调用 $n-1$ 次最大流；每次都在原无向容量图上求割，parent 数组更新不等于永久收缩或删除原图顶点。

为什么父关系更新有效 ​

每条已定父边携带一个曾经计算出的割值，其删除分量对应当时的割侧。新 $s$-$t$ 割可能把若干尚未处理的兄弟与 $s$ 放在一起，于是这些兄弟改挂到 $s$ 才能让父边继续跨过正确的割。

最小割的 uncrossing 性质保证可以选择与既有父割层叠相容的割侧。旋转处理新割包住 $t$ 父侧的情形，使已有割值留在代表同一分割的树边上。归纳结束后，每个点对路径的最轻父边都对应一个可实现的图割，并与点对最小割值相等。

直觉

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

例子与边界

四点查询例子 ​

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

$$a\stackrel{3}{\leftrightarrow }b,b\stackrel{2}{\leftrightarrow }c,b\stackrel{5}{\leftrightarrow }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。建树后，这三个查询都不再调用最大流。

对一般图可预处理树上的二进制提升表，为每个 $2^j$ 祖先保存路径最小边，从而在 $O(\log n)$ 时间回答割值；只需数值时也可用 LCA/RMQ 结构进一步优化。

推论与应用

树编码了什么 ​

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

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

适用边界与复杂度 ​

经典定理要求无向容量图。对有向图，点对割不对称，一棵无向树的路径最小边无法同时表达两个方向。负容量也不属于最大流最小割定理公理库最大流最小割定理Max-flow min-cut theorem网络最大流值等于源汇最小割容量。的标准输入。

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

若只需要一个全局最小割，取 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, 1990.
• Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.