ネットワークフロー

同義語：network flowネットワーク流

概要

前提知識: 有向グラフ, 道(グラフ), 組合せ最適化

ネットワークフロー（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}$ の組である。

写像 $f\colon A\to\mathbb{R}$ がフロー（flow）であるとは、すべての弧 $a$ で $0\le f(a)\le c(a)$（容量制約）、$s,t$ 以外のすべての頂点 $v$ で $f(\delta^-(v))=f(\delta^+(v))$（保存則）が成り立つことをいう。$\operatorname{val}(f):=f(\delta^+(s))-f(\delta^-(s))$ を $f$ の流量（value）といい、流量が最大のフローを最大流という。
$s\in S$、$t\notin S$ となる $S\subset V$ をカット（cut）といい、$c(S):=c(\delta^+(S))$ をその容量という。容量が最小のカットを最小カットという。

この定義は組合せ最適化の記事の定義「ネットワーク・フロー・カット」と同じである。すべての頂点 $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 種類の残余弧を作る。

$f(a)< c(a)$ のとき、$u$ から $w$ への順方向の残余弧 $a^+$。その残余容量を $c(a)-f(a)$ とする。
$f(a)>0$ のとき、$w$ から $u$ への逆方向の残余弧 $a^-$。その残余容量を $f(a)$ とする。
頂点集合 $V$ と残余弧全体からなる有向グラフを $f$ の残余ネットワーク $R_f$ という。

$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$ の内部の弧が打ち消し合う。

詳しい証明を開く

保存則により、$v\in S\setminus\{s\}$ では $f(\delta^+(v))-f(\delta^-(v))=0$ である（$t\notin S$ に注意）。よって $\operatorname{val}(f)=\sum_{v\in S}\bigl(f(\delta^+(v))-f(\delta^-(v))\bigr)$ である。右辺で、始点と終点がともに $S$ にある弧 $a$ は、始点の項で $+f(a)$、終点の項で $-f(a)$ として現れて打ち消し合う。残るのは $S$ から出る弧の $+f(a)$ と $S$ に入る弧の $-f(a)$ だけなので、右辺は $f(\delta^+(S))-f(\delta^-(S))$ に等しい。容量制約から $f(\delta^+(S))\le c(\delta^+(S))=c(S)$、$f(\delta^-(S))\ge0$ である。$\square$

流量を増やす手がかりは増加道である。

増加道による改善

$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 本の残余弧による変化が打ち消し合う。

詳しい証明を開く

$P$ の頂点は相異なるので、$a^+$（始点から終点へ）と $a^-$（終点から始点へ）が両方 $P$ に現れることはなく、$f'$ は矛盾なく定まる。$\varepsilon$ の選び方から $0\le f'\le c$ である。$P$ の内側の頂点 $v$ には $P$ の残余弧が 1 本入り 1 本出る。$v$ に入る残余弧が $a^+$ なら $a$ は $v$ に入る弧で、$v$ に入る量が $\varepsilon$ 増える。$a^-$ なら $a$ は $v$ から出る弧で、$v$ から出る量が $\varepsilon$ 減る。どちらでも「出る量 − 入る量」が $\varepsilon$ 減る。同様に $v$ から出る残余弧は「出る量 − 入る量」を $\varepsilon$ 増やす。よって $v$ で保存則が保たれる。$s$ からは $P$ の残余弧が 1 本出るだけなので、$s$ の「出る量 − 入る量」すなわち流量は $\varepsilon$ 増える。$\square$

最大流最小カット定理

ネットワーク $N$ には最大流が存在する。フロー $f$ について、次の 3 条件は同値である。
(a) $f$ は最大流である。
(b) $f$ の増加道（$R_f$ の $s$ から $t$ への有向道）は存在しない。
(c) $\operatorname{val}(f)=c(S)$ となるカット $S$ が存在する。
特に、最大流の流量は最小カットの容量に等しい。

