RCO アルゴリズムイントロダクション輪読会 26. 最大フロー 2

先週のページ

kenkoooo.hatenablog.com
少し被りがあります。

先週のまとめ

$|f \uparrow f'| = |f|+|f'|$
G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。

定理 26.6 最大フロー最小カットの定理

fはGの最大フローである。
残余ネットワーク Gf は増加可能経路を含まない。
Gのあるカット(S,T)に対して|f|=c(S,T) である。

証明

最大フローであるにも関わらず増加可能経路を持つと仮定すると、 $f_p$ が定まり、|f| より値が大きいGのフローが得られるので矛盾する。

Gf が増加可能経路を持たないとき、Gfにはsからtへの道が存在しない。

$S=\{ v \in V: G_f に s から v への道が存在する \}, T=V-S$ と定義する。

明らかに $s\in S$ であり、 $G_f$ にはsからtへの道が存在しないので $t\not\in S$ である。よって、この分割(S,T)はカットである。

$u\in S$ かつ $v\in T$ かつ $(u,v) \in E$ であるようなu, v を考える。
$f(u,v)\not= c(u,v)$ ならば $(u,v)\in E_f$ であり、 $v\in S$ となり矛盾する。よって $f(u,v)= c(u,v)$ である。

$f(v,u)\not=0$ ならば $c_f(u,v)=f(v,u)$ で $(u,v)\in E_f$ だから $v\in S$ となり矛盾する。よって $f(v,u)=0$

$\begin{eqnarray} f(S,T) &=& \sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u) \\ &=& \sum_{u\in S}\sum_{v\in T}c(u,v)-\sum_{u\in S}\sum_{v\in T}0 \\ &=&c(S,T) \end{eqnarray}$

全てのカット(S, T) に対して $|f| \leqq c(S,T)$ である。よって $|f| = c(S,T)$ はfが最大フローであるための十分条件である。

Ford-Fulkersonのアルゴリズム

Ford-Fulkerson(G, s, t)
    for (u, v) in G.E
        (u, v).f = 0
    while 残余ネットワーク G_f に s から t への道 p が存在する
        c_f(p) = min([c_f(u, v) for (u, v) in p])
        for (u, v) in p
            if (u, v) in G.E
                (u, v).f = (u, v).f + c_f(p)
            else
                (v, u).f = (v, u).f - c_f(p)

基本 Ford-Fulkerson の解析

増加可能経路を見つけるための DFS が O(E)
最大フローが f* とすると、ループは最悪で |f*| 回走る。
よって O(E|f*|)

余談

高速な最大フローのアルゴリズムは $O(V^3)$ で動作するが、最大フローの値が十分小さければ Ford-Fulkerson の方が速くなることがある。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day3&pid=F

2 部グラフの最大マッチング問題

プッシュ再ラベルアルゴリズム

今までは頂点にフローを溜め込むことができない条件のみを考えてきた。

頂点 u に流入するフローと頂点 u から流出するフローの合計が等しかった。
$\begin{eqnarray} \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) = 0 \end{eqnarray}$

これを緩和して、流入量が流出量を超えることが出来るものとする。
$\begin{eqnarray} \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) \geq 0 \end{eqnarray}$

このような条件でのフローをプリフローと呼ぶ。

この過剰量を e(u) とする。

$u\in V-\{s\}$ について、
$\begin{eqnarray} e(u) = \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \end{eqnarray}$

$e(u)>0$ となるような頂点 $u \in V-\{s,t\}$ をオーバーフロー頂点と呼ぶ。

高さ関数

$h(s)=|V|, h(t)=0$ であり、残余辺 $(u,v)\in E_f$ について、 $h(u)\leq h(v)+1$ が成り立つような高さ関数 h を考える。

プッシュ操作

以下の条件を満たす残余辺 (u, v) について、u から v にフローをプッシュする。
$\begin{eqnarray} \begin{cases} h(u)=h(v)+1 \\ c_f(u,v)>0 \\ e(u) > 0 \end{cases} \end{eqnarray}$

Push(u, v)
    # 適用条件: u がオーバーフロー頂点で、c_f(u, v) > 0 かつ h(u) = h(v) + 1
    df = min(e(u), c_f(u, v))
    if (u, v) in E
        (u, v).f = (u, v).f + df
    else
        (v, u).f = (v, u).f - df
e(u) -= df
e(v) += df

プッシュ後に $c_f(u,v)=0$ となるようなプッシュを飽和プッシュと呼ぶ。

再ラベル操作

$e(u)>0$ かつ $(u,v) \in E_f$ の全ての v について $h(u) \leq h(v)$ であるとき、u の高さを上げる。

Relabel(u)
    # 適用条件: u がオーバーフロー頂点、かつ、h(u) <= h(v)
    h(u) = 1 + min([h(v) for (u, v) in E_f])

基礎アルゴリズム

