12.5 二部グラフとマッチング

第 12.2 節で考えた性的パートナーの関係を表すグラフでは、頂点集合が「男性」と「女性」という二つのグループに分割され、任意の辺が必ず異なるグループに属する二要素を結んでいた。この特徴を持ったグラフは非常によく現れるので、二部グラフ (bipartite graph) という特別な名前が付いている。

定義 12.5.1

\(G\) をグラフとする。\(G\) の頂点集合を \(L(G)\) と \(R(G)\) に分割し、\(G\) の全ての辺が \(L(G)\) に属する頂点と \(R(G)\) に属する頂点を接続するようにできるとき、\(G\) を二部グラフ (bipartite graph) と呼ぶ。\(G\) が二部グラフのとき、\(L(G)\) の要素を \(G\) の左頂点 (left vertex) と呼び、\(R(G)\) の要素を \(G\) の右頂点 (right vertex) と呼ぶ。

つまり二部グラフは図 \(\text{12.2}\) のような形をしている。

12.5.1 二部マッチング問題

二部マッチング問題 (bipartite matching problem) の設定は以前に見たアメリカにおける性的パートナーの問題に似ている: ただし二部マッチング問題では、全ての人を幸せに結婚させることが目標となる。少し考えれば分かるように、この目標は様々な理由で達成不可能となる。最も明らかなのは、男性と女性の人数が異なるなら達成不可能である: 各カップルは男性一人と女性一人からなる。

では、目標が「どの女性も結婚相手が高々 \(1\) 人になるように全ての男性に女性の結婚相手を割り振る」だったらどうだろうか？全ての男性を女性との組にできるだろうか？もちろん、解答は男性の好みを表す二部グラフが持つ特徴に依存する。しかし良いニュースがある: この質問に対する解答を完全に決定する二部グラフの自然な性質が存在する。

一般に、女性の人数は男性の人数以上だと仮定する。また、特定の男性が特定の女性を好むとき、かつそのときに限って辺が存在するような二部グラフの存在を仮定する。今は各男性に対して好みの結婚相手を割り当てる問題¹を考えているので、二部グラフが表す「好む」の関係が対称的である必要はない。女性の視点から見た「好む」の関係は後で考えることにする。例えば、この二部グラフは図 \(\text{12.9}\) のような見た目をしている。

マッチング (matching) は上述の制約を満たす各男性に対する女性の割り当てと定義される。つまり、異なる男性に異なる女性が割り当てられ、全ての男性が相手の女性を好むなら、その割り当てはマッチングである。例えば、図 \(\text{12.9}\) の二部グラフには図 \(\text{12.10}\) に示すマッチングが存在する。

図 12.10可能なマッチングの一つ: 例えば John には Mergatroid が割り当てられる

12.5.2 マッチング条件

