ネットワークフロー

要点：$S$ の各頂点で「出る量 − 入る量」を足すと、$S$ の内部の弧が打ち消し合う。

要点：増加道の内側の頂点では、前後 2 本の残余弧による変化が打ち消し合う。

最大流の存在。 フロー全体の集合 $\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$

$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$

$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$

$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$

互いに弧素な $s$–$t$ 有向道の最大本数を $k$、取り除くと $s$–$t$ 有向道がなくなる弧の集合の最小の大きさを $l$ とする。そのような弧の集合 $Z$ は、$k$ 本の弧素な道のそれぞれと交わり、道どうしは弧を共有しないので、$|Z|\ge k$ である。よって $k\le l$ である。
逆を示す。すべての弧の容量を $1$ としたネットワークを考え、thm-nf-integrality により整数値の最大流 $f$ をとり、thm-nf-maxflow-mincut により $\operatorname{val}(f)=c(S)$ となるカット $S$ をとる。$s$–$t$ 有向道は $s\in S$ から始まり $t\notin S$ で終わるので、$S$ から外へ出る弧、すなわち $\delta^+(S)$ の弧を必ず含む。よって $\delta^+(S)$ を取り除くと $s$–$t$ 有向道はなくなり、$l\le|\delta^+(S)|=c(S)=\operatorname{val}(f)$ である。
零フローの流量は $0$ なので $\operatorname{val}(f)\ge0$ であり、thm-nf-decomposition により $f=\sum_i\lambda_i\chi_{P_i}+\sum_j\mu_j\chi_{C_j}$（$\lambda_i,\mu_j$ は正の整数、$\sum_i\lambda_i=\operatorname{val}(f)$）と書ける。弧 $a$ が $P_i$ に含まれれば $1\ge f(a)\ge\lambda_i\ge1$ なので $\lambda_i=1$ であり、$a$ を含む他の $P_{i'}$ はない（あれば $f(a)\ge2$）。よって $P_1,\dots,P_p$ は互いに弧素で、本数は $p=\sum_i\lambda_i=\operatorname{val}(f)\ge l$ である。したがって $k\ge l$ となり、$k=l$ である。$\square$

1：要点は、逆向きの 2 本の弧に同時に流れる部分を打ち消せば、弧素な有向道が辺素な道になることである。
辺 $uw$ ごとに弧 $u\to w$ と $w\to u$ を置いた有向グラフ $D$ を作り、すべての容量を $1$ とする。$k$ 本の互いに辺素な道があれば、取り除く辺の集合はそれぞれの道の辺を 1 本ずつ含むので、最小の大きさは $k$ 以上である。逆を示す。整数値の最大流のうち、全弧の値の和が最小のもの $f$ をとる。ある辺 $uw$ で $f(u\to w)=f(w\to u)=1$ なら、両方を $0$ にしても、$u$ と $w$ でそれぞれ入る量と出る量が $1$ ずつ減るだけなので保存則と流量は変わらず、値の和の小さい整数値の最大流が得られて矛盾する。よって、どの辺でも 2 本の弧の一方だけが値 $1$ をとりうる。
thm-nf-menger-arc の証明と同様に、thm-nf-decomposition により $f$ は $\operatorname{val}(f)$ 本の互いに弧素な $s$–$t$ 有向道（とそれ以外の閉路）に分解される。各有向道の向きを忘れると $G$ の $s$–$t$ 道である。2 本が辺 $uw$ を共有すると、弧素なので一方が $u\to w$、他方が $w\to u$ を使い、両方の値が $1$ となって上の性質に反する。よって互いに辺素な道が $\operatorname{val}(f)$ 本ある。
一方、$\operatorname{val}(f)=c(S)$ となるカット $S$ をとると、$\delta^+(S)$ の弧は、$S$ と $V\setminus S$ を結ぶ $G$ の辺と 1 対 1 に対応する（辺 $uw$、$u\in S$、$w\notin S$ には弧 $u\to w$ だけが対応する）。$s$ と $t$ を結ぶ道は必ずこれらの辺のどれかを通るので、これらを取り除けば道はなくなる。よって最小の大きさは $c(S)=\operatorname{val}(f)$ 以下であり、1 が示された。
2：要点は、各頂点を「入口側」と「出口側」の 2 つに分け、その間を 1 本の弧で結ぶと、頂点を共有しないことが弧を共有しないことに言い換えられることである。
$V\setminus\{s,t\}$ の各頂点 $v$ を 2 頂点 $v^-,v^+$ に置き換え、次の弧をもつ有向グラフ $D'$ を作る：各 $v$ について $v^-\to v^+$；$u,w$ がどちらも $s,t$ でない辺 $uw$ について $u^+\to w^-$ と $w^+\to u^-$；辺 $sw$ について $s\to w^-$；辺 $wt$ について $w^+\to t$。$s$ と $t$ は隣接しないので、$s$ と $t$ を直接結ぶ弧はない。
$s$ から出る弧は $w^-$ へ、$w^-$ から出る弧は $w^+$ への 1 本だけ、$w^+$ から出る弧は $x^-$ か $t$ へ向かう。したがって $D'$ の $s$–$t$ 有向道は $s,w_1^-,w_1^+,\dots,w_m^-,w_m^+,t$（$m\ge1$）の形をしており、$G$ の $s$–$t$ 道 $(s,w_1,\dots,w_m,t)$ と 1 対 1 に対応する。2 本の $G$ の道が内部頂点 $v$ を共有すれば、対応する $D'$ の道はどちらも弧 $v^-\to v^+$ を通る。逆に $D'$ の 2 本の道が弧を共有すれば、その弧は $v^-\to v^+$、$s\to v^-$、$v^+\to t$、$v^+\to w^-$ のいずれかで、どの場合も $G$ の道は内部頂点 $v$ を共有する。よって、内部頂点素な $s$–$t$ 道の最大本数 $k$ は、$D'$ の弧素な $s$–$t$ 有向道の最大本数に等しい。
thm-nf-menger-arc により、$D'$ には $s$–$t$ 有向道をすべて断つ $k$ 本の弧の集合 $Z$ がある。$Z$ の各弧に $V\setminus\{s,t\}$ の頂点を 1 つ対応させる：$v^-\to v^+$、$s\to v^-$、$v^+\to t$、$v^+\to w^-$ にはどれも $v$ を対応させる。こうして得た頂点の集合 $X$ は $|X|\le k$ を満たす。$G$ の $s$–$t$ 道に対応する $D'$ の道は $Z$ のある弧を通り、その弧に対応させた頂点は $G$ の道の内部頂点なので、$X$ は $s$ と $t$ を結ぶすべての道と交わる。よって最小の大きさは $k$ 以下である。逆に、$s$ と $t$ を結ぶすべての道と交わる $X\subset V\setminus\{s,t\}$ は、$k$ 本の内部頂点素な道の内部頂点を 1 つずつ含み、それらは相異なるので $|X|\ge k$ である。$\square$

$d_{f'}(v)< d_f(v)$ となる頂点 $v$ があると仮定し、そのうち $d_{f'}(v)$ が最小のものをとる。$d_{f'}(v)$ は有限で、$v\neq s$（$d_{f'}(s)=d_f(s)=0$）なので、$R_{f'}$ の最短の $s$–$v$ 有向道の最後の残余弧 $\rho$ を $u$ から $v$ への残余弧とすると、$d_{f'}(u)=d_{f'}(v)-1$ である。$v$ の選び方から $d_f(u)\le d_{f'}(u)$ である。
$\rho$ が $R_f$ にもあれば、$d_f(v)\le d_f(u)+1\le d_{f'}(u)+1=d_{f'}(v)$ となり、仮定に反する。$\rho$ が $R_f$ になければ、$\rho$ は増加によって新しく現れた残余弧である。増加で値が変わるのは $P$ の残余弧に対応する弧だけで、順方向の残余弧 $a^+$ が現れるのは $f(a)$ が減ったとき（$P$ が $a^-$ を使ったとき）、逆方向の残余弧 $a^-$ が現れるのは $f(a)$ が増えたとき（$P$ が $a^+$ を使ったとき）である。どちらの場合も $P$ は $v$ から $u$ への残余弧を使っており、$P$ は最短なので $d_f(u)=d_f(v)+1$ である。すると $d_f(v)=d_f(u)-1\le d_{f'}(u)-1=d_{f'}(v)-2$ となり、やはり仮定に反する。$\square$

要点：同じ残余弧が 2 度飽和弧になるたびに、その始点の距離 $d(\cdot)$ は 2 以上増える。距離は $|V|$ 未満なので、各残余弧が飽和弧になる回数は $|V|/2$ 以下である。
各弧 $a$ から作られうる残余弧は $a^+$ と $a^-$ の 2 つなので、残余弧の候補は $2|A|$ 個ある。各増加では少なくとも 1 つの残余弧が飽和弧になる。そこで、1 つの候補 $\rho$（$x$ から $y$ への残余弧とする）が飽和弧になる回数が $|V|/2$ 以下であることを示せば、増加の回数は $2|A|\cdot|V|/2=|V|\,|A|$ 以下となる。
$\rho$ がフロー $f$ での増加で飽和弧になったとする。$\rho$ は最短の道 $P$ の上にあるので $d_f(y)=d_f(x)+1$ である。増加の後 $\rho$ は消えるので、$\rho$ が次に飽和弧になる前に $\rho$ がもう一度現れなければならず、それには、あるフロー $f'$（$f$ より後）での増加の最短の道が、逆向きの残余弧（$y$ から $x$ への残余弧）を使う必要がある。そのとき $d_{f'}(x)=d_{f'}(y)+1$ であり、lem-nf-ek-monotone を繰り返し使うと $d_{f'}(y)\ge d_f(y)$ なので、$d_{f'}(x)\ge d_f(y)+1=d_f(x)+2$ である。次に $\rho$ が飽和弧になるときのフロー $f''$ でも、単調性から $d_{f''}(x)\ge d_{f'}(x)\ge d_f(x)+2$ である。
したがって、$\rho$ が飽和弧になるたびに、そのときの $d(x)$ は前回より $2$ 以上大きい。$\rho$ が飽和弧になるとき $x$ は最短の $s$–$t$ 有向道の上にあり $x\neq t$ なので、$0\le d(x)\le|V|-2$ である。$0,2,4,\dots$ のうち $|V|-2$ 以下のものは $|V|/2$ 個以下なので、$\rho$ が飽和弧になる回数は $|V|/2$ 以下である。
止まったとき $R_f$ には $s$–$t$ 有向道がないので、thm-nf-maxflow-mincut により $f$ は最大流である。$\square$