あるところに、これから合コンする予定の男子A,B,Cの３人がいました。
彼らは仲が良く、合コンで狙う女子が被って喧嘩にならないように事前にとある約束をしました。なぜならば合コン中に男子同士で喧嘩するのはみっともないからです。
ある程度場が進んだら、自分の箸を狙っている女子に向け、男子にだけその人が狙っている女の子がわかるようにしました。
そして、その時がやってきました。相対する女子はX,Y,Zの三人
C君はXちゃんに揃えた箸を向けました。
B君は決めかねたのか、YちゃんとZちゃんそれぞれに箸を一本ずつ向けました。
A君はあろうことか、片方の箸をさらに割り、Xちゃん、Yちゃん、Zちゃん全員に一本ずつ向けました。
図にするとこうです。
このとき、男子たちが喧嘩せずに一対一に狙っている女子を決めることができるでしょうか？
この場合は比較的すぐにわかります。
こんな感じで決めれば、喧嘩は起きません。
このようにペアを決めることをマッチングといいます。
今回は人数が少なかったので、簡単に判断できましたが、それが大人数のサークル同士の合コンだったら今みたいにきれいにマッチングができるのかどうかすぐには分かりません。
そんな時にグラフ理論には「ホールの結婚定理」という便利な定理があります。
具体例の整理
先の具体例を扱いやすいように文字を使って置き換えていきましょう。
男の集合を \(V=\{A, B, C\}\) 、女の集合を \(U=\{X, Y, Z\}\) とします。エッジ集合 \(E\) は、次のように男と女のぺアの組み合わせを示します：
$$
E=\{(A, X),(A, Y),(A, Z),(B, Y),(B, Z),(C, X)\}
$$
この例では、男と女の好みがエッジとして表現されます。つま以、男 \(A\) は女 \(X 、 Y 、 Z\) の誰とで もカップルになることができ、男 \(B\) は女 \(Y 、 Z\) とカップルになれます。男 \(C\) は女 \(X\) とカップルに なれます。
このとき、ホールの結婚定理を使って、全ての男と女がカップルになれる（完全マッチングが存在する) かどうかを確認します。
ホールの結婚定理
ホールの結婚定理の主張は次の通りです。
二部グラフ \(G=(V, U, E)\) において、完全マッチングが存在するための必要十分条件は、 すべての部分集合 \(S \subseteq V\) に対して以下の条件が成り立つことです：
$$
|N(S)| \geq|S|
$$
ここで、 \(N(S)\) は部分集合 \(S\) に隣接する頂点の集合を表します。つまり、 \(S\) の各頂点に接続されている \(U\) の頂点の集合です。
この条件を「ホールの条件」と呼びます。この条件が成り立つとき、二部グラフには完全マッチング が存在します。その逆も成り立ちます。
具体例におけるホールの条件の確認
男の集合 \(V=\{A, B, C\}\) のすべての部分集合 \(S\) についてホールの条件を確認します
1. \(S=\{A\}\)
- \(N(\{A\})=\{X, Y, Z\}\)
- \(|N(\{A\})|=3\)
- \(|S|=1\)
-よって、 \(|N(S)| \geq|S|\) が成り立ちます。
2. \(S=\{B\}\)
- \(N(\{B\})=\{Y, Z\}\)
- \(|N(\{B\})|=2\)
- \(|S|=1\)
-よって、 \(|N(S)| \geq|S|\) が成り立ちます。
3. \(S=\{C\}\)
- \(N(\{C\})=\{X\}\)
- \(|N(\{C\})|=1\)
- \(|S|=1\)
-よって、 \(|N(S)| \geq|S|\) が成り立ちます。
4. \(S=\{A, B\}\)
- \(N(\{A, B\})=\{X, Y, Z\}\)
- \(|N(\{A, B\})|=3\)
- \(|S|=2\)
-よって、 \(|N(S)| \geq|S|\) が成り立ちます。
5. \(S=\{A, C\}\)
- \(N(\{A, C\})=\{X, Y, Z\}\)
- \(|N(\{A, C\})|=3\)
- \(|S|=2\)
-よって、 \(|N(S)| \geq|S|\) が成り立ちます。
6. \(S=\{B, C\}\)
- \(N(\{B, C\})=\{X, Y, Z\}\)
- \(|N(\{B, C\})|=3\)
- \(|S|=2\)
-よって、 \(|N(S)| \geq|S|\) が成り立ちます。
7. \(S=\{A, B, C\}\)
- \(N(\{A, B, C\})=\{X, Y, Z\}\)
- \(|N(\{A, B, C\})|=3\)
- \(|S|=3\)
-よって、 \(|N(S)| \geq|S|\) が成り立ちます。
このように、すべての部分集合 \(S \subseteq V\) についてホールの条件が成り立つため、この二部グラフに は完全マッチングが存在することがわかります。
以下このホールの結婚定理を証明します。興味があれば追ってみてください。
証明
「完全マッチングが存在するとき、ホールの条件である不等式を満たす」ことは明らかです。
その逆、「ホールの条件を満たすとき、完全マッチングが存在する」を証明します。
\(|U|\) に関する帰納法で証明する。 \(|U|=1\) のときは自明。
\(|U| \leq k\) のときにHallの結婚定理が成立すると仮定する。 \(|U|=k+1\) であり Hallの条件を満たすグラフ \(G\) でを考える。以下二通りに場合分け。
\(U\) の任意の真部分集合 \(S\) に対して \(|S|+1 \leq|N(S)|\) となる場合。
この時は余裕があるので、適当に変\((u,v)\)を一本選べばよい。そして、頂点\(u\)と\(v\)を除いた二部グラフ\(G^{\prime}\left(U^{\prime}, V^{\prime}\right)\)を考えると、\(G^{\prime}\)においてもHallの条件を満たしている。よって、帰納法の仮定により、\(U^{\prime}\)をカバーするマッチング\(M\)が存在する。全体のマッチングとして\(M\)と\((u,v)\)の和集合を持ってくればよい。
\(|S|=|N(S)|\) を满たす \(S\) の真部分集合 \(A\) が存在する場合。
\(S\)と\(N(S)\)から構成される二部グラフがHallの条件を満たしていることと、帰納法の仮定により、頂点\(S\)をカバーするマッチング\(M_1\)が存在する。そして、そのマッチングは\(S\)と\(N(S)\)の間の完全マッチングである。
よって、残ったグラフ\(G^{\prime}\left(U^{\prime}, V^{\prime}\right)\)に\(U^{\prime}\)をカバーするマッチング\(M_2\)が存在することを証明すればよい。
ここで、\(U^{\prime}\)の部分集合\(S^{\prime}\)を考えてみると、\(G\)がHallの条件を満たしていることから\(|S \cup S^{\prime}| \leq|N(S \cup S^{\prime})|\)である。よって\(S \cup S^{\prime}\)の行先で\(N(S)\)に属さないものが少なくとも\(|S^{\prime}|\)個は存在する。それらは\(S\)とはつながっていないので、すべて\(S^{\prime}\)とつながっている。すなわち\(|N(S^{\prime})| \geq|S^{\prime}|\)。よって、\(G^{\prime}\)もHallの条件を満たすので帰納法の仮定により\(U^{\prime}\)をカバーするマッチング\(M_2\)が存在する。