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

先週のページ

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

先週のまとめ

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

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

  1. fはGの最大フローである。
  2. 残余ネットワーク Gf は増加可能経路を含まない。
  3. 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


Edmonds-Karp アルゴリズム

補題26.7

証明

定理26.8

証明

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}

e(x)>0, x \in Uかつ、s以外のすべての頂点が非負の過剰を持ち、s\not\in Uだから、\sum_{u\in U}e(u)>0である。

したがって

\begin{eqnarray}
 \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v) > 0
\end{eqnarray}

フローは非負だから

\begin{eqnarray}
 \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u) > 0
\end{eqnarray}

よってf(v',u')>0となる u' \in U, v' \in \overline{U} が存在する。
よって残余ネットワークG_fには残余辺(u',v')が存在する。

よって道 x\leadsto u' \to v' が存在する。これは v' \in U となり矛盾。

補題 26.20

Generic-Push-Relabel 実行中はすべての頂点 u で  h(u) \leq 2|V| -1が成り立つ。

系 26.21

relabel の回数は頂点当たり高々2|V|-1回である。

補題 26.22

飽和プッシュ回数は2|V||E|回である。

補題 26.23

非飽和プッシュ回数は4|V|^2(|V|+|E|)回である。

次回予告

Push-Relabel の解析

フロント移動

練習問題

おまけ

実装落ちてた。
github.com