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

Posted on February 15, 2022
Tags:

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

任取两点 ss, tt, 考虑这个无向图上的最小割， 有下面两种情况：
  1. ss, tt 在割的同一侧
  2. ss, tt 在割的两侧

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

1 cut-of-the-phase

求任意两点的 s-t 割如果使用网络流速度有些慢。 cut-of-the-phase 可以求出某两点之间的 s-t 最小割。既然 Stoer-Wagner 中的 ss , tt 是任取的， 自然可以选择 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 指的是argmaxv∑u∈Ad(v,u)\underset{v}{\operatorname{arg max}} \sum_{u\in A} d(v,u) (if there is no edge e(v,u), d(v,u)=0), cut-of-the-phase 指的是最后加入AA的点tt与倒数第二个加入AA的点ss的 s-t 割就是∑u∈Ad(t,u)\sum_{u\in A} d(t,u)

下面最后加入AA的点是 tt, 倒数第二个加入的是ss。令X,Y⊂VX,Y\subset V,w(X,Y)=∑x∈X∑y∈Yd(x,y)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),

要证明ss与tt之间的最小割是这样的：
fig1

而不是这样的：
fig2

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

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

假设 n=k 时满足w(t,At)≤w(X,Y)w(t,A_t)\leq w(X,Y), n=k+1, 最后加入AA的点是t′t'.

w(t′,At′)=w(t′,t)+w(t′,At)w(t',A_{t'})=w(t',t)+w(t',A_t)

由于t′t'加入AA晚于tt, 有

w(t′,At)≤w(t,At)w(t',A_t)\leq w(t,A_t)

带入， w(t′,At′)=w(t′,t)+w(t′,At)≤w(t′,t)+w(t,At)≤w(t′,t)+w(X,Y)w(t',A_{t'})=w(t',t)+w(t',A_t)\leq w(t',t)+w(t,A_t) \leq w(t',t)+w(X,Y)

得到

w(t′,t)+w(X,Y)+w(t′,Y)=w(X′,Y′) w(t',t)+w(X,Y)+w(t',Y)=w(X',Y')

w(t′,At′)≤w(X′,Y′)w(t',A_{t'})\leq w(X',Y')