2015/06/15

二部グラフの最大マッチングと増加道

分野: グラフ理論  レベル: 数学オリンピック

グラフが与えられたときに要素数最大のマッチングを求める問題を最大マッチング問題と言う。

マッチングは離散最適化の最も重要な話題の一つです。

最大マッチング問題

・今回は二部グラフの最大マッチング問題を考えます。「グラフ」「二部グラフ」の意味についてはグラフ理論の基礎をどうぞ。

・マッチングとは端点を共有しない枝の集合です。

二部マッチングの例

応用例:左側の頂点を「男性」,右側の頂点を「女性」,「お互い付き合ってもよいペア」に枝を引いたグラフを考え,カップル成立のペア数を最大化する問題。

緑が最大マッチングの一例です。3ペアは可能ですが,4ペアはどうやってもできません。

注:安定結婚問題とは問題設定が異なります。→安定マッチングとGale-Shapleyアルゴリズム

増加道

マッチングにまつわる重要な概念「増加道(増加路)」について説明します。

マッチング $M$ について以下を満たすとき道 $P$ は増加道であるという。

  • $P$ の出発点と到着点がマッチングの端点でない
  • 交互路である($M$ に含まれていない枝と含まれている枝を交互に使う)
増加道

マッチング $M$ に対して増加道 $P$ を見つけることができれば $P$ の枝を「反転」させることで新たに要素数が1大きいマッチング $M’$を作ることができます。

つまり「増加道が存在→より大きなマッチングを作れる」というわけですが,実は逆も成り立つのです!

増加道に関する定理

定理:マッチング $M$ について
増加道が存在しない $\iff$ $M$ は最大マッチング

($\Rightarrow$ の証明,やや難)
最大マッチングでないマッチング $M$ について増加道が存在することを証明する。真の最大マッチングを $M’$とする。

$M$ か $M’$のちょうど片方に属している枝の集合を $M\Delta M’$(対称差と呼ばれる)とする。マッチングの性質より,一つの頂点に隣接している $M\Delta M’$の枝は二本以下なので,$M\Delta M’$はサイクルとパスに分解できる。

サイクルについて:$M$ の枝と $M’$の枝が交互に登場
パスについて:$M’$の枝からはじまり $M’$の枝で終わるパスが存在する($|M’| > |M|$ に注意)。
このパスこそが $M$ の増加道である。

最大マッチングを求めるアルゴリズム

次に,増加道の考え方を使った最大マッチングを求めるアルゴリズムを説明します。

1.適当に(最大でなくてもよい)マッチングを取ってくる
2.今持っているマッチングに対する増加道 $P$ を探して要素数が1大きいマッチングを得る
3.2を繰り返して増加道がなくなったら終了

先ほどの定理のおかげで,最初にどんなマッチングを選んでも最終的に最大マッチングを見つけることができます。

注:増加道を探す操作は例えば幅優先探索で実現できます。

注:二部グラフの最大マッチングは最大流問題の特殊ケースとみなせます。そのため,最大フローを求めるアルゴリズムを使うこともできます(多分こっちのがpopular)。

一般グラフになるとさらに楽しくなります!
分野: グラフ理論  レベル: 数学オリンピック