最大流最小カット定理

同義語:max-flow min-cut theorem最大流・最小カット定理最大フロー最小カット定理最大流最小切断定理Ford–Fulkersonの定理Ford–Fulkerson theorem

概要

最大流最小カット定理(max-flow min-cut theorem)とは、弧に容量の付いた有限の有向グラフで、入口 $s$ から出口 $t$ へ流せる量の最大値が、$s$ を含み $t$ を含まない頂点の集合から出る弧の容量の和の最小値に等しいという定理である。増加道がなくなるまで流量を増やす方法で証明され、容量が整数なら整数値の最大流がある。線形計画の双対定理の組合せ論的な形とみることができ、二部グラフのマッチングと頂点被覆の等式や、互いに弧を共有しない道の本数についての Menger の定理は、その系として得られる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 有向グラフ, ネットワークフロー

最大流最小カット定理(max-flow min-cut theorem)とは、弧に容量の付いた有限の有向グラフで、入口 $s$ から出口 $t$ へ流せる量の最大値が、$s$ を含み $t$ を含まない頂点の集合から出ていく弧の容量の和の最小値に等しい、という定理である。どのカットも流れの上界を与えることはすぐ分かり、定理の中身は「上界のうち最も小さいものはちょうど達成される」という逆向きの不等式にある。
$$ \max_{f\text{ はフロー}}\operatorname{val}(f)=\min_{S\text{ はカット}}c(S) $$
Ford と Fulkerson が 1954 年に、Elias、Feinstein、Shannon が 1956 年に独立に証明した(Eri19 §10.3、p. 331。BM76 Theorem 11.3、p. 198 は Ford と Fulkerson の 1956 年の論文を挙げている)。
この記事では、増加道による証明と整数性を述べたあと、定理を線形計画の双対として読み直す。さらに、二部グラフの König の定理、Menger の定理の弧版、課題の選択の問題を系として導き、仮定を外すと何が成り立たなくなるかを表にする。最大流を求める手順そのものは Edmonds–Karp法、フローの道への分解は ネットワークフロー で扱う。

定義

有向グラフは、有限の頂点集合 $V$ と有限の弧の集合 $A$ からなり、各弧に相異なる始点と終点が与えられたものとする。同じ始点と終点をもつ弧が複数あってもよい。$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$(入口)、$t$(出口)、容量 $c\colon A\to\mathbb{R}_{\ge0}$ の組である。

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

カットの容量には、$S$ から出る弧だけを数え、$S$ に戻る弧は数えない。これは ネットワークフロー の記事の定義「ネットワークとフロー」と同じ規約である。

定理

最大流最小カット定理

ネットワーク $N$ には最大流が存在し、最大流の流量は最小カットの容量に等しい。さらに、フロー $f$ について次の 3 条件は同値である。
(a) $f$ は最大流である。
(b) $f$ の増加道(下の def-mfmc-residual)は存在しない。
(c) $\operatorname{val}(f)=c(S)$ となるカット $S$ が存在する。

直観としては、入口から出口への流れは、網をどう 2 つに切り分けても、その切れ目を越えなければならない。だから最も細い切れ目の太さが流量の上限になる。定理は、この「いちばん細いくびれ」だけが流れを妨げる原因であることを主張する。条件 (c) の意味も大きい。フロー $f$ とカット $S$ を 1 組示して $\operatorname{val}(f)=c(S)$ を確かめれば、ほかのフローもカットも調べずに、両方の最適性が分かる。

証明

カットは流量の上界を与える

フローとカット

任意のフロー $f$ と任意のカット $S$ について
$$ \operatorname{val}(f)=f(\delta^+(S))-f(\delta^-(S))\le c(S) $$
が成り立つ。等号 $\operatorname{val}(f)=c(S)$ は、$\delta^+(S)$ のすべての弧で $f=c$ であり、$\delta^-(S)$ のすべての弧で $f=0$ であるときに限る。

