Stoer-Wagner算法cut-of-the-phase部分证明
Stoer-Wagner 算法求无向图上的全局最小割。
任取两点s，t，考虑这个无向图上的最小割，有下面两种情况：
1. s，t在割的同一侧 2.
s，t在割的两侧
对于第二种情况，普通的s-t最小割就是这个全局最小割。对于第一种情况，已知s，t
在割的同一侧，把他们看成一个点对结果没有影响，于是把s，t两个点缩成一个点，再任取两点，重复这个过程，直到图中只有一个点。
cut-of-the-phase
求任意两点的s-t割如果使用网络流速度有些慢。 cut-of-the-phase
可以求出某两点之间的s-t最小割。既然Stoer-Wagner中的s，t是任取的，
自然可以选择cut-of-the-phase能求出最小割的那两点。
{: width=“500” }
图中 most tightly connected vertex 指的是 (if there is no edge e(v,u), d(v,u)=0)， cut-of-the-phase指的是最后加入的点与倒数第二个加入的点的s-t割就是
下面最后加入的点是，倒数第二个加入的是。令, (if there is no edge e(x,y), d(x,y)=0)，
要证明与之间的最小割是这样的：
而不是这样的：
表示之前加入的所有点的集合,为上图中的第二种情况（任意一个不是第一种情况的割,t在Y中）。下面用归纳法证明
对于n=1,2，
假设n=k时满足，n=k+1，最后加入的点是.
由于加入晚于，有
带入，
显然有