9. フロー

本章ではネットワークフローと、その最適化に関する入門的な話題に触れる。最も単純な結果でさえ鉄道やトラックのスケジューリングで直接利用できるために、ネットワークフローはロジスティクスの専門家とって非常に重要な理論である。純粋に数学的な応用も多くある: 特に、本章ではネットワークフローを使って Hall–König のマッチング定理をようやく証明する (この定理と同値だと示してきた Hall の結婚定理や König の定理といった命題も同時に証明される)。

本章の議論は私の講義ノート [17s-lec16] を元にしている。本書で概略しか示していない証明の詳細を確認するときはこの講義ノートが役立つだろう。ただ、[17s-lec16] は単純有向グラフを扱うのに対して本章では多重有向グラフを扱うので、いくらかの変更は必要になる。この変更に難しい部分は基本的に無い。

本章ではネットワークフローの最適化に関する非常に基礎的な話題だけに触れ、最後に (整数値フローに対する) 最大フロー最小カット定理と Hall–König のマッチング定理を証明する。ネットワークフロー理論をさらに勉強したい場合は [ForFul74] (分野の開拓者による古典的教科書) や [Schrij17, Chapter 4], [Schrij03, Part I] を参照してほしい。