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

前回のページ

kenkoooo.hatenablog.com

内容は大体かぶってます。

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

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

頂点 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が成り立つ。

証明

h(s)=|V|, h(t)=0 なので、 u \in V-\{s,t\} となる頂点 u について考える。

u から s への単純道  p=< v_0, ..., v_k > にを考える。ここではv_0=u, v_k=sである。pは単純道なのでk< |V|-1である。

h(v_i)\leq h(v_{i+1})+1だから

 h(v_0)=h(v_0) \leq h(v_k)+k \leq h(s)+(|V|-1)=2|V|-1

系 26.21

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

証明

各頂点の高さ関数 h(u) は最大で 2|V|-1回上がる。はい。

補題 26.22

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

証明

u から v への飽和プッシュが発生するとき、h(v)=h(u)-1である。
同様に v から u への飽和プッシュが発生するとき、h(v)=h(u)+1である。
つまり、u から v への飽和プッシュが起こった後、v から u への飽和プッシュが起こるまでに h(v) は少なくとも 2 増加する。
h(v) の最大値は 2|V|-1 なので、u と v の間に起こる飽和プッシュの回数は 2|V| 回未満であり、辺の本数を考えると全体で 2|V||E| 未満である。

補題 26.23

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

証明

ポテンシャル関数\Phiを定義する。


\begin{eqnarray}
\Phi = \sum_{v :e(v)>0} h(v)
\end{eqnarray}

頂点 u の relabel によって \Phi は高々 2|V|-1 だけ増加する。
頂点 u からの飽和プッシュによって \Phi は高々 2|V|-1 だけ増加する。

頂点 u から v への非飽和プッシュを考える。
この操作により e(u)=0 となるので、h(u) は和の対象から外れ、\Phi は正確に h(u) だけ減少する。
v がもともとオーバーフロー頂点だったとき、\Phi の増加量は 0 である。
v が新たにオーバーフロー頂点となる場合、 \Phi は h(v) だけ増加する。
h(u)=h(v)+1 だから、\Phi は少なくとも 1 減少する。

relabel 回数の上界が (2|V|-1)(|V|-2) 回、飽和プッシュ回数の上界が 2|V||E| 回、だから、relabel の上界を 2|V|^2 として、 \Phiの増加量の上界は
 (2|V|)(2|V|^2)+(2|V|)(2|V||E|) = 4|V|^2(|V|+|E|) である。

\Phi は非飽和プッシュによって減少するので、非飽和プッシュ回数の上界は4|V|^2(|V|+|E|)である。

計算量

O(V^2E)