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

フローネットワーク

各辺 $(u, v) \in E$ が、容量 $c(u,v) \geqq 0$ を持つ有向グラフである。入り口 s と出口 t が設定されている。

非負の値を取る量 $f(u,v)$ を頂点 u から頂点 v へのフローと呼ぶ。

フローは以下の 2 条件を満たす。

容量制限: 全ての $u,v \in V$ に対して、 $0 \leqq f(u,v) \leqq c(u,v)$ でなければならない。
フロー保存則: 全てのに対して、でなければならない。
- 頂点 u に入ってくるフローと、頂点 u から出ていくフローの量が等しい。

最大フロー問題は s から t への最大の値を持つフローを求める問題である。

逆平行辺

f:id:kenkoooo:20161021042256j:plain

逆平行辺を持つネットワークは簡単に逆平行辺を持たないグラフに構成し直すことが出来るので、議論を簡明にするため逆平行辺を禁止することにする。

複数の入口と出口

f:id:kenkoooo:20161021041928j:plain

複数の入口があっても超入口を作ってそこから各入口に容量無限の辺を張れば、入口 1 つのネットワークとして扱える。出口についても同様。

練習問題

1-1.

フローネットワーク G の辺 (u, v) を分割し、新しい頂点 x を導入して (u, x) と (x, v) に置き換え、c(u, x) = c(x, v) = c(u, v) と定義した G' を考える。G' の最大フローが G の最大フローと同じ値を持つことを示せ。

$f(u, x) = f(x, v)=f(u,v)$ であるため、G の最大フローの値 $|f| = \sum_{v \in V} f(s, v) -\sum_{v \in V}f(v, s)$ は辺を分割しても変わらないため。

1-2.

複数の入口や出口を持つフローネットワークの任意のフローは、超入口や超出口を追加して出来る単一の入口や出口を持つネットワークと同一であることを示せ。

超入口から張られる辺の容量は無限なので、流したいだけ流すことが出来る。そのため、超入口を与える前のグラフに比べて辺のフローは影響を受けない。

1-3.

$s \rightsquigarrow u \rightsquigarrow t$ となる道が存在しないような頂点 u が存在するとき、全ての頂点 $v \in V$ について $f(u,v)=f(v,u)=0$ を満たす最大フロー f が存在することを示せ。

1-5.

最大フロー問題を線形計画問題として記述せよ。

$\begin{eqnarray} maximize & \sum_{(s, u) \in E} f(s, u) -\sum_{(u, s)\in E}f(u, s) \\ subject\ to & \sum_{(v, u) \in E} f(v, u) = \sum_{(u, v)\in E}f(u, v) & (u \in V-\{s, t\}) \\ & f(u, v) \leqq c(u, v) & ((u, v) \in E) \\ & f(u, v) \geqq 0 & ((u, v) \in E) \end{eqnarray}$

Ford-Fulkerson 法

Ford-Fulkerson-Method(G, s, t)
    フロー f を 0 に初期化する
    while 増加可能経路 p が残余ネットワークに Gf に存在する
        フロー f を p に沿って増やす
    return f

残余ネットワーク

辺 (u, v) に追加でどのくらいフローを流すことが出来るかを残余容量 $c_f(u, v)=c(u,v)-f(u,v)$ で表す。

$(v,u) \in E$ にフローが f(v, u) 流れているとき、フローを削減できることを表現するため、 $c_f(u,v)=f(v,u)$ と表せる。

これをまとめると、
$c_f(u,v) = \begin{cases} c(u,v)-f(u,v) & (u,v) \in E \\ f(v,u) & (v,u) \in E \\ 0 & それ以外 \end{cases}$

増加

f(u,v) 流れているフローを変化させることを考える。f を G におけるフロー、f' を残余容量からなる残余ネットワーク $G_f$ のフローとすると、変化後のフローは以下のように表される。

