ネットワークフロー ― グラフを流れるもの

フローネットワーク，最大フロー最小カット定理，Ford-Fulkerson法，Edmonds-Karp，Dinic，二部マッチングへの帰着を体系的に解説する．

2026年2月27日

1 フローネットワークの定義

定義 1 (フローネットワーク).

フローネットワークとは，有向グラフ

G = (V, A)

，容量関数

c : A \to R_{\geq 0}

，ソース

s \in V

，シンク

t \in V

（

s \neq = t

）の組

(G, c, s, t)

をいう．

定義 2 (フロー).

フローネットワーク

(G, c, s, t)

上のフローとは，関数

f : A \to R_{\geq 0}

であって次を満たすものをいう：

容量制約：すべての $(u, v) \in A$ に対して $0 \leq f (u, v) \leq c (u, v)$ ．
流量保存則： $s, t$ 以外の各頂点 $v$ に対して $(u, v) \in A \sum f (u, v) = (v, w) \in A \sum f (v, w)$ ．

フローの値を

∣ f ∣ = (s, v) \in A \sum f (s, v) - (v, s) \in A \sum f (v, s)

と定める．

2 残余グラフと増加路

定義 3 (残余グラフ).

フロー

f

に対する残余グラフ

G_{f} = (V, A_{f})

を次で定める：各辺

(u, v) \in A

に対して，

$f (u, v) < c (u, v)$ ならば，残余容量 $c_{f} (u, v) = c (u, v) - f (u, v)$ の順辺 $(u, v) \in A_{f}$ ．
$f (u, v) > 0$ ならば，残余容量 $c_{f} (v, u) = f (u, v)$ の逆辺 $(v, u) \in A_{f}$ ．

定義 4 (増加路).

残余グラフ

G_{f}

における

s

から

t

への路を増加路（augmenting path）という．増加路

P

のボトルネック容量は

bottleneck (P) = min_{(u, v) \in P} c_{f} (u, v)

である．

3 カットと最大フロー最小カット定理

定義 5 (カット).

V

の分割

(S, T)

（

s \in S

，

t \in T

）を $s$ - $t$ カットという．カットの容量を

c (S, T) = (u, v) \in A u \in S, v \in T \sum c (u, v)

と定める．

定理 6 (弱双対性).

任意のフロー

f

と任意の

s

t

カット

(S, T)

に対して

∣ f ∣ \leq c (S, T)

が成り立つ．

証明.

流量保存則を

S

の各頂点について足し合わせると，

∣ f ∣ = (u, v) \in A u \in S, v \in T \sum f (u, v) - (v, u) \in A v \in T, u \in S \sum f (v, u) \leq (u, v) \in A u \in S, v \in T \sum c (u, v) = c (S, T) .

□

定理 7 (最大フロー最小カット定理).

以下の

3

条件は同値である：

$f$ は最大フローである．
$G_{f}$ に $s$ - $t$ 増加路が存在しない．
ある $s$ - $t$ カット $(S, T)$ が存在して $∣ f ∣ = c (S, T)$ ．

証明.

(1) \Rightarrow (2)

：増加路が存在すればフロー値を増やせるので，

f

は最大でない．

(2) \Rightarrow (3)

：

G_{f}

で

s

から到達可能な頂点集合を

S

，

T = V ∖ S

とする．

t \in / S

（増加路がないため）なので

(S, T)

は

s

t

カット．

(u, v) \in A

で

u \in S, v \in T

なら

c_{f} (u, v) = 0

すなわち

f (u, v) = c (u, v)

．

(v, u) \in A

で

v \in T, u \in S

なら

c_{f} (u, v) = 0

すなわち

f (v, u) = 0

．よって

∣ f ∣ = u \in S, v \in T \sum f (u, v) - v \in T, u \in S \sum f (v, u) = c (S, T) .

(3) \Rightarrow (1)

：弱双対性より，任意のフロー