$F(v):=f(\delta^+(v))-f(\delta^-(v))$ とおく。保存則から $v\neq s,t$ で $F(v)=0$ であり、$t\notin S$ だから $\operatorname{val}(f)=F(s)=\sum_{v\in S}F(v)$ である。右辺を弧ごとに集めると、両端が $S$ にある弧は始点で $+f(a)$、終点で $-f(a)$ と現れて消え、$\delta^+(S)$ の弧の $+f(a)$ と $\delta^-(S)$ の弧の $-f(a)$ が残る。これが等式である。
容量制約から $f(\delta^+(S))\le c(\delta^+(S))=c(S)$、$f(\delta^-(S))\ge0$ である。2 つの不等式の等号がともに成り立つことが、等号の条件である。$\square$

残余ネットワークと増加道

残余ネットワークと増加道

フロー $f$ に対し、頂点集合 $V$ の上の有向グラフ $R_f$ を、$A$ の各弧 $a$($u$ から $w$ へ)から次のように作る。

  • $f(a)< c(a)$ なら、$u$ から $w$ への順方向の残余弧を置き、残余容量を $c(a)-f(a)$ とする。
  • $f(a)>0$ なら、$w$ から $u$ への逆方向の残余弧を置き、残余容量を $f(a)$ とする。
    $R_f$ を $f$ の残余ネットワークといい、$R_f$ の $s$ から $t$ への(頂点の重複のない)有向道を $f$ の増加道という。

逆方向の残余弧は「すでに流した分を押し戻す」ことを表す。これがないと手順が途中で行き詰まる(ex-mfmc-back)。

増加道に沿った更新