$(f \uparrow f')(u,v) = \begin{cases} f(u,v) + f'(u,v) - f'(v,u) & (u,v) \in E \\ 0 & それ以外 \end{cases}$

補題 26.1

$|f \uparrow f'| = |f|+|f'|$ を示せ

まず、容量制限を満たすことを示す。
$\begin{eqnarray} (f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\ &\geqq& f(u,v)+f'(u,v)-f(u,v) \\ &=& f'(u,v) \\ &\geqq& 0 \end{eqnarray}$

$\begin{eqnarray} (f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\ &\leqq& f(u,v)+f'(u,v) \\ &\leqq& f(u,v)+c_f(u,v) \\ &=& f(u,v) +c(u,v) -f(u,v) \\ &=& c(u,v) \end{eqnarray}$

http://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf

全ての $u\in V$ について以下の式が成り立つことを示す。
$\sum_{v \in V}(f\uparrow f')(u,v)- \sum_{v \in V}(f\uparrow f')(v,u) = \sum_{v \in V}f(u,v)-\sum_{v \in V}f(v,u)+\sum_{v \in V}f'(u,v)-\sum_{v \in V}f'(v,u)$

u から出る辺のもう一方の端点の集合を $V_1(u) = \{ v:(u,v) \in E \}$ と表す。
また、u へ向かう辺のもう一方の端点の集合を $V_2(u) = \{ v:(v,u) \in E \}$ と表す。

G には逆平行辺を含まれないので、 $V_1(u) \cap V_2(u)=\emptyset$

$\begin{cases} (f \uparrow f')(u,v)>0 & v \in V_1(u) \\ (f \uparrow f')(v,u)>0 & v \in V_2(u) \end{cases}$

$\begin{eqnarray} \sum_{v \in V}(f\uparrow f')(u,v)&-& \sum_{v \in V}(f\uparrow f')(v,u)\\ &=& \sum_{v \in V_1(u)}(f\uparrow f')(u,v)- \sum_{v \in V_2(u)}(f\uparrow f')(v,u) \\ &=& \sum_{v \in V_1(u)}(f(u,v)+f'(u,v)-f'(v,u))- \sum_{v \in V_2(u)}(f(v,u)+f'(v,u)-f'(u,v)) \\ &=& \sum_{v \in V_1(u)}f(u, v) - \sum_{v \in V_2(u)}f(v, u) + \sum_{v \in V_1(u)}f'(u, v) + \sum_{v \in V_2(u)}f'(u, v) - \sum_{v \in V_1(u)}f'(v,u) - \sum_{v \in V_2(u)}f'(v, u) \\ &=& \sum_{v \in V_1(u)}f(u, v) - \sum_{v \in V_2(u)}f(v, u) + \sum_{v \in V_1(u) \cup V_2(u)}f'(u, v) - \sum_{v \in V_1(u) \cup V_2(u)}f'(v,u) \end{eqnarray}$

$\begin{eqnarray} |f \uparrow f'| &=& \sum_{v \in V}(f \uparrow f')(s,v) -\sum_{v \in V}(f \uparrow f')(v,s) \\ &=& \sum_{v \in V}f(s,v)- \sum_{v \in V}f(v, s) + \sum_{v \in V}f'(s,v)- \sum_{v \in V}f'(v, s) \\ &=& |f|+|f'| \end{eqnarray}$

増加可能経路

残余ネットワーク $G_f$ 上での s から t への経路。

増加可能経路 p の各辺に沿って増やすことの出来るフローの最大値を p の残余容量とし、以下のように定義する。
$c_f(p) =min\{c_f(u,v): (u, v) は p 上にある \}$

補題 26.2

関数 $f_p$ を以下のように定義する。

$f_p(u, v)= \begin{cases} c_f(p) & (u,v) が p 上にあるとき \\ 0 & それ以外 \end{cases}$

このとき、 $f_p$ は $G_f$ のフローで $|f_p|=c_f(p) > 0$ である。

$| f \uparrow f_p| =|f|+|f_p| > |f|$ より、 $f_p$ を $f$ に加えると、より最大値に近い f を得られる。

フローネットワークのカット

V を $s \in S$ と $t \in T$ を満たす S と T=V-S に分割する。これをカット (S, T) とする。

カット(S,T) と交差する純フローを
$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)$
と定義する。

カットの容量は $c(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v)$ である。

最小カットは、カット(S, T)の中で、容量が最小のカットである。

補題 26.4

カット(S, T)と交差する純フローは f(S, T)=|f| である。

証明

$\begin{eqnarray} | f | &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s)\\ &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} }\big( \sum_{v\in V}f(u,v)- \sum_{v\in V}f(v,u) \big)\\ &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} } \sum_{v\in V}f(u,v)- \sum_{u \in S-\{s\} }\sum_{v\in V}f(v,u) \\ &=& \sum_{v \in V} \big( f(s,v) +\sum_{u \in S-\{s\} } f(u,v)\big) - \sum_{v \in V} \big( f(v,s) +\sum_{u \in S-\{s\} } f(v,u)\big) \\ &=& \sum_{v \in V} \sum_{u\in S}f(u, v)- \sum_{v \in V} \sum_{u\in S}f(v, u) \\ &=& \sum_{v \in S} \sum_{u\in S}f(u, v) + \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u) - \sum_{v \in T} \sum_{u\in S}f(v, u) & (V=S \cup T かつ S \cap T = \emptyset だから)\\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u) +\big( \sum_{v \in S} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u) \big) \\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u) \\ &=& f(S,T) \end{eqnarray}$

系 26.5

G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。

証明

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

定理 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)

つづく

続きは来週やります。