f^{'}

に対し

∣ f^{'} ∣ \leq c (S, T) = ∣ f ∣

なので

f

は最大． □

4 Ford-Fulkerson 法

Ford-Fulkerson 法は， $f = 0$ から出発し， $G_{f}$ で増加路を見つけてフローを増加する操作を繰り返す．

アルゴリズム 1: Ford-Fulkerson 法

Input:

フローネットワーク

(G, c, s, t)

Output:

最大フロー

f

for all

(u, v) \in A

f (u, v) \leftarrow 0

end for

while 残余グラフ

G_{f}

に

s

から

t

への増加路

P

が存在する

δ \leftarrow min {c_{f} (u, v) : (u, v) \in P}

// ボトルネック容量

for all

(u, v) \in P

P

に沿ってフロー更新

(u, v) \in A

f (u, v) \leftarrow f (u, v) + δ

// 順辺

else

f (v, u) \leftarrow f (v, u) - δ

// 逆辺

end if

end for

end while

return

f

注意 8.

容量が有理数ならば Ford-Fulkerson 法は有限回で停止し最大フローを求める．しかし無理数の容量では収束しない例が知られている．また，増加路の選び方によっては整数容量でも非常に遅くなりうる．増加路の探索に BFS を用いる改良版が Edmonds-Karp アルゴリズムである．

5 Edmonds-Karp アルゴリズム

定理 9 (Edmonds-Karp).

増加路を BFS で（辺数最短のものを）選ぶ場合，フローの増加回数は

O (∣ V ∣ \cdot ∣ A ∣)

回以下であり，全体の計算量は

O (∣ V ∣ \cdot ∣ A ∣^{2})

となる．

証明.

鍵となる補題は，各頂点

v

について

G_{f}

における

s

からの BFS 距離

d_{f} (v)

がフロー増加のたびに単調非減少であることである．この補題の下で，ボトルネックとなった辺が次に増加路に含まれるまでに

d_{f}

が少なくとも

2

増加することが示される．

d_{f} (v) \leq ∣ V ∣

なので，各辺がボトルネックになる回数は

O (∣ V ∣)

であり，増加路の総数は

O (∣ V ∣ \cdot ∣ A ∣)

である． □

6 Dinic のアルゴリズム

Dinic のアルゴリズムは，BFS で層別グラフ（level graph）を構成し，その上でブロッキングフローを求めることを繰り返す．

定義 10 (層別グラフ).

G_{f}

において

s

からの BFS 距離

d

を計算し，

d (u) + 1 = d (v)

を満たす辺

(u, v) \in A_{f}

のみを残したグラフを層別グラフ（level graph）

L_{f}

という．

定理 11 (Dinic の計算量).

Dinic のアルゴリズムの計算量は

O (∣ V ∣^{2} \cdot ∣ A ∣)

である．

証明.

各フェーズで層別グラフにおけるブロッキングフローを

O (∣ V ∣ \cdot ∣ A ∣)

で求められる．フェーズごとに

s

から

t

への BFS 距離が厳密に増加するため，フェーズ数は高々

∣ V ∣ - 1

回である． □

注意 12.

単位容量のネットワーク（すべての容量が

1

）では Dinic のアルゴリズムは

O (∣ A ∣ ∣ V ∣)

で動作する．これは二部マッチング（後述）に応用される場合に特に重要である．

7 二部マッチングへの帰着

定理 13 (二部マッチングとフロー).

二部グラフ

G = (X ⊔ Y, E)

の最大マッチング問題は，以下のフローネットワークの最大フロー問題に帰着される：ソース

s

から

X

の各頂点に容量

1

の辺を張り，

Y

の各頂点からシンク

t

に容量

1

の辺を張り，

E

の各辺

(x, y)

に

x \to y

（容量

1

）の弧を与える．

証明.

整数容量のフローネットワークの最大フローは整数フローとして実現できる（整数性定理）．容量

1

の各辺に流量

0

または

1

が対応し，

s

および

t

に接続する辺の容量制約から各頂点は高々

1

本の辺でしか使われない．よって流量

1

の辺集合はマッチングに対応し，フロー値はマッチングの辺数に等しい． □

注意 14.

Dinic のアルゴリズムをこのネットワークに適用すると，Hopcroft-Karp アルゴリズムが自然に得られ，計算量は

O (∣ E ∣ ∣ V ∣)

である．この帰着は König の定理の別証明も与える：最大フロー

=

最小カット（最大フロー最小カット定理）であり，最小カットの容量は最小頂点被覆の大きさに対応するためである．

ネットワークフロー ― グラフを流れるもの

1 フローネットワークの定義

2 残余グラフと増加路

3 カットと最大フロー最小カット定理

4 Ford-Fulkerson 法

5 Edmonds-Karp アルゴリズム

6 Dinic のアルゴリズム

7 二部マッチングへの帰着

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