最大流の存在。 フロー全体の集合 $\Phi\subset\mathbb{R}^A$ は、不等式 $0\le f(a)\le c(a)$ と保存則の等式で定まるので閉集合であり、各成分が $[0,c(a)]$ に入るので有界である。コンパクト空間の定理「有界閉集合とコンパクト性の一致」により $\Phi$ はコンパクトで、零フロー（すべての弧で $0$）を含むので空でない。$\operatorname{val}$ は 1 次式なので連続であり、同じ記事の定理「最大値・最小値の存在」により $\Phi$ 上で最大値をとる。
(a) ⇒ (b)。 増加道があれば、lem-nf-augment により流量のより大きいフローがあるので、$f$ は最大流でない。
(b) ⇒ (c)。 $R_f$ で $s$ から有向道で到達できる頂点（$s$ 自身を含む）全体を $S$ とする。増加道がないので $t\notin S$ であり、$S$ はカットである。$a\in\delta^+(S)$ を $u\in S$ から $w\notin S$ への弧とする。$f(a)< c(a)$ なら $R_f$ に $u$ から $w$ への残余弧 $a^+$ があり、$s$ から $u$ への有向道の後に $a^+$ をつなぐと $w$ に到達できて $w\notin S$ に反する（$w$ はその道の頂点でないので、つないだ列も有向道である）。よって $f(a)=c(a)$ である。$a\in\delta^-(S)$ を $w\notin S$ から $u\in S$ への弧とすると、同様に、$f(a)>0$ なら $u$ から $w$ への残余弧 $a^-$ があって矛盾するので、$f(a)=0$ である。lem-nf-weak-duality の等式から $\operatorname{val}(f)=c(\delta^+(S))-0=c(S)$ である。
(c) ⇒ (a)。 任意のフロー $f'$ について、lem-nf-weak-duality により $\operatorname{val}(f')\le c(S)=\operatorname{val}(f)$ である。
最後の主張。 最大流 $f$ をとると、(a) ⇒ (b) ⇒ (c) により $\operatorname{val}(f)=c(S)$ となるカット $S$ がある。lem-nf-weak-duality によりどのカットの容量も $\operatorname{val}(f)$ 以上なので、$c(S)$ は最小カットの容量であり、両者は等しい。$\square$

整数性定理

容量がすべて整数のネットワークでは、零フローから始めて、増加道があるかぎり 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$ のフローのままである。

入口・出口が複数ある場合と頂点の容量

入口が複数ある場合は、新しい頂点 $s^*$ と、$s^*$ から各入口への弧（容量は全容量の和など十分大きな値）を加え、$s^*$ を入口とすればよい。出口が複数ある場合も同様である。頂点にも通過量の上限 $m(v)$ がある場合は、$v$ を 2 頂点 $v^-,v^+$ に分け、$v$ に入る弧の終点を $v^-$、出る弧の始点を $v^+$ に付け替え、容量 $m(v)$ の弧 $v^-\to v^+$ を加えればよい（BM76 Exercise 11.3.5、p. 203）。この頂点を分ける操作は、Mengerの定理の頂点版を最大流から導くときにも使う。

性質

フローの分解

すべての頂点で保存則が成り立つ写像 $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 の定理は、多くの組合せ論の最小最大定理の源である。

二部グラフの最大マッチングは、容量 $1$ のネットワークの整数値の最大流として求められる（組合せ最適化の記事の命題「二部グラフのマッチングと最大流」）。そこから、二部グラフのマッチングの最大の大きさと頂点被覆の最小の大きさが等しいことが従う（マッチング(グラフ理論) の記事の定理「二部グラフの最大マッチングと最小頂点被覆」）。
有限半順序集合を最小個数の鎖に分ける Dilworthの定理も、ネットワークの言葉で述べ直せることが Dilworthの定理の記事で触れられている。
辺を除いたときの連結性の強さ（辺連結度）と、頂点を除いたときの強さ（連結度(グラフ)）は、それぞれ 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 の定理や二部グラフのマッチングへの応用を支えている。