ネットワークフロー

あるいはフローネットワーク

色んな問題

最大流

「始点（ソース）から終点（シンク）に最大でどれくらい同時に流せますか」って問題

最小カット

「始点（ソース）から終点（シンク）に流せなくするには、最小でどれくらいの総量切ればいいですか」って問題

最大流と同じになる（双対ってやつ）

最大マッチング

「辺で繋がってる頂点で2人組を作るとき、最大で何組作れますか」って問題

二部グラフならいい感じに始点組と終点組に分けて最大流で求まる。

（二部じゃなくても効率的なアルゴリズムが存在するらしい。）

最小点被覆

「できるだけ少ない頂点を選んで、すべての辺がその頂点のどれかと繋がってるようにしましょう」って問題

二部グラフなら最大マッチングと同じ（ケーニヒの定理）

辺被覆

「頂点をいくつかのパスで埋め尽くそう」みたいな問題

二部グラフの最大マッチングに帰着できる。

反鎖

「頂点の集合で、どの2つを持ってきても辿り着けるパスがないようなもの」

辺被覆の最小と一致する（ディルワースの定理）

まとめ

← 最大マッチング = 最小点被覆

← 最小辺被覆 = 最大反鎖

参考

蟻本

競技プログラマー ハンドブック

問題例