本文是在作者阅读多篇博客后糅合而成的，部分内容有雷同。
最小割树又称 Gomory-Hu 树，由 Ralph Edward Gomory 和 Te Chiang Hu 于 1961 年发表的论文中共同提出。最小割树可以在 \(n − 1\) 次最大流中构建，并通过树上 RMQ 求任意两点之间的最小割。
板子题：
P4897 【模板】最小割树（Gomory-Hu Tree）
1.构造
定义 \(cut(u,v)\) 为无向图中 \(u,v\) 之间的最小割大小。
最小割树最开始初始化为 \(n\) 个不相连的点。先任意选取两个节点 \(u,v\), 求出它们的最小割 \(cut(u,v)\), 跑最大流时,满流的边就对应最小割中割掉的边。通过这组割, 可以把图划分成两个部分, \(u\) 所在的点集记作 \(U\), \(v\) 所在的点集记作 \(V\)。在最小割树上连接 \(u,v\), 边权为 \(cut(u, v)\)。点集 \(U,V\) 分别构成 \(u,v\) 树上的子树，递归处理 \(U,V\)，最终得到的树形结构就是就是最小割树。
2.性质
最小割树满足一个很强的性质：两点之间的最小割 等于 在最小割树上两点间路径中边的最小权。
下面是简单证明。
-
定理1 任选 \(u,v\) 跑一次最小割,将图分成了 \(S,T\) 两个集合。
则 \((x\in S,y\in T)\Longrightarrow cut(x,y)\leq cut(u,v)\)
证明 : 割断 \(u,v\) 的割显然也分隔了 \(S,T\) , 所以 \(cut(u,v)\) 是上界。 -
定理2 任取三点 \(a,b,c\) 则 \(cut(a,b),cut(a,c),cut(b,c)\) 中最小值至少出现两次。
证明 : 不妨假设 \(cut(a,b)\) 是最小的,先割开,再讨论 \(c\) 在 \(S,T\) 的那个集合内。
不妨设其在 \(S\) 内,由 {定理1} 得到 \(cut(b,c)\leq cut(a,b)\) 。
而由 \(cut(a,b)\) 最小的假设则得到 \(cut(b,c)=cut(a,b)\) ,出现两次。 -
推论1 : \(cut(a,b)\geq \min\{cut(a,c),cut(b,c)\}\)
证明 : 若 \(cut(a,b)\) 不是最小值,显然成立,若 \(cut(a,b)\) 是最小值,则一定会出现两次,也会出现在 \(\min\) 中。 -
推论2 对于两点 \((u,v)\) ,有 \(cut(u,v)\geq\min\{cut(u,w_1),cut(w_1,w_2)...,cut(w_m,v)\}\)
证明 : 首先由由 {定理2} 得到 \(cut(u,v)\geq\min\{cut(u,w_1),cut(w_1,v)\}\)。
对 \(cut(w_1,v)\)，我们重复上述操作得到 \(cut(w_1,v)\geq\min\{cut(w_1,w_2),cut(w_2,v)\}\)，结合两个集合的 min, 得到：
重复任意次即可得到 {推论2}。
- 定理3(最小割树定理) 如上所述。设 \(u,v\) 为欲求的两个点, \(u,v\) 在最小割树的路径构成一个边集 \((w_1,w_2),(w_2,y_3)...(w_{m-1},w_m)\), 其中 \(w_1=u,w_m=v\)。
证明 : 首先, 不难得到 \(u,v\) 在 \(x_i,y_i\) 最小割的两侧。由 {定理1} , \(cut(u,v)\leq cut(w_i,w_{i+1})\)。
然后根据 {定理2.2} 又能得到 \(cut(u,v)\geq\min\{cut(w_1,w_2),cut(w_2,w_3)...,cut(w_{m-1},w_m)\}\) 。
也就是\(\min\{cut(w_1,w_2),cut(w_2,w_3)...,cut(w_{m-1},w_m)\}\leq cut(u,v)\leq\min\{cut(w_1,w_2),cut(w_2,w_3)...,cut(w_{m-1},w_m)\}\)
这就得到了 \(cut(u,v)=\min\{cut(w_1,w_2),cut(w_2,w_3)...,cut(w_{m-1},w_m)\}\) 。
标签：...,geq,cut,割树,min,Tree,最小,Hu From： https://www.cnblogs.com/xm-blog/p/18336955