最大フロー問題

この記事では、ネットワークフロー理論における最大フロー問題について解説します。最大フロー問題とは、ネットワーク上で始点から終点への最大流量を求める問題で、最小カット問題や2部グラフの最大マッチング問題など、様々な問題と密接に関連しています。本記事では、これらの問題の定義、最大フロー最小カット定理、そして代表的な解法アルゴリズムについて詳しく説明します。

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.