二部グラフの最大マッチングを求めるアルゴリズム

グラフ競プロ, フロー, 最大フロー, 二部グラフ, 最大マッチング, マッチング

アルゴリズム

二部グラフの最大マッチングを求めるアルゴリズム:

  1. 二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G’\) を作る
    • \(G\) にソース \(s\) とシンク \(t\) を加える
    • \(s\) から \(L\) のすべての頂点に対して容量 1 の有向辺を加える
    • \(R\) のすべての頂点から \(t\) に対して容量 1 の有向辺を加える
    • \(L\) の頂点と \(R\) の頂点を結ぶ辺は、\(L\) から \(R\) への容量 1 の有向辺とする
  2. \(G’\) の最大フローを求めると、その流量は最大マッチングのサイズと一致する

※ マッチング \(M\) は、\(|M| = |f|\) となる1つの整数フロー \(f\) に対応します
※ マッチングの各ペアは、ソースからシンクへの流量1の部分的なフローに対応します
※ 最大フローを求めるアルゴリズムの代表例としては、Ford-Fullkerson法などがあります。

二部グラフ \(G=(L \cup R, E)\)
フローネットワーク \(G’\) での最大フロー

計算量

  • \(O(|V||E|)\)

\(G’\) の最大フロー \(f^*\) の値は \(|f^*| = O(\min(L, R))\) 程度です。最大フローを求めるのにFord-Fullkerson法を用いれば、計算量は \(O(|f^*||E|)\) になります。

C++ での実装例

AOJ GRL_7_A Bipartite Matching を解くコードです。最大フローを求めるのにFord-Fullkerson法を用いています。

アルゴリズムの正当性

  • \(G\) でのマッチング \(M\) が最大マッチング \(\Leftrightarrow\) \(M\) に対応する \(G’\) での整数フロー \(f\) が最大フロー

であることが示せれば良いです。

準備

以下の2つを用いて証明を行います。

マッチングの整数フローの対応

\(G\) のマッチング \(M\) が存在するなら、\(G’\) において \(|f|=|M|\) となる整数フロー \(f\) が存在する。
逆に\(G’\) において整数フロー \(f\) が存在するなら、\(G\) において \(|f|=|M|\) となるマッチング \(M\) が存在する。

整数性定理

容量関数 \(c\) が整数値しか取らないなら、最大フロー \(f^*\) の値 \(|f^*|\) が整数値になり、任意の頂点 \(u,v\) について \(f(u,v)\) の値も整数値になる。

証明の概要

必要条件と十分条件に分けて示しましょう。

まずは \(G\) でのマッチング \(M\) が最大マッチングのときを考えます。\(M\) に対応する整数フロー \(f\) が存在するので、これが最大フロー \(f^*\) でないと仮定して矛盾を導けば良いです。
\(f^*\) は整数性定理から整数フローとなります。よってこれに対応するマッチング \(M^*\) を考えると、\(|M^*| = |f^*| > |f| = |M|\) となり \(M\) が最大マッチングであることと矛盾します。

逆も同様に示すことができます。

練習問題