今回は、グラフ理論分野における超有名定理、最大流最小カット定理の証明について書いてみようと思います。 最大流最小カット定理は証明方法がいくつかありますが、今回は線形計画法の双対を用いた証明を紹介します。この証明方法はFord-Fulkersonのアルゴリ…