问题
求一个任意的无向图的全局最小割。即，定义$\lambda(x,y)$表示$x,y$两点之间的最小割，给出一张任意的无向图，你需要求出$\min_{x\neq y}\lambda(x,y)$。
Stoer-Wagner 算法
约定
用$w(x,y)$表示$x,y$之间的边权。用$c(X,Y)$表示$\sum_{x\in X,y\in Y} w(x,y)$，其中$X,Y$是图中点集的两个子集。
定义contract(x,y)表示将$x,y$两个点缩起来，具体来说就是新建一个点$u$，对于任意$v\neq x,v\neq y$，令$w(u,v) = w(v,x) + w(v,y)$，然后将$x,y$从原图中删去。
算法过程
如果两个点在全局最小割的异侧，那么它们之间的最小割就是全局最小割；否则，将它们缩起来对全局最小割没有影响。
Stoer-Wagner算法的过程是：每一次求出两个点的最小割，然后把它们缩起来。整个算法过程中求出过的最小割的最小值就是全局最小割。
但是这样还是要求$n-1$次最小割。
优化：MinimumCutPhase
我们并不是需要求某两个点之间的最小割，只要我们求出的是某两个点之间的最小割就可以了。
MinimumCutPhase可以在$O(n^2)$的时间内求出某两个点之间的最小割，以下是它的过程：
- 首先随便选择一个点$a$，令$A=\{a\}$。
- 然后选择一个点不在$A$中的点$x$，使得$c(A,\{x\})$最大，然后将$x$加入$A$。
- 重复2.直到$A$以外只剩下一个点。则我们最后加入$A$的那个点和剩下的那个点（设为$z$）之间的最小割就是$c(A,\{z\})$。
正确性：实际上可以证明，假设加入$A$的点依次为$v_1=a,v_2\cdots v_{n-1}$，令最后剩下的那个点为$v_n$，那么对于任意的$i\ge 2$，在只考虑$v_1,v_2\cdots v_i$以及它们之间的边的时候，$v_i$和$v_{i-1}$之间的最小割是$c(\{v_1,v_2,\cdots v_{i-1}\},\{v_i\})$。
由于$v_i,v_{i-1}$的任意一个割都会删掉$(v_i,v_{i-1})$这条边，所以$\lambda(v_i,v_{i-1})$等于将$(v_i,v_{i-1})$删掉之后求得的最小割$\lambda’(v_i,v_{i-1})$加上$w(v_i,v_{i-1})$。所以接下来只考虑将$(v_i,v_{i-1})$删掉后的图。
首先证明在只考虑$v_1,v_2,\cdots v_i$以及它们之间的边的时候，$c(\{v_1,v_2,\cdots v_{i-1}\},\{v_i\})\le \lambda(v_{i-1},v_{i-2})$。用归纳法。对于$i=2$显然成立。对于$i>2$：
- 将$v_i$以及与$v_i$相邻的所有边从图中删掉，此时$v_{i-1}$和$v_{i-2}$的最小割是$(\{v_1,v_2,\cdots v_{i-2}\},\{v_{i-1}\})$（归纳假设）。
- 由MinimumCutPhase的过程可以知道
- 由于$v_i$和$v_{i-1}$之间没有边，所以
- 将上面的两个式子带入(1)，可以得到
- 由于$c(\{v_1,v_2,\cdots v_{i-2},v_i \},\{v_{i-1}\})$等于加入$v_i$这个点之前图中的$v_{i-1},v_{i-2}$的最小割，并且在加入$v_i$之后两个点的最小割不可能变得比加入之前更小，所以$c(\{v_1,v_2,\cdots v_{i-2},v_i \},\{v_{i-1}\})=\lambda(v_{i-1},v_{i-2})$。所以我们得到了
然后我们将证明，只考虑$v_1,v_2,\cdots v_i$以及它们之间的边的时候，$c(\{v_1,v_2,\cdots v_{i-1}\},\{v_i\})\le \lambda(v_{i},v_{i-2})$。用归纳法。对于$i=2$显然成立。对于$i>2$：
- 删去$v_{i-1}$以及原图中与它相邻的边。对得到的图重新进行MinimumCutPhase，最后加入$A$的点是$v_{i-2}$，剩下的点是$v_i$。
- 此时$v_i,v_{i-2}$之间的最小割是$c(\{v_1,v_2,\cdots v_{i-2}\},\{v_i\})$。
- 把$v_{i-1}$加回去之后的图中，得到$\lambda(v_i,v_{i-2}) = c(\{v_1,v_2,\cdots v_{i-2},v_{i-1},v_i\})$。
综合以上两个结论：
以及
以及
可以得到