Hallホールのマッチング定理 (Hall's matching theorem) と呼ばれる有名な結果は、二部グラフがマッチングを持つための必要十分条件を与える。この結果は非常に有用な数学的ツールであることが判明している。

これから Hall のマッチング定理を「男性」と「女性」の言葉で表明・証明する (その後に数学的な言葉を使ったバージョンを示す)。男性の集合が好む女性の集合を、その集合に属する男性が好む女性全体の集合として定義する。例えば図 \(\text{12.9}\) の設定において、男性の集合 \(\left\{ \text{Tom}, \text{John} \right\}\) が好む女性の集合は \(\left\{ \text{Martha}, \text{Sara}, \text{Mergatroid} \right\}\) である。明らかに、全ての男性に女性を割り当てるには次のマッチング条件 (matching condition) が成り立つ必要がある:

\[ \begin{aligned} \text{[マッチング条件]}\ \ & \text{どの男性の集合も、それが好む女性の集合より大きくない} \end{aligned} \]

例えば、もし特定の \(4\) 人の男性が好む女性が \(3\) 人しかいないならマッチングは存在しない。Hall のマッチング定理は、この条件が十分条件でもあると主張する: つまりマッチング条件が成り立つならマッチングは存在する。

定理 12.5.2

「男性の集合 \(M\) と女性の集合 \(W\) のマッチングが存在する」と「マッチング条件が成り立つ」は同値である。

証明まず、マッチングが存在するときマッチング条件が成り立つと示す。\(M\) の任意の部分集合において、それぞれの男性はその部分集合が好む女性の集合に属する女性一人とマッチする。任意の女性は高々 \(1\) 人の男性とマッチするので、\(M\) の任意の部分集合の要素数は、それが好む女性の集合の要素数以上である。よってマッチング条件は成り立つ。

続いて、マッチング条件を仮定してマッチングが存在すると示す。\(|M|\) に関する強い数学的帰納法を用いる。次の述語 \(P(m)\) を帰納法の仮定とする:

\[ \begin{aligned} P(m) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ & \text{\(M\) の要素数が \(m\) でマッチング条件を満たすなら、} \\ & \text{\(M\) にマッチングが存在する} \end{aligned} \]

ベースケース: \(|M| = 1\) のとき、マッチング条件は唯一の男性が一人以上の女性を好むことを意味する。このとき明らかにマッチングは存在する。

帰納ステップ: \(|M| = m + 1 \geq 2\) のとき、二つの場合を分けて考える。

Case 1:

[要素数 \(m\) 以下の \(M\) の任意の非空部分集合が、それが好む女性の集合より真に大きいとき] この場合は「余裕がある」ので難しくない: 任意に選んだ男性を彼が好む任意の女性とマッチさせて脇に置けば、\(m\) 人の男性と \(|W| - 1\) 人少ない女性が残り、マッチング条件は依然として成り立つ。よって帰納法の仮定 \(P(m)\) から残りの \(m\) 人の男性に対するマッチングも存在すると分かる。

Case 2:

[要素数 \(m\) 以下の \(M\) の非空部分集合であって、それが好む女性の集合と同じ大きさのものが存在するとき] そのような \(M\) の非空部分集合を \(X\) として、\(X\) が好む女性の集合を \(Y\) とする。このとき \(X\) と \(Y\) はマッチング条件を満たすので、強い帰納法の仮定より \(X\) に属する男性と \(Y\) に属する女性のマッチングが存在する。よって後は \(M - X\) に属する男性と \(W - Y\) に属する女性のマッチングが存在すると示せばよい。

\(M - X\) と \(W - Y\) はマッチング条件を満たす。なぜなら、もし \(M - X\) の部分集合 \(M_{0}\) であって、\(M_{0}\) が好む \(W - Y\) に属する女性全体の集合 \(W_{0}\) が \(M_{0}\) より小さいものが存在するなら、\(M\) と \(W\) のマッチング条件の反例となる \(M\) の部分集合が構築できるからである。具体的には、\(M_{0} \cup X\) が反例となる: \(M_{0} \cup X\) が好む \(M\) に属する女性全体の集合は \(W_{0} \cup Y\) であり、これは仮定より \(M_{0} \cup X\) より小さい。従って、強い帰納法の仮定より男性の集合 \(M - X\) と女性の集合 \(W - Y\) のマッチングは存在する。これで \(M\) 全体に対するマッチングが完成した。

両方の場合で男性に対するマッチングが構築できたので、帰納ステップが完了した。よって強い数学的帰納法の原理より定理 12.5.2 は成り立つ。 ■

定理 12.5.2 の証明は二部グラフのマッチングを構築するアルゴリズムを与える。このアルゴリズムはそれほど効率的でないものの、別の効率的なアルゴリズムが知られている。そのため、考えている問題を二部グラフのマッチングを見つける問題に帰着できるなら、その問題は十分効率的に解くことができる。

形式的な議論

続いて定理 12.5.2 を数学的な用語を使って書き換える。こうしておけば「この男性の集合が好む女性の集合は...」などと言わないで済む。

定義 12.5.3

\(G\) をグラフとする。どの二辺も同じ頂点を接続しないような辺の集合 \(M \subseteq E(G)\) を \(G\) のマッチング (matching) と呼ぶ。マッチング \(M\) が被覆 (cover) する頂点とは、\(M\) に属する辺が接続する頂点を意味する。グラフの全頂点を被覆するマッチングを完全マッチング (perfect matching) と呼ぶ。

頂点の集合 \(S \subseteq V(G)\) の隣接頂点 (neighbor) \(N(S)\) とは、辺関係による \(S\) の像を意味する。つまり、次のように定義される:

\[ N(S) ::= \left\{ r \; | \; \text{ある \(s \in S\) で } \langle s\>\text{---}\>r \rangle \in E(G) \right\} \]

次の条件が成り立つとき、\(S\) をボトルネック (bottleneck) と呼ぶ:

\[ |S| > |N(S)| \]

定理 12.5.4[Hall のマッチング定理 (Hall's matching theorem)]

\(G\) を二部グラフとする。「\(L(G)\) を被覆するマッチングが存在する」と「\(L(G)\) の任意の部分集合がボトルネックでない」は同値である。

簡単なマッチング条件

二部グラフ \(G\) のマッチング条件は \(L(G)\) の全ての部分集合が特定の性質を持つことを要求する。一般に、全ての部分集合が何らかの性質を持つことの確認は、それぞれの確認が短い時間で完了するとしても、部分集合の個数が指数的に大きくなるために集合が大きくなるとすぐに手に負えなくなる ── 集合の要素数が \(30\) のとき部分集合は \(10\) 億個を超える。しかし、二部グラフでは頂点の次数を利用する単純な性質でマッチングの存在を保証できる。二部グラフの左頂点の次数が全て右頂点の次数以上であるとき、その二部グラフは次数制約 (degree-constraint) を満たすと言うことにする。より正確には:

定義 12.5.5

二部グラフ \(G\) が次数制約 (degree-constraint) を満たすとは、ある \(d \geq 1\) が存在して、全ての \(l \in L(G)\), \(r \in R(G)\) が次の不等式を満たすことを言う:

\[ \text{deg}(l) \geq d \geq \text{deg}(r) \tag{12.2}\]

例えば、図 \(\text{12.9}\) の二部グラフは \(d = 2\) とした次数制約を満たす: 左頂点は全て \(2\) 個以上の頂点と隣接し、全ての右頂点は \(2\) 個以下の頂点と隣接する。

定理 12.5.6

\(G\) が次数制約を満たす二部グラフなら、\(L(G)\) を被覆するマッチングが存在する。

証明 \(G\) が次数制約を満たすと仮定し、\(S\) を \(L(G)\) の部分集合とする。これから \(S\) が Hall のマッチング定理における条件を満たすと示す。言い換えれば、次の不等式を示す:

\[ |N(S)| \geq |S| \tag{12.3}\]

端点が \(S\) に含まれる辺全体の集合を \(D_{S}\) とする。\(G\) は次数制約を満たすので、\(S\) に属する頂点のそれぞれに対して、それを端点とする辺が少なくとも \(d\) 個ある。つまり次の不等式が成り立つ:

\[ |D_{S}| \geq d \, |S| \]

同様に、\(D_{S}\) に属する任意の辺は定義より \(N(S)\) に属する端点を持つ。\(G\) は次数制約を満たすので、\(N(S)\) に属する頂点に接続する辺の個数は \(d\) 以下である。つまり次の不等式が成り立つ:

\[ d \, |N(S)| \geq |D_{S}| \]

二つの不等式を合わせれば次を得る:

\[ d \, |N(S)| \geq d \, |S| \]

両辺を \(d \geq 1\) で割れば不等式 \(\text{(12.3)}\) を得る。 ■

全ての頂点が同じ次数を持つグラフは正則グラフ (regular graph) と呼ばれ、現実世界の様々な問題で登場する。空でない正則二部グラフは定義より次数制約を満たすので、定理 12.5.6 より完全マッチングを持つ。

二部マッチング問題を男女の結婚を使って説明すると「この左頂点とマッチする右頂点」の代わりに「この男性の結婚相手」と言えて便利である一方で、文章が不穏になる弊害もある。著者らは婚姻が異性間でのみ行われるべきだとは考えていないし、男性が結婚相手の選択権を持つべきだとも考えていない。 ↩︎