最大フロー最小カット定理が言っていること ― 双対性の直感

最大フローと最小カットが等しいという驚くべき定理を，「最も弱い部分がボトルネック」という直感から解説します．増加路の考え方，LP 双対性とのつながり，道路やインターネットの帯域幅の実例も紹介します．

2026年2月27日

ネットワークフロー理論の中心にある最大フロー最小カット定理は，グラフ理論で最も美しい結果のひとつです．「送れるフローの最大量」と「ネットワークを切断するのに必要な最小コスト」が一致するというこの定理は，一見まったく異なる2つの量が等しいという双対性の典型例です．

1 フローとは何か ― 水道管のアナロジー

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

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

G = (V, A)

に容量関数

c : A \to R_{\geq 0}

と，2つの特別な頂点

s

（ソース，源泉）と

t

（シンク，排水口）を指定したものです．

水道管のネットワークを想像してください． $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 : (u, v) \in A \sum f (u, v) = w : (v, w) \in A \sum f (v, w)$

フローの値

∣ f ∣

は，

s

から出ていくフローの総量です：

∣ f ∣ = \sum_{w : (s, w) \in A} f (s, w)

．

注意 3.

流量保存則は「中間ノードでは水が溜まらない」ということです．入ってきた分だけ出ていきます．キルヒホッフの法則の流体版です．

2 カットとは何か ― ネットワークの急所

定義 4 (

s

t

カット).

頂点集合の分割

(S, T)

（

s \in S

t \in T

S \cup T = V

）を

s

t

カットと呼びます．カットの容量は

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

です．

カットは「ネットワークを $s$ 側と $t$ 側に分断する線」です．分断するには， $S$ から $T$ に向かうすべての弧を「切断」する必要があり，その容量の合計がカットの容量です．

注意 5 (高速道路のボトルネック).

東京から大阪に物資を輸送するとき，途中のどこか一か所の道路を封鎖すれば輸送を完全に遮断できます．封鎖コストが最小になるような場所 ― それが最小カットです．

3 弱い双対性 ― まず「以下」を理解する

定理 6 (弱い双対性).

任意のフロー

f

と任意の

s

t

カット

(S, T)

に対して

∣ f ∣ \leq c (S, T)

これは直感的に明らかです． $s$ から $t$ にフローを送るには，必ずカット $(S, T)$ を横断する弧を通らなければなりません．そこを通過できるフローは容量以下ですから，フローの値はカットの容量で上から抑えられます．

注意 7.

水道管のアナロジーで言えば，「どんなに効率よく水を流しても，途中の最も細い部分を超えることはできない」ということです．

4 最大フロー最小カット定理 ― 等号の成立

弱い双対性は「 $\leq$ 」を言うだけです．驚くべきことに，等号が達成されます．

定理 8 (最大フロー最小カット定理 (Ford-Fulkerson)).

ネットワーク

(G, c, s, t)

において，

f max ∣ f ∣ = (S, T) min c (S, T)

すなわち，最大フローの値と最小カットの容量は等しくなります．

注意 9 (なぜ等号が成立するのか ― 増加路の直感).

フロー

f

が最大でないとします．すると，

s

から

t

へまだフローを増やせる経路 ― 増加路（augmenting path）― が存在します．増加路がある限り，フローを押し流し続けます．

増加路がなくなったとき何が起こるでしょうか？

s

から残余グラフで到達できる頂点の集合を

S

，残りを

T

とすると，

S

から

T

へ向かうすべての弧は容量いっぱいに使われています（さもなければ増加路が存在するため）．したがって

∣ f ∣ = c (S, T)

が成り立ち，これは同時にフローが最大でカットが最小であることを意味します．

5 LP 双対性 ― より深い視点

最大フロー最小カット定理は，実は線形計画法（LP）の双対定理の特殊ケースです．

注意 10.

最大フロー問題は次の LP として定式化できます：

max ∣ f ∣ subject to 0 \leq f (e) \leq c (e), 流量保存

この LP の双対問題を書き下すと，最小カット問題に帰着します．LP 双対定理（強双対性）が，最大フロー = 最小カットを保証するのです．

これは偶然ではありません．数学の多くの場面で「最大化問題の最適値 = 対応する最小化問題の最適値」という双対性が現れます．最大フロー最小カットは，その最も美しい具体例です．

6 実世界の応用

例 11 (インターネットの帯域幅).

s

をサーバー，

t

をクライアント，弧をネットワーク回線，容量を帯域幅とすると，最大フローはサーバーからクライアントに送れるデータ量の上限を表します．最小カットが「ネットワークのボトルネック」― 帯域幅を制限している箇所を特定します．

例 12 (二部マッチング).

二部グラフの最大マッチング問題は，最大フロー問題に帰着できます．ソースからすべての左頂点に容量1の弧を，右頂点からシンクに容量1の弧を引き，元の辺に容量1を与えれば，最大フロー = 最大マッチングのサイズとなります．

例 13 (プロジェクト選択問題).

利益をもたらすプロジェクト群があり，プロジェクト間に依存関係がある場合，どのプロジェクトを実行するかの最適選択は最小カット問題に帰着できます．

7 まとめ

最大フロー： $s$ から $t$ に送れるフローの最大量
最小カット： $s$ と $t$ を分断するための最小コスト
この2つは常に等しい ― 増加路がなくなったとき，ボトルネック（カット）に到達する
LP 双対性の美しい特殊ケースであり，数学全体に通じる「最大 = 最小」の思想を体現している

次の記事では，二部グラフの世界に足を踏み入れます．なぜ二部グラフでは「すべてが上手くいく」のかを解説します．

グラフ理論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

最大フロー最小カット定理が言っていること ― 双対性の直感

1 フローとは何か ― 水道管のアナロジー

2 カットとは何か ― ネットワークの急所

3 弱い双対性 ― まず「以下」を理解する

4 最大フロー最小カット定理 ― 等号の成立

5 LP 双対性 ― より深い視点

6 実世界の応用

7 まとめ

Share your expertise with the world

More from Folio公式

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

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

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

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