$P$ を $f$ の増加道とし、$\varepsilon>0$ を $P$ の残余弧の残余容量の最小値とする。$P$ が $a$ の順方向の残余弧を通る弧では $f'(a):=f(a)+\varepsilon$、逆方向の残余弧を通る弧では $f'(a):=f(a)-\varepsilon$、ほかの弧では $f'(a):=f(a)$ とおくと、$f'$ はフローで $\operatorname{val}(f')=\operatorname{val}(f)+\varepsilon$ である。

要点:$P$ の内側の頂点では、入ってくる残余弧と出ていく残余弧の効果が打ち消し合う。

詳しい証明を開く

$P$ の頂点は相異なるので、1 つの弧 $a$ の順方向と逆方向の残余弧が両方 $P$ に現れることはなく、$f'$ は矛盾なく定まる。$\varepsilon$ の取り方から $0\le f'\le c$ である。

$F(v):=f(\delta^+(v))-f(\delta^-(v))$ を、$f'$ について同様に定めたものを $F'(v)$ とする。頂点 $v$ から出る $P$ の残余弧は、順方向なら $v$ から出る量を $\varepsilon$ 増やし、逆方向なら $v$ に入る量を $\varepsilon$ 減らすので、どちらでも $F(v)$ を $\varepsilon$ 増やす。同様に、$v$ に入る $P$ の残余弧は、どちらの向きでも $F(v)$ を $\varepsilon$ 減らす。

$P$ の内側の頂点には $P$ の残余弧が 1 本入り 1 本出るので $F'(v)=F(v)$ であり、$s,t$ 以外で保存則が保たれる。$s$ からは 1 本出るだけなので $F'(s)=F(s)+\varepsilon$、すなわち流量は $\varepsilon$ 増える。$\square$

定理の証明

最大流の存在。 フロー全体の集合 $\Phi\subset\mathbb{R}^A$ は、弱い不等式と等式で定まるので閉じていて、$\Phi\subset\prod_{a}[0,c(a)]$ なので有界である。また $0\in\Phi$ である。よって $\Phi$ は空でないコンパクト集合で、1 次式 $\operatorname{val}$ は $\Phi$ 上で最大値をとる。
(a) ⇒ (b)。 増加道があれば、lem-mfmc-augment により流量がより大きいフローがある。
(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$ への順方向の残余弧があり、$w$ に到達できてしまう。よって $f(a)=c(a)$ である。$a\in\delta^-(S)$ を $w\notin S$ から $u\in S$ への弧とする。$f(a)>0$ なら $R_f$ に $u$ から $w$ への逆方向の残余弧があり、やはり $w$ に到達できてしまう。よって $f(a)=0$ である。lem-mfmc-weak の等号の条件から $\operatorname{val}(f)=c(S)$ である。
(c) ⇒ (a)。 任意のフロー $f'$ について、lem-mfmc-weak により $\operatorname{val}(f')\le c(S)=\operatorname{val}(f)$ である。
最大流と最小カットの一致。 最大流 $f$ をとる。(a) ⇒ (b) ⇒ (c) により $\operatorname{val}(f)=c(S)$ となるカット $S$ がある。lem-mfmc-weak からどのカットの容量も $\operatorname{val}(f)=c(S)$ 以上なので、$S$ は最小カットである。$\square$

(b) ⇒ (c) の証明は、増加道がないときに最小カットを具体的に与えている。「$R_f$ で $s$ から行ける頂点の集合」を計算すればよい。

整数性定理

容量がすべて整数なら、すべての弧で整数値をとる最大流が存在する。実際、零フローから始めて lem-mfmc-augment の更新を増加道があるかぎり繰り返すと、高々 $c(\delta^+(s))$ 回で止まり、止まったときのフローは整数値の最大流である。

$f$ が整数値なら残余容量はすべて正の整数なので $\varepsilon\ge1$ は整数で、更新後の $f'$ も整数値である。零フローは整数値なので、手順中のフローはすべて整数値であり、流量は 1 回ごとに $1$ 以上増える。カット $\{s\}$ に lem-mfmc-weak を使うと流量は $c(\delta^+(s))$ 以下なので、更新は高々 $c(\delta^+(s))$ 回で止まる。止まったフローには増加道がないので、thm-mfmc-main の (b) ⇒ (a) により最大流である。$\square$

この定理が組合せ論への応用の鍵である。容量が $1$ のネットワークでは、整数値のフローは「使う・使わない」の選択になるからである。一方、容量が無理数を含むと、増加道の選び方によっては手順が止まらず、最大流に収束しないことさえある(Eri19 §10.4、p. 335)。増加道として弧の本数が最小のものを選べば、容量が実数でも有限回で止まる(Edmonds–Karp法)。

例

手順の実行と最小カット

頂点 $s,a,b,c,t$ と次の弧のネットワークを考える(括弧は容量):$s\to a$($4$)、$s\to b$($3$)、$a\to b$($2$)、$a\to c$($2$)、$b\to c$($1$)、$b\to t$($2$)、$c\to t$($4$)。
零フローから、増加道 $s\to a\to c\to t$ に $2$、$s\to b\to t$ に $2$、$s\to a\to b\to c\to t$ に $1$ を流すと、$f(s\to a)=3$、$f(s\to b)=2$、$f(a\to b)=1$、$f(a\to c)=2$、$f(b\to c)=1$、$f(b\to t)=2$、$f(c\to t)=3$ となり、流量は $5$ である。
このとき $R_f$ で $s$ から行ける頂点は $s,a,b$ である($s\to a$、$s\to b$ に余りがあるが、$a\to c$、$b\to c$、$b\to t$ は満杯で、$c$ にも $t$ にも行けない)。$S=\{s,a,b\}$ の容量は $2+1+2=5$ で流量に等しいので、$f$ は最大流、$S$ は最小カットである。カットは全部で $8$ 個あり、$\{s,a,b\}$ のほかの容量は $6$ 以上なので、最小カットはこの 1 つだけである。入口のすぐ外でも出口のすぐ手前でもない、網の途中にくびれがある例である。

逆方向の残余弧が要る例

頂点 $s,a,b,t$ と弧 $s\to a$、$s\to b$、$a\to b$、$a\to t$、$b\to t$(容量はすべて $1$)のネットワークで、最初に道 $s\to a\to b\to t$ に $1$ を流す。このフローには、順方向の弧だけでできた $s$ から $t$ への道がない。$s\to a$ と $b\to t$ が満杯だからである。しかし最大流の流量は $2$ である($s\to a\to t$ と $s\to b\to t$ に $1$ ずつ流す)。
$R_f$ には $a\to b$ の逆方向の残余弧 $b\to a$ があり、増加道 $s\to b\to a\to t$ がある。これに沿って更新すると、$a\to b$ の流れが取り消されて流量 $2$ のフローになる。

カットの性質を 2 つ述べる。

最小カットの性質
  1. $f$ を最大流、$S$ を最小カットとすると、$\delta^+(S)$ のすべての弧で $f=c$、$\delta^-(S)$ のすべての弧で $f=0$ である。
  2. $S,S'$ が最小カットなら、$S\cap S'$ と $S\cup S'$ も最小カットである。
  1. thm-mfmc-main により $\operatorname{val}(f)=c(S)$ なので、lem-mfmc-weak の等号の条件から従う。
  2. まず、任意の部分集合 $S,S'\subset V$ について
    $$ c(S)+c(S')\ge c(S\cap S')+c(S\cup S') $$
    を示す。容量は $0$ 以上なので、弧 $a$($u$ から $w$ へ)が右辺で数えられる回数が左辺で数えられる回数以下であることを確かめればよい。$a\in\delta^+(S\cap S')$ かつ $a\in\delta^+(S\cup S')$ なら、$u\in S\cap S'$、$w\notin S\cup S'$ なので、$a$ は左辺で 2 回数えられる。$a\in\delta^+(S\cap S')$ なら、$u$ は $S,S'$ の両方に属し、$w$ は少なくとも一方に属さないので、$a\in\delta^+(S)$ または $a\in\delta^+(S')$ である。$a\in\delta^+(S\cup S')$ なら、$u$ は少なくとも一方に属し、$w$ は両方に属さないので、やはり $a\in\delta^+(S)$ または $a\in\delta^+(S')$ である。
    $S,S'$ がカットなら、$s\in S\cap S'$、$s\in S\cup S'$、$t\notin S\cup S'$ なので、$S\cap S'$、$S\cup S'$ もカットである。最小カットの容量を $m$ とすると $2m=c(S)+c(S')\ge c(S\cap S')+c(S\cup S')\ge2m$ であり、等号が成り立つ。$\square$

線形計画の双対として見る

最大流を求める問題は、弧の値 $f(a)$ を変数とする線形計画問題である。弧 $a$ の始点を $\partial^+a$、終点を $\partial^-a$ と書く。線形計画法 の記事の定義「双対問題」に従って双対問題を作ると、変数は弧ごとの $y_a\ge0$ と頂点ごとの $\pi_v\in\mathbb{R}$ で、次の問題になる。
$$ \text{(D)}\qquad\text{最小化 }\sum_{a\in A}c(a)\,y_a\quad\text{条件 }y_a\ge\pi_{\partial^+a}-\pi_{\partial^-a},\ \ y_a\ge0,\ \ \pi_s=1,\ \ \pi_t=0 $$

双対問題の導き方を開く

主問題は「最大化 $\sum_a\bigl(\mathbf 1_{\partial^+a=s}-\mathbf 1_{\partial^-a=s}\bigr)f(a)$、条件 $f(a)\le c(a)$、$v\neq s,t$ で $f(\delta^+(v))-f(\delta^-(v))\le0$ と $f(\delta^-(v))-f(\delta^+(v))\le0$、$f\ge0$」である。乗数を順に $y_a\ge0$、$p_v\ge0$、$q_v\ge0$ とし、$\rho_v:=p_v-q_v$($v\neq s,t$)とおく。$f(a)$ の係数の条件は $y_a+\rho_{\partial^+a}-\rho_{\partial^-a}\ge\mathbf 1_{\partial^+a=s}-\mathbf 1_{\partial^-a=s}$ である($\rho_s=\rho_t=0$ とする)。$\pi_v:=-\rho_v$($v\neq s,t$)、$\pi_s:=1$、$\pi_t:=0$ とおくと、これは $y_a\ge\pi_{\partial^+a}-\pi_{\partial^-a}$ と同じである。目的関数は $\sum_ac(a)y_a$ である。


カット $S$ からは、$\pi_v:=1$($v\in S$)、$\pi_v:=0$($v\notin S$)、$y_a:=1$($a\in\delta^+(S)$)、$y_a:=0$(それ以外)という (D) の実行可能解ができ、目的関数の値は $c(S)$ である。つまりカットは (D) の値が $0,1$ だけの解である。次の命題は、(D) の最適値がカットだけで達成されることをいう。

双対問題の解からカットを作る

$(y,\pi)$ を (D) の実行可能解とする。$\theta\in(0,1]$ について $S_\theta:=\{v\in V\mid\pi_v\ge\theta\}$ とおくと、$S_\theta$ はカットであり、
$$ \int_0^1c(S_\theta)\,d\theta\le\sum_{a\in A}c(a)\,y_a $$
が成り立つ。とくに $c(S_\theta)\le\sum_ac(a)y_a$ となる $\theta$ がある。

$\pi_s=1\ge\theta>0=\pi_t$ なので $S_\theta$ はカットである。弧 $a$($u$ から $w$ へ)が $\delta^+(S_\theta)$ に入るのは $\pi_w< \theta\le\pi_u$ のときである。そのような $\theta\in(0,1]$ の集合は長さ $\max(\pi_u-\pi_w,0)$ 以下の区間なので、$a$ の積分への寄与は $c(a)\max(\pi_u-\pi_w,0)\le c(a)y_a$ 以下である($c(a)\ge0$ と (D) の条件を使う)。$\theta\mapsto c(S_\theta)$ は有限個の値をとる階段関数なので、弧について足し合わせれば不等式を得る。積分の値を超えない $\theta$ がとれることは、平均値の性質である。$\square$

零フローと $\{s\}$ から作った解により、主問題と (D) はともに実行可能である。よって 線形計画法 の記事の定理「線形計画法の双対定理」から、最大流の流量は (D) の最適値に等しい。prop-mfmc-lp により (D) の最適値は最小カットの容量以上であり、lem-mfmc-weak と合わせて $\max\operatorname{val}=\min c$ が再び得られる。これは、増加道を使わない第 2 の証明である。
この見方では、thm-mfmc-main は「双対問題 (D) に、値が $0,1$ の最適解がある」という主張であり、thm-mfmc-integrality は「主問題に、容量が整数なら整数の最適解がある」という主張である。一般の線形計画問題では、係数が整数でも整数の最適解があるとは限らない(たとえば「最大化 $x$、条件 $2x\le1$、$x\ge0$」の最適解は $x=\frac12$ である)。

応用

二部グラフのマッチング

グラフのマッチングとは端点を共有しない辺の集合、頂点被覆とは、どの辺にも少なくとも一方の端点が属する頂点の集合である。マッチングの最大の大きさを $\nu(G)$、頂点被覆の最小の大きさを $\tau(G)$ と書く。

König の定理(二部グラフ)

部集合 $X,Y$ をもつ有限二部グラフ $G$ について $\nu(G)=\tau(G)$ である。

マッチングの辺は端点を共有しないので、頂点被覆はそれぞれの辺から別々の頂点を含み、$\nu(G)\le\tau(G)$ である。逆を示す。
新しい頂点 $s,t$ を加え、弧 $s\to x$($x\in X$、容量 $1$)、$y\to t$($y\in Y$、容量 $1$)、辺 $xy$ ごとの弧 $x\to y$(容量 $M:=\lvert X\rvert+1$)を張ったネットワークを作る。thm-mfmc-integrality により整数値の最大流 $f$ がある。$x$ に入る量は $1$ 以下なので、$x$ から出る弧で値が正のものは高々 1 本で、その値は $1$ である。$y$ から出る量も $1$ 以下なので、$y$ に入る弧で値が正のものは高々 1 本である。よって値 $1$ の弧 $x\to y$ に対応する辺の集合はマッチングで、その大きさは $\operatorname{val}(f)$ である。したがって $\operatorname{val}(f)\le\nu(G)$ である。
$S$ を最小カットとする。$c(S)\le c(\{s\})=\lvert X\rvert< M$ なので、弧 $x\to y$ で $x\in S$、$y\notin S$ となるものはない。$C:=(X\setminus S)\cup(Y\cap S)$ とおくと、$\delta^+(S)$ は $x\in X\setminus S$ ごとの $s\to x$ と $y\in Y\cap S$ ごとの $y\to t$ からなるので、$c(S)=\lvert C\rvert$ である。辺 $xy$ について、$x\notin S$ なら $x\in C$ であり、$x\in S$ なら $y\in S$ なので $y\in C$ である。よって $C$ は頂点被覆である。thm-mfmc-main から $\tau(G)\le\lvert C\rvert=c(S)=\operatorname{val}(f)\le\nu(G)$ である。$\square$

容量を $1$ でなく十分大きな $M$ にしたことで、最小カットの形がそのまま頂点被覆になる。同じ等式の Hall の条件を使う証明は マッチング(グラフ理論) の定理「二部グラフの最大マッチングと最小頂点被覆」にあり、容量をすべて $1$ とする証明は 組合せ最適化 の命題「二部グラフのマッチングと最大流」にある。

互いに交わらない道

道の本数と弧カット

有向グラフ $(V,A)$ の相異なる 2 頂点 $s,t$ について、互いに弧を共有しない $s$ から $t$ への有向道の最大本数は、取り除くと $s$ から $t$ への有向道がなくなる弧の集合の最小の大きさに等しい。

$k$ 本の弧素な道は、そのような弧の集合から別々の弧を含むので、最大本数は最小の大きさ以下である。逆を示す。容量をすべて $1$ とし、整数値の最大流 $f$ とカット $S$ を $\operatorname{val}(f)=c(S)$ となるようにとる(thm-mfmc-main、thm-mfmc-integrality)。$s$ から $t$ への有向道は $\delta^+(S)$ の弧を通るので、$\delta^+(S)$ は大きさ $c(S)$ の、道を断つ弧の集合である。一方、$\operatorname{val}(f)\ge0$ なので、ネットワークフロー の記事の定理「フローの分解」により、$f$ は正の整数を係数とする有向道と有向閉路の和で、道の係数の和は $\operatorname{val}(f)$ である。容量が $1$ なので、この道の族は互いに弧を共有せず、係数はすべて $1$ である。よって弧素な道が $\operatorname{val}(f)=c(S)$ 本ある。$\square$

これは Mengerの定理 の弧版である(BM76 Theorem 11.4、p. 204)。頂点版・無向グラフの形は Mengerの定理 で扱う。

課題の選択

前提のある課題の選択

有限集合 $P$ の各課題 $v$ に利益 $p(v)\in\mathbb{R}$(負なら費用)があり、「$u$ を行うなら $w$ も行う」という前提の組の集合 $L\subset P\times P$ があるとする。前提を満たす $X\subset P$ のうち、$p(X):=\sum_{v\in X}p(v)$ を最大にしたい(Eri19 §11.7、pp. 366–367)。
$H:=\sum_{p(v)>0}p(v)$、$M:=H+1$ とする。$s,t$ を加え、$p(v)>0$ の $v$ に弧 $s\to v$(容量 $p(v)$)、$p(v)< 0$ の $v$ に弧 $v\to t$(容量 $-p(v)$)、$(u,w)\in L$ に弧 $u\to w$(容量 $M$)を張る。カット $S$ に $X:=S\setminus\{s\}$ を対応させる。$c(\{s\})=H< M$ なので、最小カットは弧 $u\to w$ を切らず、$X$ は前提を満たす。前提を満たす $X$ については
$$ c(S)=\sum_{v\notin X,\,p(v)>0}p(v)+\sum_{v\in X,\,p(v)< 0}\bigl(-p(v)\bigr)=H-p(X) $$
である。よって $p(X)$ の最大値は $H$ から最小カットの容量を引いたものであり、最大流の計算で求まる。
たとえば $p(a)=5$、$p(b)=3$、$p(e)=-4$、$p(g)=-2$ で、$a$ の前提が $e$、$b$ の前提が $e,g$ のとき、$H=8$ である。$\{a,b,e,g\}$ の利益は $2$ で、対応するカットの容量は $4+2=6=8-2$ である。ほかの前提を満たす $X$ の利益は $1$ 以下なので、これが最適である。

反例:仮定を外すと成り立たないこと

次の表の各行は、条件を 1 つだけ替えたときに成り立たなくなることを示す。

替える条件反例成り立たなくなること
容量が整数弧 $s\to t$ が 1 本で容量 $\frac12$thm-mfmc-integrality:整数値の最大流の存在
残余弧に逆方向を含めるex-mfmc-back の最初のフロー(b) ⇒ (a):順方向の道がなければ最大流であること
カットの容量は出る弧だけを数える下の 4 本の弧のネットワーク最大流と最小カットの一致(戻る弧も数えた場合)
頂点が有限個下の無限の道lem-mfmc-weak:流量がカットの容量以下であること
流すものが 1 種類下の星型グラフ流量の和の最大と、切り離しに要る辺の数の最小の一致
表の反例の確かめ

戻る弧も数える場合。 弧 $s\to a$、$a\to t$(容量 $1$)と $a\to s$、$t\to a$(容量 $5$)のネットワークを考える。カットは $\{s\}$ と $\{s,a\}$ の 2 つである。定義どおりの容量はどちらも $1$ で、最大流の流量 $1$ に等しい。戻る弧の容量も足すと、どちらも $6$ になり、$1$ と一致しない。
無限の道。 $V=\{s,t,v_1,v_2,\dots\}$ とし、弧 $s\to v_1$、$v_i\to v_{i+1}$($i\ge1$、容量 $1$)だけをもつ無限のネットワークで、すべての弧で $f=1$ とおく。$s,t$ 以外の各頂点で入る量と出る量は等しく、流量は $1$ である。しかし $t$ には弧がないので、カット $V\setminus\{t\}$ の容量は $0$ である。流れは無限の彼方へ逃げている。lem-mfmc-weak の証明で、$S$ が有限であることを使っていた。
星型グラフ。 中心 $o$ と葉 $x_1,x_2,x_3$ を辺で結んだ無向グラフで、3 つの組 $\{x_1,x_2\}$、$\{x_2,x_3\}$、$\{x_1,x_3\}$ を結びたい。各組の道に重み $\lambda_{ij}\ge0$ を載せ、各辺を通る重みの和を $1$ 以下とする。どの道も 2 本の辺を通り、辺は 3 本なので $2\sum\lambda_{ij}\le3$ であり、重みの和の最大は $\frac32$ である(すべて $\frac12$ とすれば達成される)。一方、3 つの組をすべて切り離すには、葉のうち高々 1 つしか $o$ につながっていてはいけないので、辺を $2$ 本除く必要があり、$2$ 本で足りる。よって最大 $\frac32$ と最小 $2$ は一致しない。組が 1 つだけなら、各辺を互いに逆向きの 2 本の弧に置き換えることで、無向グラフでも等号が成り立つので、最大と最小が一致しない原因は組の数である。

補足

  • 入口・出口が複数の場合、頂点に容量がある場合:新しい頂点を加える、頂点を 2 つに分けるなどの変形で、この記事の形に帰着する(ネットワークフロー の例「入口・出口が複数ある場合と頂点の容量」)。
  • 定理の使い方:グラフの多くの結果は、適切なネットワークを作ることで最大流最小カット定理から得られる(BM76 p. 198)。Hallの結婚定理 も、Hall の条件のもとで頂点被覆の大きさを評価すれば cor-mfmc-konig から導ける。Dilworthの定理 もネットワークの言葉で述べ直せる。
  • 計算:(b) ⇒ (c) の証明から、最大流が求まれば最小カットは 1 回の探索で求まる。カットの最小化を、全カットを調べずに行えるのはこのためである。

関連項目

参考文献

[1]
J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Macmillan / American Elsevier, 1976, Chapter 11:Theorem 11.2(p. 197)、Theorem 11.3(p. 198)、Theorem 11.4(p. 204)
[2]
Jeff Erickson, Algorithms, 1st paperback edition, Independently published, 2019, §10.3 The Maxflow-Mincut Theorem(p. 331)、§10.4 Ford and Fulkerson's augmenting-path algorithm(pp. 334–335、Integrality Theorem と Irrational Capacities)、§11.7 Project Selection(pp. 366–367)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する