Edmonds–Karp法
概要
Edmonds–Karp法（Edmonds–Karp algorithm）とは、ネットワークの最大流を求める増加道の方法（Ford–Fulkerson の方法）で、残余ネットワークの増加道として弧の本数が最小のものを幅優先探索で選ぶ規則をいう。容量が任意の非負実数でも、増加は頂点の個数と弧の本数の積以下の回数で止まって最大流を与え、全体の手間は $|V|\,|A|\,(|V|+|A|)$ に比例する。増加道の選び方を決めない方法では、容量が整数でも回数が頂点と弧の個数で抑えられない例や、無理数の容量で手順が止まらず流量が最大流の流量に近づかない例がある。
Edmonds–Karp 法（Edmonds–Karp algorithm）は、ネットワークの最大流を求める方法の一つである。零フローから始めて、残余ネットワークに入口から出口への有向道（増加道）があるかぎり、それに沿って流量を増やすという Ford–Fulkerson の方法で、増加道として弧の本数が最小のものを選ぶ。最短の増加道は幅優先探索で見つかる。
増加道の選び方を決めない一般の方法では、容量が整数なら有限回で止まるが、その回数は頂点と弧の個数では抑えられず、容量に無理数があると止まらないことさえある。最短の増加道を選ぶと、容量が任意の非負の実数でも、増加の回数は頂点の個数と弧の本数の積以下になる。この記事では、この回数の上界を証明し、計算の手間を見積もり、選び方が悪いと回数が増える例と止まらない例を確かめる。
定義
ネットワーク $N=(V,A,s,t,c)$、フロー、流量 $\operatorname{val}(f)$、残余ネットワーク $R_f$、増加道は ネットワークフロー の記事の定義「ネットワークとフロー」「残余ネットワーク」とその後の説明による。容量 $c\colon A\to\mathbb R_{\ge0}$ は実数でよく、同じ始点と終点をもつ弧が複数あってもよい。弧 $a$ から作られうる残余弧は、順方向の $a^+$（残余容量 $c(a)-f(a)$）と逆方向の $a^-$（残余容量 $f(a)$）の 2 つで、$R_f$ には残余容量が正のものだけが属する。$a^+$ と $a^-$ は互いに逆向きの残余弧である。
増加道 $P$ の残余弧の残余容量の最小値を $\varepsilon(P)$ と書く。ネットワークフロー の記事の補題「増加道による改善」のとおり、$P$ が $a^+$ を含む弧で $f(a)$ を $\varepsilon(P)$ 増やし、$a^-$ を含む弧で $\varepsilon(P)$ 減らすと、流量が $\varepsilon(P)$ 増えたフローになる。これを $P$ に沿った増加 という。このとき残余容量が $\varepsilon(P)$ だった $P$ の残余弧は $R_f$ から消える。それをこの増加の 飽和弧 とよぶ。
- 零フローから始めて、$R_f$ に増加道があるかぎり、増加道を 1 つ選んでそれに沿って増加させることを繰り返す手順を、Ford–Fulkerson の方法（増加道の方法）という。増加道の選び方は決めない。
- Ford–Fulkerson の方法で、増加道として毎回 $R_f$ の $s$–$t$ 有向道のうち弧の本数が最小のもの（最短の増加道）を選ぶ手順を Edmonds–Karp 法 という。
Edmonds–Karp 法の 1 回の繰り返しは、次の 3 段からなる。(1) 現在のフロー $f$ から残余ネットワーク $R_f$ を作る。(2) $R_f$ で $s$ から幅優先探索を行い、$t$ に印が付かなければ止まる。印が付けば、探索木で $t$ から親をたどって最短の増加道 $P$ を得る。(3) $\varepsilon(P)$ を求め、$P$ に沿って増加させる。
フロー $f$ と頂点 $v$ について、$R_f$ で $s$ から $v$ への有向道の弧の本数の最小値を $d_f(v)$ と書く（有向道がなければ $d_f(v)=\infty$）。$d_f(s)=0$ であり、$R_f$ に $u$ から $v$ への残余弧があれば $d_f(v)\le d_f(u)+1$ である。最短の増加道 $P$ の上の連続する 2 頂点 $u,v$ では $d_f(v)=d_f(u)+1$ である。
直感
$R_f$ の頂点を $s$ からの距離 $d_f$ で層に分けると、最短の増加道は $s$ から層を 1 つずつ進む弧だけを通る。増加で新しく現れる残余弧は、使った弧の逆向き、つまり層を 1 つ戻る弧なので、近道を作らない。だから各頂点の距離は減らない（lem-ek-monotone）。一方、飽和弧は消え、それが再び現れるには逆向きの弧を使う増加が必要で、その間に始点の距離が 2 以上増える。距離は $|V|$ 未満なので、これは有限回しか起こらない。選び方を決めない方法では、遠回りの増加道が新しい近道を作り、同じ弧が何度でも満たされたり空いたりする（ex-ek-bad-integer、ex-ek-distance-decrease）。
回数の上界
$f$ をフロー、$P$ を $R_f$ の最短の増加道とし、$P$ に沿って増加させたフローを $f'$ とする。このとき、すべての頂点 $v$ について $d_{f'}(v)\ge d_f(v)$ である。
$d_{f'}(v)< d_f(v)$ となる頂点があると仮定し、そのうち $d_{f'}(v)$ が最小の $v$ をとる。$d_{f'}(v)$ は有限で、$v\ne s$ である。$R_{f'}$ の最短の $s$–$v$ 有向道の最後の残余弧を $u$ から $v$ への $\rho$ とすると、$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$ が使った残余弧の逆向きの残余弧だけなので、$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$
特に、Edmonds–Karp 法で選ばれる増加道の長さ $d_f(t)$ は、回を追って減らない。
ネットワーク $N=(V,A,s,t,c)$（容量は任意の非負実数）に Edmonds–Karp 法を行うと、増加は高々 $|V|\,|A|$ 回で止まり、止まったときのフローは最大流である。
要点：同じ残余弧が次に飽和弧になるまでに、その始点の距離は $2$ 以上増える。距離は $|V|-2$ 以下なので、各残余弧が飽和弧になる回数は $|V|/2$ 以下である。
残余弧の候補は各弧の $a^+,a^-$ で $2|A|$ 個あり、各増加では少なくとも 1 つが飽和弧になる。よって、1 つの候補 $\rho$（$x$ から $y$ への残余弧）が飽和弧になる回数が $|V|/2$ 以下であることを示せば、増加の回数は $2|A|\cdot|V|/2=|V|\,|A|$ 以下である。
$\rho$ がフロー $f$ での増加で飽和弧になったとする。$\rho$ は最短の増加道の上にあるので $d_f(y)=d_f(x)+1$ である。増加の後 $\rho$ は消える。$\rho$ が再び飽和弧になるには、その前に $\rho$ が再び現れなければならず、そのためには、あるフロー $f'$（$f$ より後）での増加の道が、$\rho$ の逆向きの残余弧（$y$ から $x$ への残余弧）を使う必要がある。そのとき $d_{f'}(x)=d_{f'}(y)+1$ であり、lem-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$ は最短の増加道（弧は $|V|-1$ 本以下）の上の $t$ でない頂点なので $0\le d(x)\le|V|-2$ である。$0,2,4,\dots$ のうち $|V|-2$ 以下のものは $|V|/2$ 個以下なので、$\rho$ が飽和弧になる回数は $|V|/2$ 以下である。
止まったとき $R_f$ には増加道がないので、ネットワークフロー の記事の定理「最大流最小カット定理」の (b) ⇒ (a) により $f$ は最大流である。$\square$
この定理は容量が整数であることを使わないので、最大流が存在することの、コンパクト性を使わない証明にもなっている。
実数の加減と比較を 1 回の操作と数えると、Edmonds–Karp 法は $|V|\,|A|\,(|V|+|A|)$ に比例する回数の操作で最大流を求める。特に $|A|\ge|V|-1$ なら $|V|\,|A|^2$ に比例する。
1 回の増加では、$R_f$ を作る（各弧について残余容量を 2 つ計算する）のに $|V|+|A|$ に比例する操作、$s$ からの幅優先探索で最短の増加道を求めるのに $|V|+2|A|$ に比例する操作（幅優先探索 の記事の命題「幅優先探索の手間」と注意「有向グラフでの幅優先探索」）、道に沿って $\varepsilon(P)$ を求めて値を更新するのに $|V|$ に比例する操作がかかる。thm-ek-iterations により増加は $|V|\,|A|$ 回以下なので、合計は $|V|\,|A|\,(|V|+|A|)$ に比例する。$|A|\ge|V|-1$ なら $|V|+|A|\le2|A|+1$ である。$\square$
Eri19 §10.6（pp. 341–342）も、距離の単調性と、同じ残余弧が消える回数の評価から、同じ型の回数の上界と手間の評価を導いている。BM76 pp. 199, 202 は、増加道を探すラベル付けで「先にラベルを付けた頂点から先に調べる」ようにする Edmonds と Karp の改良を紹介し、これが最短の増加道を選ぶことにあたると述べている。
例
頂点 $s,a,b,t$ と、弧 $s\to a$（容量 $2$）、$s\to b$（$1$）、$a\to b$（$1$）、$a\to t$（$1$）、$b\to t$（$2$）のネットワークを考える。零フローでは最短の増加道は長さ $2$ の $s,a,t$ と $s,b,t$ である。$s,a,t$ を選ぶと $\varepsilon=1$ で、$a\to t$ が飽和する。次の最短の増加道は $s,b,t$ で、$\varepsilon=1$ で $s\to b$ が飽和する。このとき $R_f$ の残余弧は $s\to a$（$1$）、$a\to s$（$1$）、$a\to b$（$1$）、$t\to a$（$1$）、$b\to s$（$1$）、$b\to t$（$1$）、$t\to b$（$1$）で、最短の増加道は長さ $3$ の $s,a,b,t$ であり、$\varepsilon=1$ で流量は $3$ になる。カット $\{s\}$ の容量 $2+1=3$ に等しいので最大流である。選ばれた道の長さは $2,2,3$ と減らない。
$m$ を正の整数とする。頂点 $s,p,u,q,r,v,w,t$ と、容量 $m$ の弧 $s\to p$、$p\to u$、$u\to q$、$q\to t$、$s\to r$、$r\to v$、$v\to w$、$w\to t$、容量 $1$ の弧 $u\to v$ からなるネットワークを考える（BM76 Figure 11.9、p. 202 と同じ形）。カット $\{s\}$ の容量は $2m$ で、長さ $4$ の道 $s,p,u,q,t$ と $s,r,v,w,t$ に $m$ ずつ流せば流量 $2m$ なので、最大流の流量は $2m$ である。Edmonds–Karp 法ではまさにこの 2 本が選ばれ、2 回で止まる。
一方、長さ $5$ の増加道 $s,p,u,v,w,t$（$u\to v$ を順方向に使う）と $s,r,v,u,q,t$（$u\to v$ を逆方向に使う）を交互に選ぶと、毎回の $\varepsilon$ は $u\to v$ の $1$ である。$2k$ 回の後のフローは $u\to v$ で $0$、他の 8 本の弧で $k$ であり、$k< m$ の間は次の道も増加道である。よって最大流に達するまで $2m$ 回かかり、$m>36$ なら $|V|\,|A|=72$ を超える。
$r=(\sqrt5-1)/2$ とすると $r^2=1-r$、$0< r< 1$ である。$M\ge6$ を整数とする。頂点 $s,a,b,c,d,t$ と、容量 $M$ の弧 $s\to a$、$s\to b$、$s\to d$、$a\to t$、$c\to t$、$d\to t$、および弧 $e_1=b\to a$（容量 $1$）、$e_2=b\to c$（容量 $1$）、$e_3=d\to c$（容量 $r$）からなるネットワークを考える。道 $s,a,t$ と $s,d,t$ に $M$ ずつ、$s,b,c,t$ に $1$ を流すと流量 $2M+1$ で、カット $\{s,a,b\}$ の容量（$s\to d$、$a\to t$、$b\to c$）も $2M+1$ なので、最大流の流量は $2M+1$ である。
増加道として次の 4 本を使う。
$$
\begin{aligned}
P_0&=s,b,c,t, & P_1&=s,d,c,b,a,t,\\
P_2&=s,b,c,d,t, & P_3&=s,a,b,c,t.
\end{aligned}
$$
$P_1$ は $e_3$ を順方向、$e_2$ を逆方向、$e_1$ を順方向に、$P_2$ は $e_2$ を順方向、$e_3$ を逆方向に、$P_3$ は $e_1$ を逆方向、$e_2$ を順方向に使う。$e_1,e_2,e_3$ の残余容量 $c(e_i)-f(e_i)$ の組を状態とよぶ。
最初に $P_0$ に沿って増加させると $\varepsilon=1$ で、状態は $(1,0,r)$ になる。偶数 $n\ge0$ について状態が $(r^n,0,r^{n+1})$ なら、$P_1,P_2,P_1,P_3$ の順に増加させると、$\varepsilon$ はそれぞれ $r^{n+1},r^{n+1},r^{n+2},r^{n+2}$ で、状態は
$$
(r^n,0,r^{n+1})\to(r^{n+2},r^{n+1},0)\to(r^{n+2},0,r^{n+1})\to(0,r^{n+2},r^{n+3})\to(r^{n+2},0,r^{n+3})
$$
と変わる。
状態の計算を開く
$P_1$ の $\varepsilon$ は $e_3$ の残余容量 $r^{n+1}$、$e_2$ の流量 $1$、$e_1$ の残余容量 $r^n$ の最小値 $r^{n+1}$ で、増加後 $e_1$ は $r^n-r^{n+1}=r^n(1-r)=r^{n+2}$、$e_2$ は $r^{n+1}$、$e_3$ は $0$ になる。$P_2$ の $\varepsilon$ は $e_2$ の残余容量 $r^{n+1}$ と $e_3$ の流量 $r$ の最小値 $r^{n+1}$ で、$e_2$ は $0$、$e_3$ は $r^{n+1}$ になる。再び $P_1$ では、$e_3$ の $r^{n+1}$、$e_2$ の流量 $1$、$e_1$ の $r^{n+2}$ の最小値 $r^{n+2}$ で、$e_1$ は $0$、$e_2$ は $r^{n+2}$、$e_3$ は $r^{n+1}-r^{n+2}=r^{n+3}$ になる。$P_3$ では、$e_1$ の流量 $1$ と $e_2$ の $r^{n+2}$ の最小値 $r^{n+2}$ で、$e_1$ は $r^{n+2}$、$e_2$ は $0$ になる。4 本の道は容量 $M$ の弧をどれも順方向に使い、各道はそのような弧を 2 本ずつ通るので、それらの弧の流量は流量 $\operatorname{val}(f)$ 以下である。下で見るとおり流量はいつも $2+\sqrt5$ 未満で $5$ より小さいので、それらの弧の残余容量は $M-5\ge1$ より大きく、$\varepsilon$（いつも $1$ 以下）を決めることはない。$\square$
したがってこの増加は永久に続けられ、どの段階でも増加道があるので手順は止まらない。流量は
$$ 1+2\sum_{j\ge1}r^j=1+\frac{2r}{1-r}=1+\frac{2}{r}=2+\sqrt5 $$
に増加しながら収束し、最大流の流量 $2M+1\ge13$ に近づかない。Edmonds–Karp 法をこのネットワークに行えば、thm-ek-iterations により $6\cdot9=54$ 回以下の増加で最大流に達する。
この例は Zwick によるもので、Eri19 §10.4（pp. 335–336）にある。容量が有理数なら、このようなことは起こらない。
容量がすべて有理数なら、Ford–Fulkerson の方法は増加道をどう選んでも有限回で止まり、最大流を与える。
容量の分母の公倍数となる正の整数を $L$ とする。零フローの残余容量はすべて $1/L$ の整数倍であり、フローの値と残余容量が $1/L$ の整数倍なら、$\varepsilon(P)$ も $1/L$ の正の整数倍で、増加後の値もそうである。よって毎回の増加で流量は $1/L$ 以上増える。流量はいつもカット $\{s\}$ の容量 $c(\{s\})$ 以下なので（ネットワークフロー の記事の補題「フローとカット」）、増加は $L\,c(\{s\})$ 回以下で止まる。止まったときは増加道がないので、最大流最小カット定理により最大流である。$\square$
仮定を外した場合
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-ek-iterations の「最短の増加道を選ぶ」（容量は整数のまま） | ex-ek-bad-integer | 増加の回数が $\lvert V\rvert\,\lvert A\rvert$ で抑えられない |
| thm-ek-iterations の「最短の増加道を選ぶ」（容量は実数） | ex-ek-nonterminating | 手順が止まらず、流量の極限も最大流の流量でない |
| lem-ek-monotone の「最短の」 | 下の例 | ある頂点の距離が減る |
容量がすべて $1$ の弧 $s\to x_1$、$x_1\to x_2$、$x_2\to x_3$、$x_3\to w$、$w\to t$、$s\to w$ のネットワークを考える。零フロー $f$ では $d_f(x_3)=3$、最短の増加道は $s,w,t$ である。最短でない増加道 $s,x_1,x_2,x_3,w,t$ に沿って増加させたフロー $f'$ では、$s\to w$ が残り、新しく逆向きの残余弧 $w\to x_3$ が現れるので、$d_{f'}(x_3)=2< d_f(x_3)$ である。lem-ek-monotone の証明は、新しく現れた残余弧が最短の道の上の弧の逆向きであることを使っている。
補足
最短の増加道を選ぶ規則は、Ford と Fulkerson も実用上の工夫として述べていたもので、Dinitz も独立に同様の規則を提案した（Eri19 p. 341）。Dinitz の方法も最短の道に沿って流すが、記録の工夫により手間を $|V|^2|A|$ に比例する回数まで減らす（同所の脚注。この記事では証明しない）。増加の回数が容量によらないことは、容量の値の大きさではなく、ネットワークの形だけで手間が決まることを意味する。Edmonds と Karp は、$\varepsilon(P)$ が最大の増加道を選ぶ規則も調べており、容量が整数なら、最大流の流量を $F\ge1$ として、増加の回数はおよそ $|A|\log F$ 回で済む（同書 pp. 340–341。この記事では証明しない）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
