書記が数学やるだけ#622 フローネットワークの性質の性質

フローネットワークについては最適化数学でも扱う重要な問題で，今回は性質についてまとめる。

問題

説明

あらかじめ，フローネットワークの制約条件を示す。

最大フロー問題は交通網や送電網の最適化に応用される。

後に示すように，最大フローであれば同時に最小カットでもある。

解答

ソースから出たものは全てシンクに入ることを数式で示しておく。

フロー値の数式をカットで示す。

任意のフローと任意のカットについて，以下の不等式が成り立つ。

これらから，フロー値とカットが一致するならば，それは最大フロー＆最小カットである。

上の具体例を示しておく。実際にどのような経路で最大フローが達成できるかは次回扱う。

本記事のもくじはこちら：