ei1333's page

二部グラフの最大マッチング(Bipartite-Matching)

説明

グラフ $G=(V, E)$ において, $V$ が $2$ つの部分集合 $X$ と $Y$ に分割され, $E$ のどの辺も一方の端点は $X$ に, もう一方の端点は $Y$ に属しているとき, $G$ を 二部グラフ という.

グラフ $G=(V, E)$ において, $M$ が $E$ の部分集合でかつ $M$ のどの $2$ 辺も共通の端点をもたないとき, $M$ を $G$ の マッチング といい, 辺の本数が最大であるマッチングを 最大マッチング という.

ここでは, 二部グラフの最大マッチングを最大流のアルゴリズムを利用して求める。

計算量

$O(VE)$

実装例

何かと便利なので, 生存しているとき true を入れる alive 配列を追加してある.

応用 1: 最小頂点被覆 = 最大マッチング

グラフ $G = (V, E)$ において, 各辺 $e$ について端点のいずれか少なくとも一方が $V'$ に含まれるような $V$ の部分集合 $V'$ のうち, $V'$ の頂点数が最小であるものを 最小頂点被覆 という.

Königの定理(最大マッチング最小被覆定理) では, 二部グラフについて最大マッチングの本数と最小被覆の頂点数は等しいことを示している.

応用 2: DAGの最小パス被覆 = V - 最大マッチング

グラフ $G = (V, E)$ において, そのグラフの全ての頂点が $1$ つ以上のパスに含まれるようなパスの集合をを パス被覆 という.

特に, パス被覆の中でパスの数が最小のものを 最小パス被覆 という.

DAGの最小パス被覆は二部グラフの最大マッチング問題に帰着でき, 容易に解くことができる. 具体的には頂点を倍長して, 始点を左側に, 終点を右側に配置したグラフを考える. まず $V$ 本のパスがあれば被覆できることは自明. このグラフのマッチング一組に対して必要なパスを $1$ つ減らすことができるため, $V - $ (二部グラフの最大マッチング) が最小パス被覆となる.

参考: DAGのパス被覆の問題 - antaの競技プログラミング練習日記

応用 3: 辞書順最小

ある最大マッチングの状態から, 貪欲に上の頂点から順にフローを押し戻してより番号が小さいものが使えないか試していくことで辞書順最小の最大マッチングを求めることができる. (事前に辺について辞書順にソートしておく必要がある.)

応用 4: 押し戻す, 加える

二部グラフが変化するときについて, 変化が微妙なときは現在のマッチングの状態をもとに, それを押し戻したり新たに加えたりして少ない計算量で修正することが出来る.

以下では頂点追加と削除を実装している.

参考: Hopcroft-Karp

$O(E \sqrt V)$ のアルゴリズムもある. 微妙に速い。

参考: Hopcroft–Karp algorithm - wikipedia