書記が数学やるだけ#625 二部グラフの最大マッチング

二部グラフはマッチングを考える上で基本となる。

問題

説明

増加道という概念を用いて，最大マッチングを示していく。今回は増加道を用いた解法を示すが，他にも最大流問題を用いた解法もよく用いられる。

解答

増大道を含まないならば最大マッチングを示すには，最大マッチングでないものに増加道が一つ足せば最大マッチングであることを示す。

最大マッチング問題と最小被覆問題は双対の関係にある。

では実際に最大マッチングを求めてみる。

飽和していない頂点に対し，マッチしていない頂点があれば，その2つをマッチングする。

マッチしていない頂点がない場合，そのマッチングからたどって増加道を探す。

増加道についてマッチングを反転させることで，1つ多いマッチングを得る。これを繰り返して，増加道がなくなったら，それが求める最大マッチングである。

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