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

二部グラフにおける最大マッチング問題について,問題の意味とアルゴリズムをわかりやすく紹介します。

二部グラフ・マッチングとは

  • グラフとは,点の集合と枝の集合からなる「つながり方」を表すモデルです。

  • 二部グラフとは,点が 22 グループにわかれていて,同じグループ間はつながっていないようなグラフです。→グラフ理論の基礎

二部グラフの例

二部グラフの例

頂点が青と赤の2グループに分かれています。青同士、赤同士は枝で結ばれていないので二部グラフです。

  • マッチングとは,端点を共有しない枝の集合です。
  • グラフが与えられたときに要素数最大のマッチングを求める問題を最大マッチング問題と言います。マッチングは離散最適化の最も重要な話題の一つです。
最大マッチング問題の例

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

二部マッチングの例

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

増加道

最大マッチングを求めるアルゴリズムを説明するために必要な「増加道(増加路)」について説明します。

増加道の定義

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

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

例えば,下図左の「紫三角を端点とする長さ5の太線の道」は増加道です。

増加道

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

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

増加道に関する定理

定理

マッチング MM について,
増加道が存在しない     \iffMM は最大マッチング

増加道が存在すれば最大マッチングではないので,対偶を取ると \Leftarrow が成立します。\Rightarrow の対偶「最大マッチングでないなら増加道が存在する」を証明します。

証明

最大マッチングでないマッチング MM について増加道が存在することを証明する。真の最大マッチングを MM' とする。

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

  • サイクルについて: MM の枝と MM' の枝が交互に登場

  • パスについて: MM' の枝からはじまり MM' の枝で終わるパスが存在する(M>M|M'| > |M| に注意)。

このパスこそが MM の増加道である。

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

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

  1. 適当に(最大でなくてもよい)マッチングを取ってくる

  2. 今持っているマッチングに対する増加道 PP を探して要素数が1大きいマッチングを得る。増加道を探す操作は,例えば幅優先探索でできる。

  3. 2を繰り返して増加道がなくなったら終了する

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

注:二部グラフの最大マッチングは最大流問題の特殊ケースとみなせます。そのため,最大フローを求めるアルゴリズムを使うこともできます。おそらく最大フローを使う方が有名ですが,増加道の考え方がおもしろので紹介しました。

ちなみに,最大マッチング問題と似たような問題として,安定結婚問題があります。→安定マッチングとGale-Shapleyアルゴリズム

一般グラフになるとさらに楽しくなります!