順方向の辺（行き先、容量、逆辺のインデックス）

最大フロー問題を完全攻略！基礎から最小カット定理・実装まで徹底解説

競技プログラミングの難所として立ちはだかるだけでなく、通信トラフィック制御や物流ネットワークの最適化、さらにはシフトスケジューリングまで、社会基盤の裏側を支え続ける重要概念が「最大フロー問題」です。一見すると複雑な数理モデルに見えますが、本質は「スタート地点からゴール地点へ、パイプの太さの限界を守りながら一度に流せる水の最大量を求める」という極めて直感的なパズルに他なりません。

しかし、いざ実装や証明に踏み込むと「なぜ逆向きの辺が必要なのか」「最小カットとどう結びつくのか」といった疑問に直面し、挫折してしまう学習者が後を絶ちません。本稿では、ネットワークフローの基本概念から残余グラフの直感的メカニズム、代表的アルゴリズムの計算量比較、実務に役立つPythonコードまで、エンジニアが押さえるべき急所を体系的に整理してお届けします。

📌 【この記事の重要ポイントまとめ】

• 要点1：最大フロー問題の本質は「残余グラフ上でボトルネックを特定し、流せる限り水を送り込む」ことにある。
• 要点2：最大フロー最小カット定理により、「最大流量」と「ネットワークを寸断する最小コスト」は完全に一致する。
• 要点3：フォード・ファルカーソン法、エドモンズ・カープ法、ディニツ法を計算量と用途に応じて使い分けることが攻略の鍵。

【基礎編】最大フロー問題とは何か？ネットワーク構造と基本用語をわかりやすく解説

最大フロー問題（Maximum Flow Problem）を理解する第一歩は、対象となるネットワークを「有向グラフ（矢印付きの点と線）」として捉えることです。水道管のネットワークをイメージすると構造がすっきりと見えてきます。

このグラフには、必ず以下のような固有の要素が存在します。

• 頂点（ノード）：水の中継地点や分岐点。
• 始点（ソース / $S$）：水が無限に湧き出るスタート地点。
• 終点（シンク / $T$）：水が流れ込む最終ゴール地点。
• 有向辺（エッジ）：水が流れるパイプ。向きが決まっており、逆流は許されません。
• 容量（キャパシティ / $c(e)$）：そのパイプに1秒間に流せる水の最大限界量。
• 流量（フロー / $f(e)$）：実際にそのパイプを流れている水の量（$0 \le f(e) \le c(e)$）。

ルールはシンプルで、「各パイプの容量を超えてはならない（容量制約）」こと、そして始点と終点以外のすべての中継地点において「入ってくる水の総量と出ていく水の総量が完全に等しくなければならない（流量保存則）」という2点のみです。この制約を満たした上で、始点 $S$ から終点 $T$ へ同時に送り込める水の総量を最大化するのが最大フロー問題の目的です。

なぜ「最大流＝最小カット」なのか？驚くほど美しい最大フロー最小カット定理の直感的理解

ネットワークフロー理論における最大の白眉が、1956年にレスター・フォードとデルバート・ファルカーソンによって証明された「最大フロー最小カット定理（Max-Flow Min-Cut Theorem）」です。この定理は、グラフ理論における「双対性（表裏一体の関係）」の美しさを鮮やかに示しています。

まず「カット」とは、頂点集合を始点 $S$ を含むグループ（$S$ 側）と、終点 $T$ を含むグループ（$T$ 側）の2つに完全に分断することを指します。このとき、$S$ 側のグループから $T$ 側のグループへ向かうパイプをすべて切断すれば、$S$ から $T$ への水の供給は完全に止まります。切断したパイプの容量の合計を「カットの容量」と呼び、考えられるすべての分割方法の中で最も合計容量が小さくなる境界線を「最小カット」と呼びます。

直感的に考えてみましょう。パイプ網のどこかに必ず「ネットワーク全体のボトルネック」となる最狭のくびれ部分が存在します。どんなに他のパイプを太くしても、この最狭部以上の水を流すことは不可能です。最大フロー最小カット定理が主張しているのは、まさに「流せる最大の水の量（最大流）は、ネットワークを寸断するために破壊すべきパイプ容量の最小合計（最小カット）と完全に一致する」という事実です。

