マッチング問題への帰着

この問題は次のグラフの問題に読み替えることができます。
「\(2N\) 個の頂点 \(X_1,\ldots,X_N,Y_1,\ldots,Y_N\) を持ち辺のないグラフがある。\(1\leq i \leq N,\ 1 \leq j \leq M\) を満たす各 \((i,j)\) に対して \(X_i\) と \( Y_{A_{i,j}}\) を結ぶ辺を追加する(多重辺あり)。この \(N+N\) 頂点\(NM\) 辺の二部グラフを、\(M\) 組の完全マッチングに分解できるか。可能なら例を挙げよ」

この読み替えでは、頂点 \(X_i\) が元の問題の「\(i\) 行目」を、頂点 \(Y_k\) が元の問題の「数 \(k\)」を表しています。\(1\) つの完全マッチングは 元の問題における \(1\) つの列の割り当てを表し、\(X_i\) と \(Y_k\) を結ぶ辺を\(j\) 組目の完全マッチングに割り当てることは、\(i\) 行目 \(j\) 列目に数 \(k\) を配置することに相当します。

完全マッチングが存在することの証明

もし \(M\) にも \(A_{i,j}\) にも依存せず、必ず完全マッチングが存在するならば、完全マッチングを \(1\) つずつ作っていくことで必ず \(M\) 組の完全マッチングを作ることができます。なぜなら、完全マッチングを \(1\) つ作り使った辺をグラフから取り除くと、\(M\) が \(1\) 小さい問題に帰着され帰納的に構築できるためです。

必ず完全マッチングが存在することは ホールの定理 から従います。

ホールの定理

\(\{X_1,\dots,X_N\}\) と \(\{Y_1,\ldots,Y_N\}\) を部集合とする二部グラフがある。\(X_i\) と直接辺で繋がっている頂点の集合を \(S_i\) とする。このグラフが完全マッチングを持つ必要十分条件は、\(\{1,\ldots,N\}\) の任意の部分集合 \(I\) に対して、\(|\cup_{i\in I}S_i|\geq |I|\) が成り立つことである。

いま考えているグラフがホールの定理の条件を満たしていることを確かめます。

\(\{1,\ldots,N\}\) の任意の部分集合 \(I\) を任意にとります。このとき、\(i\in I\) に対する(多重集合としての) \(S_i\) たちの多重集合としての和集合の大きさは \(|I| M\) です。ここで、その多重集合には同じ元は高々 \(M\) 個しか含まれていないので、集合としての大きさは \(|I|\) 以上になります。よって示されました。

完全マッチングを求める

ホールの定理により完全マッチングが存在することはわかりました。二部グラフの完全マッチングを具体的に \(1\) つ求めることは、フローアルゴリズムを用いて高速にできます。

\(2\) つの頂点 \(S,G\) を追加し、\(S\) から各 \(X_i\) へ、各 \(Y_j\) から \(T\) へ有向辺を張り、既存の辺は \(X_i\) から \(Y_j\) の方向に向きづけします。このグラフで、全ての辺の容量を\(1\) とし、\(S\) から \(T\) へ流量 \(N\) のフローを流したとき、フローが流れる辺が完全マッチングをなします。

計算量は頂点数を \(V\)、辺数を \(E\) として \(O(V^{0.5}E)\) です。

「完全マッチングを \(1\) 組求め、使った辺を取り除く」を \(M\) 回繰り返すことで、グラフを \(M\) 組の完全マッチングに分解することができます。計算量は \(O(\sum_{m\leq M} N^{0.5}(Nm))=O(N^{1.5}M^2)\) となり、十分高速に動作します。

より高速な解法

グラフをマッチングに分解する問題は、辺彩色問題だと思うことができます。正則二部グラフの辺彩色は\(O(NM\log NM)\) で求められることが知られているので、この問題もその計算量で解けます。

具体的なアルゴリズムについては、例えばこちらの記事を参照してください。

37zigenさんによる記事