最大フロー問題

最大フロー問題：ネットワークにおける流量最大化

最大フロー問題とは、ネットワーク上の始点から終点への最大流量を求める問題です。ネットワークは、ノード（頂点）とそれらを繋ぐエッジ（辺）で構成され、各エッジには容量（通過できる流量の最大値）が設定されています。最大フロー問題の目的は、始点から終点への流量を最大化するフロー（各エッジを通過する流量の割り当て）を見つけることです。

問題の定式化

より厳密には、最大フロー問題は有向グラフG(V, E)上で定義されます。ここで、Vはノードの集合、Eはエッジの集合です。各エッジ(u, v) ∈ Eには、容量c(u, v)が与えられています。始点sと終点tが指定され、各エッジ(u, v)を通過する流量をf(u, v)とすると、最大フロー問題は次の制約条件の下で、始点から終点への総流量Σ_{v∈V} f(s, v)を最大化する問題となります。

容量制約: 各エッジ(u, v)について、0 ≤ f(u, v) ≤ c(u, v)
フロー保存則: 各ノードu (sとtを除く)について、Σ_{v∈V} f(u, v) = Σ_{v∈V} f(v, u) （流入量 = 流出量）

最小カット問題との関係

最大フロー問題と密接に関連する問題として、最小カット問題があります。最小カット問題とは、有向グラフにおいて、始点sと終点tを分離するような辺の集合（カット）のうち、辺の容量の総和が最小となるものを求める問題です。

驚くべきことに、最大フローの値は最小カットの容量に等しいことが知られています。これを最大フロー最小カット定理といいます。この定理は、最大フロー問題を解く上で重要な理論的基盤となります。

2部グラフの最大マッチング問題

最大フロー問題の応用として、2部グラフの最大マッチング問題があります。2部グラフとは、ノードの集合が2つの互いに素な集合に分割でき、エッジが異なる集合のノード間にのみ存在するグラフです。最大マッチングとは、どの2つのエッジも共通のノードを持たないようなエッジの集合のうち、最大となるものを指します。

2部グラフの最大マッチング問題は、適切なネットワークを構成することで最大フロー問題として定式化し、解くことができます。

解法アルゴリズム

最大フロー問題を解くためのアルゴリズムは多数存在します。代表的なものとしては、以下のものが挙げられます。

フォード・ファルカーソン法: 最大フロー最小カット定理に基づいたアルゴリズム。シンプルですが、最悪ケースでは効率が悪い。
エディンカーン・カープ法: フォード・ファルカーソン法の改良版。効率が向上している。
プッシュ・リラベル法: より効率的なアルゴリズム。

これらのアルゴリズムは、それぞれ異なるアプローチを用いて最大フローを求めます。より高度なアルゴリズムも開発されており、 Goldberg and Tarjan (1988) などの論文で詳細な解説がされています。

参考文献

Sleator, D. D., & Tarjan, R. E. (1983). A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3), 362–391.
Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM, 32(3), 652–686.
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum-flow problem. Journal of the ACM, 35(4), 921–940.
* Cheriyan, J., & Mehlhorn, K. (1999). An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters, 69(5), 239–242.

もう一度検索