4-1 ネットワーク流
前提知識：HallとKőnig
一本のpathだけでは容量を使い切れない
sourceからsinkへ物資や情報を送りたいとします。各有向arcには一度に通せる容量があります。一つのpathへ可能な限り流すだけでは、早い選択が後の経路を塞ぐことがあります。
matchingで既存の割当をalternating pathに沿って反転したように、flowでも過去の送り方を部分的に取り消す必要があります。その「まだ増やせる向き」と「取り消せる逆向き」を同時に記録するのがresidual networkです。
networkとflow
容量付きネットワーク|capacitated networkとは、有限有向multigraph $D=(V,A)$、相異なるsource $s$ とsink $t$、各arc $a\in A$ の容量
$$
c(a)\in\mathbb R_{\ge0}
$$
からなる。sourceへ入るarcとsinkから出るarcはないものとする。
平行arcと互いに逆向きのarcを許し、arcには固有の名前を付けて区別します。
network上のflowとは、各arcに実数 $f(a)$ を割り当て、次を満たすものである。
- 容量制約：
$$ 0\le f(a)\le c(a)\qquad(a\in A). $$ - 保存則：$v\ne s,t$ に対して
$$ \sum_{\substack{a\in A\\a\text{ enters }v}}f(a) = \sum_{\substack{a\in A\\a\text{ leaves }v}}f(a). $$
この二条件を満たすflowを実行可能フロー|feasible flowという。フロー値|flowの値を
$$ |f|= \sum_{a\text{ leaves }s}f(a) - \sum_{a\text{ enters }s}f(a) $$
と定める。
全頂点で「流出－流入」を足すと各arcが一度ずつ正負に現れて相殺するため、保存則から
$$
|f|=
\sum_{a\text{ enters }t}f(a)
-
\sum_{a\text{ leaves }t}f(a)
$$
も成り立ちます。sourceから正味に出た量とsinkへ正味に入った量は等しいのです。
任意のfeasible flowに対して
$$
|f|\le\sum_{a\text{ leaves }s}c(a).
$$
sourceへ入るflowは非負なので
$$
|f|
=\sum_{a\text{ leaves }s}f(a)-\sum_{a\text{ enters }s}f(a)
\le\sum_{a\text{ leaves }s}f(a)
\le\sum_{a\text{ leaves }s}c(a).
$$
□
従って最大化問題には有限の上界があります。
residual network
各original arc $a:u\to v$ について、現在のflow $f(a)$ からできる二種類の操作を考えます。
- forward residual arc $a^+:u\to v$：さらに $c(a)-f(a)$ だけ増やせる。
- backward residual arc $a^-:v\to u$：既存flowを $f(a)$ だけ取り消せる。
flow $f$ に対する残余ネットワーク|residual network $D_f$ は、各original arc $a:u\to v$ について
$$
c_f(a^+)=c(a)-f(a)>0
$$
ならforward residual arc $a^+$ を置き、
$$
c_f(a^-)=f(a)>0
$$
ならbackward residual arc $a^-$ を置く有向multigraphである。
original networkに $v\to u$ という別arcがある場合、そのforward residual arcと、$u\to v$ のbackward residual arcは同じ向きでも異なる操作です。arc名を区別する理由です。
$D_f$ における $s$ から $t$ への有向path $P$ を $f$-増加路 (フロー)|augmenting pathという。そのボトルネック容量|bottleneck residual capacityを
$$
\Delta(P)=\min_{b\in E(P)}c_f(b)
$$
と定める。
$P$ に沿って $\Delta=\Delta(P)$ だけaugmentするとは、forward residual arc $a^+$ を通るたび $f(a)$ を $\Delta$ 増やし、backward residual arc $a^-$ を通るたび $f(a)$ を $\Delta$ 減らすことです。
augmentationがflowを保つこと
feasible flow $f$ とaugmenting path $P$ に対し、$0<\delta\le\Delta(P)$ だけaugmentして得る $f'$ はfeasible flowであり
$$
|f'|=|f|+\delta
$$
を満たす。
forward arc $a^+$ では
$$
f'(a)=f(a)+\delta\le f(a)+c(a)-f(a)=c(a)
$$
で、非負性も保たれます。backward arc $a^-$ では
$$
f'(a)=f(a)-\delta\ge f(a)-f(a)=0
$$
で、上限も保たれます。従って容量制約が成り立ちます。
pathの内部頂点 $v$ ではresidual pathが一本で入り一本で出ます。forwardかbackwardかにかかわらず、入る操作は $v$ への正味流入を $\delta$ 増やし、出る操作は正味流出を $\delta$ 増やすと解釈できます。両者が相殺するため保存則は保たれます。arcごとに確認しても、original flowの増減が $v$ の流入側と流出側で同量です。
sourceではpathが一本出て戻らず、正味流出が $\delta$ 増えます。sinkでは正味流入が $\delta$ 増えます。従って $|f'|=|f|+\delta$ です。□
backward arcは「物を逆向きに送る」のではなく、以前の選択を取り消す操作です。これによりgreedyな初期選択を後から修正できます。
Ford--Fulkerson算法
- zero flow $f(a)=0$ から始める。
- residual network $D_f$ で $s$--$t$ path $P$ を探す。
- 見つかれば $\Delta(P)$ だけaugmentし、2へ戻る。
- pathがなければ停止して $f$ を出力する。
各反復でflow値は真に増えます。ただし実数容量では、増分が無限に小さくなり停止しない経路選択もあり得ます。整数容量では有限停止を完全に保証できます。
全容量が非負整数なら、Ford--Fulkerson算法はどのaugmenting pathを選んでも有限回で停止し、途中および出力の全arc flowは整数である。反復回数は
$$
\sum_{a\text{ leaves }s}c(a)
$$
以下である。
初期flowは整数です。flowが整数なら各residual capacity
$$
c(a)-f(a)\quad\text{または}\quad f(a)
$$
も整数であり、path上の最小値 $\Delta(P)$ は正整数です。augmentationは各flowへ整数を加減するためintegralityが保たれます。
各反復でflow値は $\Delta(P)\ge1$ 増えます。一方、基本上界によりflow値はsourceから出る容量和を超えません。従って反復回数はその整数上界以下で、有限停止します。□
容量が全て有理数なら共通分母を掛けて整数容量へ変換できるので、やはり有限停止します。無理数容量では有限停止の保証にpath選択規則が必要です。BFSで最短arc数のaugmenting pathを選ぶEdmonds--Karp算法は、実容量でも有限回で停止します。その $O(|V||A|^2)$ 証明は「最大流最小切断定理」の定理後の発展へ置きます。
具体計算――backward arcで選択を直す
頂点 $s,a,b,t$ とarc
$$
s\to a,\quad s\to b,\quad a\to b,\quad a\to t,\quad b\to t
$$
を考え、容量を順に
$$
1,\ 1,\ 1,\ 1,\ 1
$$
とします。
最初にpath $s\to a\to b\to t$ へ1流すと、この三arcが飽和します。このままoriginal arcだけを見ると、残る $s\to b$ から先の $b\to t$ は飽和し、増やせません。
しかしresidual networkには $a\to b$ のbackward arc $b\to a$ があります。path
$$
s\to b\to a\to t
$$
をresidualにたどり1 augmentすると、
- $s\to b$ と $a\to t$ を1増やす。
- $a\to b$ を1減らす。
結果は
$$ s\to a\to t,\qquad s\to b\to t $$
へ各1流す値2のflowです。過去の一本を取り消すことで二本へ組み替えました。
flow decomposition
flowはarcごとの数値表ですが、その正の部分をsource--sink pathとdirected cycleの流れに分解できます。
有限network上のfeasible flow $f$ は、有限個の $s$--$t$ 有向path flowと有向cycle flowの和に分解できる。path flowの係数の総和は $|f|$ である。
正のflowをもつarcだけからなる有向部分グラフを考えます。$|f|>0$ ならsourceから正のflow arcをたどり始められます。内部頂点へ正のflowで入ったなら保存則により正のflowで出るarcもあります。
有限性から、たどり続けるとsinkへ到達するか、既出頂点を再訪します。sinkへ到達した場合は $s$--$t$ walkを得ます。途中のdirected cycleを削れば $s$--$t$ pathになります。再訪した場合はdirected cycleを得ます。
得たpathまたはcycle上のflow最小値 $\delta>0$ を全arcから引きます。容量制約と保存則を保ち、少なくとも一本の正flow arcが0になります。pathを引いた場合はflow値が $\delta$ 減り、cycleを引いた場合はflow値が変わりません。
path成分を引き終えてflow値が0になった後にも正flow arcが残る場合、そのarcから向きに沿ってたどります。sinkへの正味流入はflow値0に等しく、sinkから出るarcはないので、sinkへ入る正flow arcは残っていません。sourceへ入るarcもありません。従って有限性により内部頂点を再訪し、directed cycleを得ます。これを同じ方法で引きます。
正flow arc数が毎回少なくとも一つ減るので有限回でzero flowになります。引いたpath・cycleと係数を逆に足せば元の $f$ です。pathを引いたときだけ値がその係数だけ減り、最後は0なのでpath係数総和は元の $|f|$ です。□
cycle flowはsourceからsinkへ運ぶ正味量へ寄与しません。最大値だけが目的ならcycle成分を除いたflowを選べます。
matchingをflowとして表す
二部グラフ $G=(X\sqcup Y,E)$ からnetworkを作ります。
- source $s$ から各 $x\in X$ へ容量1のarc。
- 各辺 $xy\in E$ を $x\to y$ の容量1 arc。
- 各 $y\in Y$ からsink $t$ へ容量1のarc。
上のnetworkで、整数値 $k$ のintegral flowが存在することと、$G$ に大きさ $k$ のmatchingが存在することは同値である。
matching $M$ があれば、各 $xy\in M$ に対するpath
$$
s\to x\to y\to t
$$
へ1ずつ流します。matching辺は端点を共有しないため、$s\to x$ と $y\to t$ の容量1を超えず、内部保存則も成り立ちます。flow値は $|M|=k$ です。
逆に値 $k$ のintegral flowを取ります。容量は全て1なので各arc flowは0または1です。正のcycle flowを除いても値を変えずintegralです。残るflowをpathへ分解すると、各正flow pathは
$$
s\to x\to y\to t
$$
の形です。容量1により同じ $x$ または $y$ を二pathが共有できません。従ってflow 1の中間arc $x\to y$ を集めるとmatchingになり、その本数はflow値 $k$ です。□
この対応で、matchingのalternating pathはflow networkのresidual augmenting pathになります。「増加路」の反転はFord--Fulkersonの容量1版です。
演習
arc $s\to a,s\to b,a\to b,a\to t,b\to t$ の容量をそれぞれ $3,2,1,2,3$ とする。flow値を順に $2,1,1,1,2$ と割り当てたものがfeasibleか判定し、値を求めよ。
全arcでflowは0以上かつ容量以下です。頂点 $a$ には2入り、$a\to b$ と $a\to t$ へ1ずつ、合計2出るので保存されます。頂点 $b$ には $s$ から1、$a$ から1の合計2が入り、$t$ へ2出るので保存されます。
sourceからの正味流出は $2+1=3$、sinkへの流入も $1+2=3$ なのでfeasibleで値3です。□
前問のflowについて、各original arcのforward・backward residual capacityを書け。
順に
$$
\begin{array}{c|ccccc}
a&s a&s b&a b&a t&b t\\ \hline
c(a)-f(a)&1&1&0&1&1\\
f(a)&2&1&1&1&2
\end{array}
$$
です。forward capacity 0の $a\to b$ はresidual networkに現れません。他のforward arcは表の第一行の正値をもち、各backward arcは第二行の値をもちます。□
前問のresidual networkでpath
$$
s\to b\to a\to t
$$
を考える。中央はoriginal arc $a\to b$ のbackward arcである。bottleneckを求め、最大量augmentした新flowを書け。
residual capacitiesは $s\to b$ が1、$b\to a$ が $f(a\to b)=1$、$a\to t$ が1なのでbottleneckは1です。
augment後は $s\to b$ と $a\to t$ が1ずつ増え、$a\to b$ が1減ります。arc順の新flowは
$$
(2,2,0,2,2).
$$
値は3から4へ増え、$a$ では流入2・流出2、$b$ では流入2・流出2です。□
sourceから出るarc容量が4,3,2であるnetworkに値9のfeasible flowが見つかった。このflowがmaximumであることを、本章の基本上界だけで示せ。
任意のflow値はsourceから出る容量和
$$
4+3+2=9
$$
以下です。値9のfeasible flowがこの上界を達成しているため、それより大きいflowは存在せずmaximumです。これは特別な場合の最適性証明書です。□
arc $s\to a,a\to t,s\to b,b\to t,a\to b,b\to a$ にflowを順に $2,2,1,1,1,1$ 流す。feasibleであることを確認し、path flowとcycle flowへ分解せよ。
$a$ には $s$ から2、$b$ から1入り、$t$ へ2、$b$ へ1出ます。$b$ には $s$ から1、$a$ から1入り、$t$ へ1、$a$ へ1出るので保存則が成立します。値は3です。
これは
$$
2(s\to a\to t)+1(s\to b\to t)
$$
というpath flowと
$$
1(a\to b\to a)
$$
というcycle flowの和です。path係数和は $2+1=3$ でflow値に一致します。□
二部グラフ
$$
N(x_1)=\{y_1,y_2\},\quad
N(x_2)=\{y_2\},\quad
N(x_3)=\{y_2,y_3\}
$$
を容量1 networkへ変換し、値3のintegral flowを一つ書け。
sourceから各 $x_i$、各 $x_i$ から表示された $y_j$、各 $y_j$ からsinkへ容量1 arcを置きます。
matching
$$
\{x_1y_1,x_2y_2,x_3y_3\}
$$
に対応して三path
$$
s\to x_1\to y_1\to t,\quad
s\to x_2\to y_2\to t,\quad
s\to x_3\to y_3\to t
$$
へ各1流せば値3です。各容量1 arcを高々一回しか使いません。□
本章で得たもの
residual networkは、未使用容量を進むforward操作と、以前のflowを取り消すbackward操作を同時に記録します。augmenting pathに沿う更新は容量制約・保存則を保ち、flow値をbottleneckだけ増やします。整数容量ではFord--Fulkersonが有限停止しintegral flowを返します。
しかし本章では、residual pathがなくなったflowが必ずmaximumだとはまだ証明していません。これがmax-flow min-cut定理です。
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
