Gomory–Hu 树

割等价树 ​

给定无向容量图 (G=(V,E,c))，容量非负。Gomory–Hu 树是同一顶点集上的带权树公理库树Tree连通且无圈的无向图，等价地任意两点间有唯一简单路径。 (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) 个点对的割值。

父数组构造 ​

固定根 0，把树暂存为 parent 数组。初始令每个 (s>0) 的 parent 都是 0。依次处理 (s=1,\ldots,n-1)，取 (t=\operatorname{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) 父侧的情形，使已有割值留在代表同一分割的树边上。归纳结束后，每个点对路径的最轻父边都对应一个可实现的图割，并与点对最小割值相等。

四点查询例子 ​

考虑无向图本身就是一棵容量树： [ 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。建树后，这三个查询都不再调用最大流。

对一般图可预处理树上的二进制提升表，为每个 (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.