Initialize-Preflow(G, s)
    for v in V
        h(v) = 0
        e(v) = 0
    for (u, v) in E
        (u, v).f = 0
    h(s) = |V|
    for v in G[s]
        (s, v).f = c(s, v)
        e(v) = c(s,v)
        e(s) -= c(s, v)

これによって s から出る全ての辺に容量上限までフローを流す。
つまり、s から出る辺は残余グラフに含まれなくなる。
よって全ての残余辺 $(u,v) \in E_f$ について $h(u) \leq h(v)+1$ が成り立つ。
（全ての $u \in V-\{s\}$ について $h(u)=0$ だから）

Generic-Push-Relabel(G)
    Initialize-Preflow(G, s)
    while 適用可能な push か relabel がある
        適用可能な push か relabel を選び、実行する

Push-Relabel の正当性

アルゴリズムが停止したときプリフロー f が最大フローであることと、アルゴリズムが停止することを示す。

補題 26.14

u がオーバーフロー頂点であれば、push か relabel が実行可能である。

証明

u から push が実行可能でない場合、全ての残余辺 $(u, v) \in E_f$ について、 $h(u) < h(v)+1$ である。
このとき、 $h(u) \leq h(v)$ であり、relabel が実行可能である。

補題26.15

Generic-Push-Relabel の実行中、h(u) は減少しない。

証明

h(u) は relabel 以外では変化せず、relabel では適用のたびに必ず 1 以上増える。

補題26.16

Generic-Push-Relabel は h を高さ関数として維持する。

証明

初期状態では h が高さ関数制約を満たしている。

u から出る辺 (u, v) を考える。
Relabel(u) を行った後は $h(u) \leq h(v)+1$ が保証される。

u に入る辺 (w, u) を考える。
Relabel(u) の前に $h(w) \leq h(u) +1$ が成立していたならば、操作後は $h(w) < h(u) +1$ が成立する。

よって Relabel(u) は高さ制約を維持する。

Push(u, v) を実行することを考える。

Push(u, v) によって $f(v, u)$ が減少するとき、 $c_f(v,u)$ が増加する。
これは $E_f$ に (v, u) が加わると考えられる。
このとき $h(u)=h(v)+1$ だから $h(v)=h(u)-1< h(u)+1$ である。
新しい残余辺 (v, u) について $h(v) \leq h(u)+1$ が成り立つ。

Push(u, v) によって $c_f(u,v)$ が減少するとき、 $E_f$ から (u, v) が取り除かれると考える。
このときは、制約が取り除かれるので、再び h は高さ関数である。

補題26.17

f をプリフローとする。このとき残余グラフ $G_f$ には s から t への道はない。

証明

矛盾を導くために $G_f$ における s から t への道 $p = < v_0,v_1,...,v_k >$ が存在すると仮定する。
$v_0=s, v_k=t$ である。
一般性を失うことなく $k<|V|$ と仮定する。

$i=0,1,...,k-1$ に対して $(v_i,v_{i+1}) \in E_f$ である。
$i=0,1,...,k-1$ に対して $h(v_i)\leq h(v_{i+1}) +1$ である。
よって $h(s)\leq h(t)+k$ である。
ここで $h(t)+k=0+k=k$ だから $h(s)\leq k <|V|$ となり、高さ関数制約 $h(s)=|V|$ に矛盾する。

補題26.18

Generic-Push-Relabel を実行して停止したとき、プリフロー f は最大フローである。

証明

Initialize-Preflow 実行後の f はプリフローである。

while ループ内では push と relabel が実行される。
relabel は f に影響しない。
push 実行前に f がプリフローならば、実行後も f はプリフローである。

補題 26.14 より、停止したときは $V-\{s,t\}$ にオーバーフロー頂点は存在しない。
よって $v \in V-\{s,t\}$ について e(v)=0 である。
よって、プリフロー f はフローである。

補題 26.17 より、残余ネットワーク $G_f$ には s から t への道が存在しない。
よってフロー f は最大フローである。

Push-Relabel の解析

補題 26.19

f をプリフローとする。この時、残余ネットワーク $G_f$ の任意のオーバーフロー頂点 u から s への単純道が存在する。

証明

オーバーフロー頂点 x について、 $U=\{v: G_f において xからvへの単純道がある\}$ とする。
s が U に含まれることを示す。

矛盾を導くために $s \not\in U$ を仮定する。
$\overline{U}=V-U$ とする。

$\begin{eqnarray} e(u) = \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \end{eqnarray}$
より、
$\begin{eqnarray} \sum_{u\in U}e(u) &=& \sum_{u\in U}\big( \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \big) \\ &=& \sum_{u\in U}\big( \big( \sum_{v \in U} f(v,u) + \sum_{v \in \overline{U}} f(v,u) \big) - \big( \sum_{v \in U} f(u,v) + \sum_{v \in \overline{U}} f(u,v) \big) \big) \\ &=& \sum_{u\in U}\sum_{v \in U}f(v,u)+ \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)-\sum_{u\in U}\sum_{v \in U}f(u,v)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\ &=& \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\ \end{eqnarray}$