ネットワークフロー(network flow)とは、弧に容量の付いた有向グラフの上で、各頂点での出入りの釣り合いと各弧の容量制約を守りながら入口 $s$ から出口 $t$ へ物を流す方法と、その流量の最大値を調べる理論である。中心にあるのは、最大流の流量が最小カットの容量に等しいという最大流最小カット定理で、容量が整数なら整数値の最大流がある。フローは $s$ から $t$ への有向道と有向閉路に分解でき、ここから互いに交わらない道の最大本数を切断の最小の大きさで表す Menger の定理が導かれる。最短の増加道を選ぶ方法は、容量が実数でも頂点数と弧数の積以下の回数で最大流に到達する。
ネットワークフロー(network flow)とは、各辺に容量(通せる量の上限)の付いた有向グラフの上で、入口から出口へ物を流す方法とその最大量を調べる理論である。水道管や通信網、輸送路の上の流れを抽象化したもので、各頂点で「入る量と出る量が等しい」ことと各辺で「容量を超えない」ことだけを要求する。中心にあるのは、流せる量の最大値(最大流)が、網を入口側と出口側に切り分けるときに切られる辺の容量の和の最小値(最小カット)に等しいという最大流最小カット定理である。
この記事では、ネットワークとフローの言葉を整えて最大流と最小カットの等式を述べ(thm-nf-maxflow-mincut。証明は 最大流最小カット定理 で行う)、整数性定理(thm-nf-integrality)と、フローが入口から出口への道と閉路に分解されること(thm-nf-decomposition)を証明する。この分解からは、互いに交わらない道の最大本数を切断の最小の大きさで表す Menger の定理が導かれる(Mengerの定理)。また、増加道として最短のものを選べば、容量が整数でなくても有限回で最大流に到達する(Edmonds–Karp法)。
この記事の有向グラフは、有限集合 $V$ を頂点集合、有限集合 $A$ を弧(有向辺)の集合とし、各弧 $a$ に始点と終点(相異なる 2 頂点)を与えたものである。同じ始点と終点をもつ弧が複数あってもよい。頂点の集合 $S\subset V$ について、始点が $S$ に、終点が $V\setminus S$ にある弧の集合を $\delta^+(S)$、始点が $V\setminus S$ に、終点が $S$ にある弧の集合を $\delta^-(S)$ と書き、$\delta^{\pm}(v):=\delta^{\pm}(\{v\})$ とする。写像 $g\colon A\to\mathbb{R}$ と $B\subset A$ に対し $g(B):=\sum_{a\in B}g(a)$ と書く。
ネットワーク $N=(V,A,s,t,c)$ とは、上の有向グラフ $(V,A)$、相異なる 2 頂点 $s$(入口、source)と $t$(出口、sink)、および容量 $c\colon A\to\mathbb{R}_{\ge0}$ の組である。
この定義は 組合せ最適化 の記事の定義「ネットワーク・フロー・カット」と同じである。すべての頂点 $v$ について $f(\delta^+(v))-f(\delta^-(v))$ を足すと、各弧が始点で $+$、終点で $-$ と 1 回ずつ数えられて $0$ になる。保存則により $s,t$ 以外の頂点の項は $0$ なので、$t$ では $f(\delta^-(t))-f(\delta^+(t))=\operatorname{val}(f)$ であり、流量は「出口に正味で流れ込む量」でもある。
流れを増やす余地を見るには、次のネットワークを使う。
フロー $f$ に対し、各弧 $a$(始点 $u$、終点 $w$)から、次の 2 種類の残余弧を作る。
$R_f$ の $s$ から $t$ への有向道を $f$ の増加道(augmenting path)という。
以下の証明では、弧の列で表した道と閉路を使う。有向グラフ $(V,A)$ の $s$–$t$ 有向道とは、相異なる頂点 $s=v_0,v_1,\dots,v_k=t$ と、$v_{i-1}$ から $v_i$ への弧 $a_i$ の列 $(a_1,\dots,a_k)$ のことであり、有向閉路とは、相異なる頂点 $v_0,\dots,v_{k-1}$($k\ge2$)と、$v_{i-1}$ から $v_i$ への弧 $a_i$($v_k:=v_0$)の列 $(a_1,\dots,a_k)$ のことである。どちらでも弧 $a_1,\dots,a_k$ は相異なる。道や閉路 $P$ に対し、$P$ の弧で $1$、それ以外の弧で $0$ をとる写像を $\chi_P\colon A\to\mathbb{R}$ と書く。
最大流の流量を上から抑えるのは、次の等式と不等式である。
任意のフロー $f$ と任意のカット $S$ について
$$
\operatorname{val}(f)=f(\delta^+(S))-f(\delta^-(S))\le c(S)
$$
が成り立つ。
$S$ の各頂点で「出る量 − 入る量」を足すと、$S$ の内部の弧が打ち消し合うことから分かる(最大流最小カット定理 の補題「フローとカット」)。
流量を増やす手がかりは増加道である。
$P$ を $f$ の増加道とし、$\varepsilon>0$ を $P$ の残余弧の残余容量の最小値とする。$P$ が $a^+$ を含む弧 $a$ では $f'(a):=f(a)+\varepsilon$、$a^-$ を含む弧では $f'(a):=f(a)-\varepsilon$、それ以外の弧では $f'(a):=f(a)$ と定めると、$f'$ はフローで $\operatorname{val}(f')=\operatorname{val}(f)+\varepsilon$ である。
増加道の内側の頂点では、前後 2 本の残余弧による変化が打ち消し合うので保存則が保たれる(最大流最小カット定理 の補題「増加道に沿った更新」)。
ネットワーク $N$ には最大流が存在する。フロー $f$ について、次の 3 条件は同値である。
(a) $f$ は最大流である。
(b) $f$ の増加道($R_f$ の $s$ から $t$ への有向道)は存在しない。
(c) $\operatorname{val}(f)=c(S)$ となるカット $S$ が存在する。
特に、最大流の流量は最小カットの容量に等しい。
証明は 最大流最小カット定理 にある(ネットワークの規約は同じで、条件 (a)(b)(c) の番号も同じである)。要点は、増加道がないとき、$R_f$ で $s$ から到達できる頂点全体 $S$ がカットになり、$\delta^+(S)$ の弧は満杯、$\delta^-(S)$ の弧の値は $0$ なので、lem-nf-weak-duality の等式から $\operatorname{val}(f)=c(S)$ となることである。
容量がすべて整数のネットワークでは、零フローから始めて、増加道があるかぎり lem-nf-augment の改善を繰り返すと、高々 $c(\delta^+(s))$ 回で止まり、止まったときのフローはすべての弧で整数値をとる最大流である。特に、整数値の最大流が存在する。
$f$ が整数値のフローなら、残余容量 $c(a)-f(a)$、$f(a)$ はすべて整数なので、増加道の $\varepsilon$ は正の整数、すなわち $1$ 以上であり、改善後の $f'$ も整数値である。零フローは整数値なので、手順中のフローはすべて整数値で、流量は 1 回ごとに $1$ 以上増える。一方、カット $\{s\}$ に lem-nf-weak-duality を使うと、流量はつねに $c(\delta^+(s))$ 以下である。零フローの流量は $0$ なので、改善は高々 $c(\delta^+(s))$ 回で、その後は増加道がない。thm-nf-maxflow-mincut の (b) ⇒ (a) により、止まったときのフローは最大流である。$\square$
最大流最小カット定理は Ford と Fulkerson による(BM76 Theorem 11.3、p. 198。同書は増加道を探すラベル付けの方法も同じ 2 人によるものとして紹介している)。最大流と、それと同じ容量のカットを並べて示せば、他のフローを 1 つも調べずに最適性が確かめられる。最大流の存在は、コンパクト性を使わずに、Edmonds–Karp法 の定理「増加の回数の上界」からも従う。容量が整数でないと、整数値の最大流があるとは限らない(弧 $s\to t$ が 1 本で容量 $\frac12$ なら最大流の流量は $\frac12$ である)。
フローは「各交差点で出入りが釣り合い、各道路で上限を守る交通」である。入口から出口へ流せる量は、どこかの「くびれ」で決まる。網を入口側 $S$ と出口側に分けると、入口から出口へ行く流れはどこかで $S$ の外へ出る弧を通るので、流量はそれらの弧の容量の和を超えない。最大流最小カット定理は、最も細いくびれでちょうど等号が成り立つことを主張する。
流れを道の束として見ることもできる。保存則を満たす流れは、入口から出口へ向かう何本かの道と、どこにも出入りしない渦(閉路)を重ねたものに分解できる(thm-nf-decomposition)。容量がすべて $1$ なら、整数値の最大流は互いに弧を共有しない道の束になり、最大流最小カット定理は「交わらない道の本数」と「道をすべて断つのに必要な弧の本数」が等しいという組合せ論の定理に化ける。これが Menger の定理である(Mengerの定理)。
頂点 $s,a,b,t$ と弧 $s\to a$(容量 $2$)、$s\to b$($1$)、$a\to b$($1$)、$a\to t$($1$)、$b\to t$($2$)のネットワークで、道 $s\to a\to t$ に $1$ だけ流したフロー $f$ を考える(他の弧では $0$)。流量は $1$ である。$R_f$ の残余弧は、$s\to a$(残余容量 $1$)、$a\to s$($1$)、$s\to b$($1$)、$a\to b$($1$)、$t\to a$($1$)、$b\to t$($2$)である。$a\to t$ は満杯なので順方向の残余弧はない。$R_f$ には $s\to a\to b\to t$ と $s\to b\to t$ の有向道があり、それぞれで $1$ ずつ流量を増やせる。両方を行うと $f(s\to a)=2$、$f(s\to b)=1$、$f(a\to b)=1$、$f(a\to t)=1$、$f(b\to t)=2$ の流量 $3$ のフローになる。カット $\{s\}$ の容量は $2+1=3$ なので、これは最大流であり、$\{s\}$ は最小カットである。
頂点 $s,a,b,t$ と弧 $s\to a$、$a\to b$、$b\to a$、$a\to t$(容量はすべて $2$)のネットワークで、$f(s\to a)=1$、$f(a\to b)=1$、$f(b\to a)=1$、$f(a\to t)=1$ はフローである($a$ に入る量 $1+1$ と出る量 $1+1$、$b$ に入る量 $1$ と出る量 $1$ が等しい)。これは $s$–$t$ 有向道 $(s\to a,\ a\to t)$ と有向閉路 $(a\to b,\ b\to a)$ に $1$ ずつ流したものの和であり、流量 $1$ は道の部分だけから来る。閉路の部分は流量を変えないので、取り除いても流量 $1$ のフローのままである。
すべての頂点で保存則が成り立つ写像 $g\colon A\to\mathbb{R}_{\ge0}$(入口・出口を特別扱いしない)を循環(circulation)という。
$g$ を有向グラフ $(V,A)$ 上の循環とし、$g(a)>0$ となる弧の個数を $r$ とする。このとき、有向閉路 $C_1,\dots,C_q$($q\le r$)と正の実数 $\mu_1,\dots,\mu_q$ で
$$
g=\sum_{j=1}^{q}\mu_j\chi_{C_j}
$$
となるものが存在する。$g$ が整数値なら $\mu_j$ はすべて整数にとれる。
$r$ に関する帰納法で示す。$r=0$ なら $g=0$ で、$q=0$ とすればよい。$r\ge1$ とし、$g(a_1)>0$ となる弧 $a_1$ をとり、その始点を $w_0$、終点を $w_1$ とする。$w_i$ が $g(a_i)>0$ となる弧 $a_i$ の終点として得られたとき、$w_i$ に入る量 $g(\delta^-(w_i))$ は正であり、保存則により出る量 $g(\delta^+(w_i))$ も正なので、$g(a_{i+1})>0$ となる $w_i$ から出る弧 $a_{i+1}$ がとれる。その終点を $w_{i+1}$ とする。$V$ は有限なので、$w_j=w_i$ となる $i< j$ が現れる。最初に現れるそのような $j$ をとると、$w_i,\dots,w_{j-1}$ は相異なり、$C:=(a_{i+1},\dots,a_j)$ は有向閉路である(弧はループでないので $j-i\ge2$)。
$\mu:=\min\{g(a)\mid a\in C\}>0$ とし、$g':=g-\mu\chi_C$ とおく。$\mu$ の選び方から $g'\ge0$ である。$C$ の各頂点には $C$ の弧がちょうど 1 本入り 1 本出るので、$\chi_C$ はすべての頂点で保存則を満たし、$g'$ も循環である。$g'(a)>0$ となる弧の個数は、最小値をとる弧で $g'=0$ となるので $r-1$ 以下である。帰納法の仮定を $g'$ に用いれば $g$ の分解が得られる。$g$ が整数値なら $\mu$ は整数で、$g'$ も整数値である。$\square$
$f$ をネットワーク $N=(V,A,s,t,c)$ のフローとし、$\operatorname{val}(f)\ge0$ とする。このとき、$s$–$t$ 有向道 $P_1,\dots,P_p$、有向閉路 $C_1,\dots,C_q$($p+q\le|A|+1$)と正の実数 $\lambda_i,\mu_j$ で
$$
f=\sum_{i=1}^{p}\lambda_i\chi_{P_i}+\sum_{j=1}^{q}\mu_j\chi_{C_j},\qquad \sum_{i=1}^{p}\lambda_i=\operatorname{val}(f)
$$
となるものが存在する。$f$ が整数値なら、$\lambda_i,\mu_j$ はすべて整数にとれる。
$t$ から $s$ への新しい弧 $a^*$ を加えた有向グラフ $(V,A\cup\{a^*\})$ を考え、$g:=f$($A$ の上)、$g(a^*):=\operatorname{val}(f)$ と定める。$g\ge0$ である。$s,t$ 以外の頂点では $f$ の保存則がそのまま成り立つ。$s$ では出る量と入る量の差が $\operatorname{val}(f)-g(a^*)=0$ である。$t$ では、定義の後で見たように $f(\delta^-(t))-f(\delta^+(t))=\operatorname{val}(f)$ なので、出る量 $f(\delta^+(t))+g(a^*)$ と入る量 $f(\delta^-(t))$ が等しい。よって $g$ は循環である。
lem-nf-circulation により $g=\sum_j\mu_j\chi_{C_j}$($C_j$ は $(V,A\cup\{a^*\})$ の有向閉路、個数は $|A|+1$ 以下)と書ける。有向閉路の弧は相異なるので、各 $C_j$ は $a^*$ を高々 1 回含む。$a^*$ を含む閉路は、$a^*$ の終点 $s$ から始めて並べ直すと「$s$ から $t$ への有向道に $a^*$ を付けたもの」なので、$a^*$ を除いた部分は $N$ の $s$–$t$ 有向道である。これらを $P_i$、その係数を $\lambda_i$ とする。$a^*$ を含まない閉路は $(V,A)$ の有向閉路である。$A$ の上で $g=f$ なので求める等式が得られ、$a^*$ での値を比べると $\sum_i\lambda_i=g(a^*)=\operatorname{val}(f)$ である。整数性は lem-nf-circulation から従う。$\square$
分解に現れる閉路の部分 $\sum_j\mu_j\chi_{C_j}$ を取り除いても、容量制約と保存則は保たれ、流量は変わらない。また、最大流 $f$ に、すべての弧で正の値をとる有向閉路 $C$ があれば、$C$ の弧の値の最小値 $\mu$ を引いた $f-\mu\chi_C$ も同じ流量のフローで($\chi_C$ はすべての頂点で保存則を満たす)、正の値をとる弧の個数が減る。これを高々 $|A|$ 回繰り返せば、すべての弧で正の値をとる有向閉路をもたない最大流が得られる。
容量がすべて $1$ のネットワークで整数値の最大流を thm-nf-decomposition で道に分解すると、互いに弧を共有しない $s$–$t$ 有向道の最大本数が、取り除くと $s$–$t$ 有向道がなくなる弧の集合の最小の大きさに等しいことが分かる。これが Menger の定理の弧版で、頂点版・辺版や、$k$-連結性を道の本数で言い換える Whitney の定理とあわせて Mengerの定理 で扱う。
零フローから増加道に沿って流量を増やす方法は、容量が整数なら有限回で止まる(thm-nf-integrality)が、増加道の選び方が悪いと回数は頂点と弧の個数で抑えられず、容量に無理数があると止まらないこともある。増加道として弧の本数が最小のものを選べば、容量が実数でも $|V|\,|A|$ 回以下で止まり、最大流に到達する(Edmonds–Karp法)。
最大流最小カット定理と Menger の定理は、多くの組合せ論の最小最大定理の源である。
| 外す条件・替える条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-nf-decomposition の $\operatorname{val}(f)\ge0$ | 弧 $t\to s$ 1 本(容量 $1$)で $f=1$ | $s$–$t$ 有向道と有向閉路の正の係数の和に書けない |
1 行目:$s$ から出る弧がないので $\operatorname{val}(f)=0-1=-1$ である。$s$–$t$ 有向道は存在せず、有向閉路もないので、正の係数の和として書けるのは $0$ だけであり、$f\neq0$ と矛盾する。証明では $g(a^*)=\operatorname{val}(f)\ge0$ を使っている。
Menger の定理(1927 年、Mengerの定理)はそれより前の結果で、BM76 §11.4(p. 203)はこれを最大流最小カット定理の応用として導いている。容量の代わりに弧ごとに下限も課す問題(BM76 Exercise 11.3.4、p. 203)や、流す費用を最小にする問題も、同じ残余ネットワークの考え方で扱われる。
最大流を求める問題は、弧の値を変数とし、容量制約と保存則を制約とする線形計画問題の特別な場合である(KT17 §13.6、pp. 273–274)。一般の線形計画問題は、係数と定数が整数でも整数の最適解をもつとは限らない(同所)。ネットワークでは容量が整数なら整数値の最大流がある(thm-nf-integrality)ことが、Menger の定理や二部グラフのマッチングへの応用を支えている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する