Stoer-Wagner算法cut-of-the-phase部分证明

Stoer-Wagner 算法求无向图上的全局最小割。

任取两点 $s$, $t$, 考虑这个无向图上的最小割, 有下面两种情况：

1. $s$, $t$ 在割的同一侧
2. $s$, $t$ 在割的两侧

对于第二种情况, 普通的s-t最小割就是这个全局最小割。对于第一种情况, 已知 $s$, $t$ 在割的同一侧, 把他们看成一个点对结果没有影响, 于是把 $s$ , $t$ 两个点缩成一个点, 再任取两点, 重复这个过程, 直到图中只有一个点。

1 cut-of-the-phase

求任意两点的s-t割如果使用网络流速度有些慢。 cut-of-the-phase 可以求出某两点之间的s-t最小割。既然Stoer-Wagner中的 $s$ , $t$ 是任取的, 自然可以选择cut-of-the-phase能求出最小割的那两点。

Min Cut Phase(G,w,a)
A <- {a}
while(A!=V)
    add A the most tightly connected vertex
store cut of the phase
shrink G by merging the two vertices added last

图中 most tightly connected vertex 指的是$\underset{v}{\mathrm{argmax}}{\sum }_{u\in A}d(v,u)$ (if there is no edge e(v,u), d(v,u)=0), cut-of-the-phase指的是最后加入$A$的点$t$与倒数第二个加入$A$的点$s$的s-t割就是${\sum }_{u\in A}d(t,u)$

下面最后加入$A$的点是 $t$, 倒数第二个加入的是$s$。令$X,Y\subset V$,$w(X,Y)={\sum }_{x\in X}{\sum }_{y\in Y}d(x,y)$ (if there is no edge e(x,y), d(x,y)=0),

要证明$s$与$t$之间的最小割是这样的：

而不是这样的：

$A_t$表示$t$之前加入$A$的所有点的集合,$X,Y$为上图中的第二种情况（任意一个不是第一种情况的割,t在Y中）。下面用归纳法证明$w(t,A_t)\le w(X,Y)$

对于n=1,2, $w(t,A_t)=w(X,Y)$

假设n=k时满足$w(t,A_t)\le w(X,Y)$, n=k+1, 最后加入$A$的点是$t^{\prime }$.

$$w(t^{\prime },A_{t^{\prime }})=w(t^{\prime },t)+w(t^{\prime },A_t)$$

由于$t^{\prime }$加入$A$晚于$t$, 有

$w(t^{\prime },A_t)\le w(t,A_t)$

带入, $w(t^{\prime },A_{t^{\prime }})=w(t^{\prime },t)+w(t^{\prime },A_t)\le w(t^{\prime },t)+w(t,A_t)\le w(t^{\prime },t)+w(X,Y)$

得到

$$w(t^{\prime },t)+w(X,Y)+w(t^{\prime },Y)=w(X^{\prime },Y^{\prime })$$

$$w(t^{\prime },A_{t^{\prime }})\le w(X^{\prime },Y^{\prime })$$