基本定义
割 cut
对于一张带权无向图$G=(V,E)$，定义一个割 (cut)为两个集合$S,T\in V$，满足$S\cap T = \emptyset, S\cup T = V$。定义一条边为割边 (cut edge)当且仅当它的两个端点分别在$S$集合和$T$集合内。定义一个割的容量 (capacity of a cut)为所有的割边的边权的和。
定义$s-t$割 (s-t cut)为满足$s\in S,t\in T$的割。
流 flow
对于一张满足所有的边的容量$c(u,v)$（即$u$到$v$这条边的边权）非负的带权有向图$G=(V,E)$，指定一个源点 (source)和汇点 (sink)，则定义它的一个流网络 (flow network)为一个映射$f:V\times V \to R$，满足以下三个性质：
- $f(u,v)\le c(u,v)$
- $f(u,v)=-f(v,u)$
- 对于任意$u\not= s, u\not = t$，满足$\sum_{x\in V}f(x,u) = \sum_{x\in V} f(u,x)$
最大流问题：找出一个从源点到汇点的可行流，使得该可行流的流量最大。
最大流最小割定理 max-flow min-cut theorem
最大流的流量等于最小割的容量。
符号 & 约定
对于$G=(V,E)$，令$W$为$V$的一个子集，$\delta(W)$表示所有恰好有一个端点在$W$以内的的边构成的集合。
则我们也可以用一个满足$s\in W, t\not\in W$的$\delta (W)$来表示一个$s-t$割。我们用$c(W)$表示这个割的容量。
下文中均用$f(u,v)$表示$u,v$的最大流流量（也是最小割容量）。
一些引理
a)
设对于某一张带权图$G$，用$f(u,v)$表示从$u$到$v$的最大流（也等于最小割），则有：$f(u,v) \ge \min \{ f(u,w),f(v,w) \}$。
b) symmetry
对于任意$W\subseteq V$，有$c(W) = c(\complement_VW)$。
c) submodularity
对于任意的$A\subseteq V, B \subseteq A, v\in V$，有$c(A \cup \{ v\}) - c(A) \ge c(B\cup\{v\}) - c(B)$。
推广：
- 令$X \subseteq \complement_V A$，则有$ c(A\cup X) -c(A) \ge c(B\cup X)-c(B)$。
- 对于任意$A,B\subseteq V$，有$c(A) + c(B) \ge c(A\cup B) + c(A\cap B)$。证明：移项得到$c(A) - c(A\cap B) \ge c(A\cup B)- c(B)$，令$U=A\cap B, V=B,X=A\cap \complement_VB$，套用推广1可以得证。
d) posimodularity
对于任意$A\subseteq V,B\subseteq V$，有$c(A) + c(B) \ge c(A - B) +c(B- A)$，这里的$A-B$定义为$A \cap ( \complement_V B)$。
证明：
e)
令$\delta (W)$为一个$s,t$的最小割，则对于任意$u,v\in W$，存在一个$u,v$最小割$\delta (X)$满足$X\subseteq W$。
证明：
假设$\delta(X)$为一个满足$X,W$有交且不包含的$u,v$最小割。下面不失一般性地只考虑$s\in W,s\in X,u\in X$的情况，因为其它情况都可以通过交换$u,v$或者将$X$变成$\complement_V X$的方式变成$s\in W,s\in X,u\in X$的情况。
情况1：$t\not \in X$。则有$c(W) + c(X) \ge c(W\cup X) + c(W\cap X)$。由于$u\in X,u\in W$而$v\not \in X$，所以$W\cap X$是一个$u,v$割，所以$c(W\cap X) \ge c(X)$。而由于$t\not\in X,t\not \in W$，所以$W\cup X$是一个$s,t$割，所以$c(W\cup X) \ge c(W)$。由此可得$c(W) + c(X) \le c(W\cup X) + c(W\cap X)$，故而$c(W) = c(W\cup X),c(X)=c(W\cap X)$，所以$X\cap W$也是$u,v$的最小割。
情况2：$t\in X$。则有$c(W) + c(X) \ge c(W-X) + c(X-W)$。因为$X-W$是一个$s,t$割，所以$c(X-W) \ge c(W)$；又因为$W-X$是一个$u,v$割，所以$c(W-X) \ge c(X)$。故而得到$c(W-X) = c(X),c(X-W) = c(W)$，所以$W-X$也是$u,v$的最小割。
证毕。
Gomory-Hu Tree
定义
对于任意一张图$G$，它的Gomory-Hu tree是一棵生成树$T$，满足$T$中每条边$(u,v)$，设割掉这条边之后得到的其中一个连通块是$P$，则$(u,v)$的边权为$c(P)$，并且$G$中$(u,v)$的最小割为$\delta(P)$。
构造算法
a)
我们维护$V$的一个划分$\{ S_1,S_2\cdots S_m\}$和一棵以$\{ S_1,S_2\cdots S_m\}$作为点集的生成树$T$，并用$w’(S_i,S_j)$描述$T$中连接$S_i,S_j$的边的边权。我们要使$T$始终满足：对于任意一条边$(S_i,S_j)$，存在$a\in S_i,b\in S_j$满足$f(a,b) = w’(S_i,S_j)$，并且所对应的最小割割开了$T$上由$(S_i,S_j)$分开的两个子树中的点构成的两个点集。
最初，我们令划分为$\{V\}$。
找出一个$|S_i|\ge 2$的集合，从这个集合中任取两个点$x,y$，求出$x,y$的最小割。考虑这个最小割中包含$x$的点集$X$与包含$y$的点集$Y$，将$S_i$划分成$S_i^x = S_i \cap X$和$S_i^y = S_i\cap Y$，然后考虑原来的$T$中与$S_i$相邻的点集$S_j$，如果$S_j \subseteq X$则让$S_j$与$S_i^x$连边，否则若$S_j \subseteq Y$，就让$S_j$与$S_i^y$连边；根据前面的引理e)，一定存在一个最小割使得$S_j$只与$X,Y$中的一个有交；边的边权为原来的$T$中的$w’(S_i,S_j)$。
实现上，求最小割的时候，考虑$T$中删掉了$S_i$之后得到的那些子树，把每个子树缩成一个点，对于某个点$x$与某个子树，$x$与这棵子树缩成的点之间的边权为$x$与这棵子树的所有点之间的边权的和，这样就可以得到一个满足$S_j$只与$X,Y$中的一个有交的最小割。
这样迭代$n-1$次就可以求出Gomory-Hu Tree。
b)
假设现在要求$S$这个点集的Gomory-Hu tree。任意选择两个点$x,y\in S$，求出$x,y$的最小割$\delta(X)$。在$x,y$之间建边权为$c(X)$的边，然后将$S$分为$X$和$\complement_S X$，递归下去求解即可。
性质
考虑$x,y$两个点以及它们在$T$上的路径经过的点$\{p_1,p_2\cdots p_k\}$。
由于引理a)，我们有$f(x,y) \ge \min \{ f(x,p_1),f(p_1,p_2) \cdots f(p_{k-1},p_k),f(p_k,y)\}$，也即是说$f(x,y)$大于等于它们在$T$的路径上的边权最小值。
另一方面，根据定义，$T$上将$T$的点集分成$P$和$\complement_V P$两部分的那条边，其边权等于$c(P)$。所以，$x$到$y$的路径上的每一条边所对应的割都是$x-y$割，所以$x,y$的最小割可以达到$\min\{ f(x,p_1),f(p_1,p_2) \cdots f(p_{k-1},p_k),f(p_k,y)\}$。
故而，$G$中任意两点的最小割等于它们在$T$之间的路径上的边权最小值。