この定理があるおかげで、「流量を最大化する問題」を「境界を最小化する問題」に言い換えて解くことが可能になり、画像処理の領域分割（Graph Cuts）やプロジェクト選択問題など、一見フローとは関係のない最適化問題へ応用する道が開かれています。

【解法比較】フォード・ファルカーソン法からディニツ法まで！アルゴリズムの仕組みと計算量

最大フロー問題を解くアルゴリズムは、歴史とともに計算効率の改善が進められてきました。どの解法も共通して用いる中核概念が「残余グラフ」と「増加道（Augmenting Path）」です。

残余グラフとは、「あとどれだけ水を増やせるか」を示す順方向の空き容量辺に加え、「すでに流した水をキャンセル（押し戻し）できる権利」を意味する逆方向の辺（逆辺）を張った仮想的なグラフです。この残余グラフ上で $S$ から $T$ への経路（増加道）を探索し、見つかった経路の中で最も細いパイプの空き容量分だけ水を流す——この操作を増加道がなくなるまで繰り返します。

アルゴリズム名	探索手法	時間計算量	特徴と適用シーン
フォード・ファルカーソン法 (Ford-Fulkerson)	深さ優先探索 (DFS)	$O(F \cdot |E|)$ ※$F$は最大流量	実装が極めて平易。ただし容量が大きい場合や実数容量では計算回数が爆発するリスクあり。
エドモンズ・カープ法 (Edmonds-Karp)	幅優先探索 (BFS)	$O(|V| \cdot |E|^2)$	最短辺数の増加道を選ぶことで、流量 $F$ に依存しない強多項式時間を達成。
ディニツ法 (Dinic's Algorithm)	BFS（レベルグラフ構築） ＋ DFS（ブロッキングフロー）	$O(|V|^2 \cdot |E|)$ ※二部マッチング時は $O(|E|\sqrt{|V|})$	競技プログラミングのデファクトスタンダード。実用上、理論値より遥かに高速に動作。

近年の競技プログラミング（AtCoderやCodeforcesなど）の実戦では、最悪ケースでも安定したパフォーマンスを発揮するディニツ法（Dinic法）をライブラリ化しておくのが定石となっています。

競技プログラミングや実務で必須！「二部マッチング問題」への鮮やかな応用テクニック

最大フロー問題の威力が最も分かりやすく体感できるのが、二部マッチング問題（Bipartite Matching）への帰納です。「仕事と作業員のマッチング」「就活生と採用枠の割り振りに伴う最適ペア決め」など、実社会で頻発する課題の多くがこのモデルに帰着されます。

二部グラフにおいて、互いに重なり合わないペアを最大いくつ作れるかという問題は、以下のようにネットワークを構築するだけで、そのまま最大フロー問題として解くことができます。

1. 仮想の始点 $S$ と終点 $T$ を新設する。
2. 始点 $S$ から左側のグループ（例：作業員）の各頂点へ、容量1の有向辺を張る。
3. ペア形成が可能な左右の頂点間に、容量1（または無限大）の有向辺を張る。
4. 右側のグループ（例：仕事）の各頂点から終点 $T$ へ、容量1の有向辺を張る。
5. このネットワークで $S$ から $T$ への最大フローを計算する。

すべての辺の容量が「1」であるため、1つの頂点に流れる流量は最大でも1に制限されます。その結果、求められた最大流量がそのまま「最大マッチング数」となり、水が流れたパイプの組み合わせが「最適なペア一覧」を表すことになります。この変換手順は、ネットワークフロー最適化の基本パターンとして必ず習得しておきたい技術です。

【コピペで動く】ネットワークフロー最適化を実現するPython実装サンプル

ここでは、実務やコンテストで即戦力となるディニツ法（Dinic's Algorithm）のPython実装を紹介します。クラス形式で簡潔にまとめており、グラフ構築から最大フローの計算までスムーズに実行可能です。

from collections import deque class Dinic: def init(self, n): self.n = n self.graph = [[] for _ in range(n)] self.level = [-1] * n self.iter = [0] * n def add_edge(self, from_node, to_node, cap): forward = [to_node, cap, None] # 逆方向の辺（初期容量は0） backward = [from_node, 0, forward] forward[2] = backward self.graph[from_node].append(forward) self.graph[to_node].append(backward) def _bfs(self, s, t): self.level = [-1] * self.n self.level[s] = 0 queue = deque([s]) while queue: v = queue.popleft() for to_node, cap, rev in self.graph[v]: if cap > 0 and self.level[to_node] < 0: self.level[to_node] = self.level[v] + 1 queue.append(to_node) return self.level[t] >= 0 def _dfs(self, v, t, f): if v == t: return f for i in range(self.iter[v], len(self.graph[v])): self.iter[v] = i edge = self.graph[v][i] to_node, cap, rev = edge if cap > 0 and self.level[v] < self.level[to_node]: d = self._dfs(to_node, t, min(f, cap)) if d > 0: edge[1] -= d # 順方向の容量を減らす rev[1] += d # 逆方向の容量を増やす return d return 0 def max_flow(self, s, t): flow = 0 INF = float('inf') while self._bfs(s, t): self.iter = [0] * self.n while True: f = self._dfs(s, t, INF) if f == 0: break flow += f return flow # --- 使用例 --- if name =="main": # 頂点数 4 (0: 始点S, 1: 中継A, 2: 中継B, 3: 終点T) dinic = Dinic(4) dinic.add_edge(0, 1, 2) # S -> A (容量 2) dinic.add_edge(0, 2, 1) # S -> B (容量 1) dinic.add_edge(1, 2, 1) # A -> B (容量 1) dinic.add_edge(1, 3, 1) # A -> T (容量 1) dinic.add_edge(2, 3, 2) # B -> T (容量 2) result = dinic.max_flow(0, 3) print(f"最大流量: {result}") # 出力: 最大流量: 3 

この実装のポイントは、_bfs で距離階層（レベルグラフ）を作り、最短ホップ数で到達できる辺だけを _dfs で探索している点です。さらに self.iter で探索済みの辺をスキップする仕組み（ポインタ走査）により、無駄な探索を徹底的に排除しています。

【最大フロー問題】に関するよくある質問（FAQ）

Q1：残余グラフで「逆向きの辺」を張る理由は何ですか？
A1：一度流してしまったフローを「後からやり直す（キャンセルする）」ためです。貪欲法のように手当たり次第に水を流すと、後からより最適な流し方が見つかった際に対応できなくなります。逆辺に容量を持たせることで、「すでに流した分を押し戻して別の経路に迂回させる」選択肢を残すことができます。

Q2：エドモンズ・カープ法とディニツ法はどちらを使うべきですか？
A2：基本的にはディニツ法の一択です。エドモンズ・カープ法は教育用として非常に優れていますが、計算量が $O(|V||E|^2)$ とやや重く、競技プログラミングの厳しい制限時間（2秒など）ではTLE（時間切れ）になるケースがあります。ディニツ法は実装量もそこまで増えず、$O(|V|^2|E|)$ かつ実践では驚異的な速度を誇ります。

Q3：最小費用流問題とは何が違うのですか？
A3：最大フロー問題が「パイプの太さの限界内で最大流量を求める」のに対し、最小費用流問題は「各パイプを水が通る際にかかるコスト（輸送費など）が存在し、指定された流量を達成するための最小合計コストを求める」問題です。最大フロー問題の発展系であり、解法にはプライマル・デュアル法やベルマン・フォード法を組み合わせたアプローチが用いられます。

まとめ：ネットワークフロー最適化を武器にアルゴリズム力を引き上げる

最大フロー問題は、一見すると難解な数理アルゴリズムに感じられますが、「残余グラフでボトルネックを探す」「逆辺で流量を調整する」という根本の仕組みさえ掴んでしまえば、驚くほど見通しが良くなります。さらに最大フロー最小カット定理の理解を深めることで、複雑な制約条件をグラフの切断問題として定式化する高度なモデリング能力が身につきます。

まずは手元のエディタでディニツ法の実装を動かし、二部マッチングなどの代表的な問題に適用してみることから始めてみてください。グラフアルゴリズムを自在に操る強力な武器として、日々のコーディングや設計に活用していきましょう。 （出典: 最大 フロー 問題（Yahoo!ニュース））