【グラフ理論】ホールの結婚定理の応用は？ 日常的なものから群論などへの応用などを解説
こんにちは！半沢です！
今回の記事ではグラフ理論におけるホールの結婚定理(Hall’s marriage thoerem)の応用について解説したいと思います。
ホールの結婚定理がトランプなどの日常的な例から群論などの大学数学にも応用できる優れモノであることを，この記事に詰め込みました。
そもそものホールの結婚定理を知りたい方は，こちらの記事で解説していますので必要に応じて参照してください。
ぜひ面白さと奥深さを味わってください。
重み付き多重\(\,2\,\)部グラフへの応用
まずは重み付き多重\(\,2\,\)部グラフへの応用を見ていきましょう。
主張
命題\(\,1\,\)
\(\,w\,\)を正の実数とする。
全ての頂点に対して隣接する辺の重みの総和が\(\,w\,\)となる，
重み付き多重\(\,2\,\)部グラフは完全マッチングを持つ。
重みつきグラフにおいて全ての辺の重みを\(\,1\,\)とすると，
ある点に「隣接する辺の重みの総和」とはその点の次数に変わりないので，
以下の系\(\,1\,\)が得られます。
系\(\,1\,\)
\(k\,\)を\(\,1\,\)以上の整数とする。
\(k\text{-}\)正則多重\(\,2\,\)部グラフは完全マッチングを持つ。
この命題\(\,1\,\)はホールの結婚定理を用いることで簡単に証明できます。
証明は命題\(\,1\,\)のトランプへの応用例の後に載せているので，そちらをご覧ください。
この命題\(\,1\,\)はトランプに応用できるだけでなく，実はバーコフ-フォンノイマンの定理の証明にも使えます。
そのことに関しては改めて記事にする予定ですので，そちらをお待ちください。
トランプへの応用
前節の命題\(\,1\,\)(系\(\,1\,\))をトランプへと応用すると，次のことが言えます。
ジョーカーを抜いた\(\,52\,\)枚のトランプから，カード\(\,4\,\)枚からなる山を\(\,13\,\)個適当に作る。
このとき各山から，うまく\(\,1\,\)枚ずつ取り出すことで\(\,1\sim 13\,\)のカードを揃えることができる。
手元のトランプを使ってやってみると面白いです。
実際に私がやってみたところ次の表のようになりました。
確かに赤で示した数字たちが綺麗に\(\,1\sim13\,\)となっていますね。
さてここからは，
「うまく取れば\(\,1\sim 13\,\)のカードを揃えることができる」ことを命題\(\,1\,\)(系\(\,1\,\))を用いて示していきましょう。
問題の状況を\(\,2\,\)部グラフのマッチングに持ち込むために，
次のような\(\,2\,\)部グラフ\(\,G=G(X,Y)\,\)を構成します。
\(X=\{\,\)13個の山\(\,m_1,m_2,\cdots,m_{13}\}\,\)：山の集合
\(Y=\{1,2,\ldots,13\}\)：カードの数の集合
辺\(\,m_ki\,\,(m_k\in X,i\in Y)\,\)を描く
\(\Leftrightarrow\,\)山\(\,m_k\,\)の中に\(\,i\,\)のカードがある。
例えば先程の私の例でやってみると次のようなグラフが出来上がります。
このグラフ\(\,G\,\)は\(\,4\text{-}\)正則\(\,2\,\)部多重グラフとなります。
なぜなら重複も認めると山\(\,m_k\,\)にあるカードは丁度\(\,4\,\)枚であり，
また数字\(\,i\,\)が書かれたカードも丁度\(\,4\,\)つの山に含まれるからですね。
よって命題\(\,1\,\)(系\(\,1\,\))より\(\,G\,\)は完全マッチング\(\,M\,\)を持つことが分かります。
そのため山\(\,m_k\,\)から，その山に\(\,M\,\)によって対応する数字が書かれたカードを取り出していくことで\(\,1\sim 13\,\)のカードを揃えることができます。
したがって題意は示されました。\(\quad\square\)
上の証明によって“うまく”取れば\(\,1\sim 13\,\)のカードを揃えることができるのは分かりました。
しかし実際にやってみた方は分かると思うのですが，この“うまい”取り方を見つけるのは難しいです。
これについては証明のようにトランプを\(\,2\,\)部グラフに対応させた後，
\(2\,\)部グラフの最大マッチングを見つけるアルゴリズムによって“うまい”取り方を見つけることができます。
必要に応じて参照してください。
証明
ここでは前々節で述べた命題\(\,1\,\)の証明をしましょう。
命題\(\,1\,\)
\(\,w\,\)を正の実数とする。
全ての頂点に対して隣接する辺の重みの総和が\(\,w\,\)となる，
重み付き多重\(\,2\,\)部グラフは完全マッチングを持つ。
命題\(\,1\,\)の前提を満たす重み付き多重\(\,2\,\)部グラフを\(\,G=G(X,Y)\,\)とおきましょう。
まず\(\,2\,\)つの部集合の点の数が同じ，つまり\(\,|X|=|Y|\,\)であることを確認しましょう。
これはグラフ\(\,G\,\)の辺の重みの総和\(\,S\,\)を，それぞれ\(\,X,Y\,\)の点を中心に数える数え方によって
\(S=w|X|=w|Y|\)
となることから，\(w\not= 0\)で割って\(\,|X|=|Y|\,\)を得ることができます。
\(|X|=|Y|\,\)より，もし仮に\(\,G\,\)が\(\,X\,\)の全ての頂点を飽和するマッチングを持つとすると，それは完全マッチングになります。
そのためホールの結婚定理より\(\,G\,\)が完全マッチングを持つことを示すには
「\(\,X\,\)の任意の部分集合\(\,S\not=\emptyset\,\)について\(\,|N_G(S)|\geq |S|\,\)が成り立つ」ことを示せばよいです。
そこで\(\,X\,\)の任意の部分集合\(\,S\not=\emptyset\,\)について考えましょう。
このとき，もちろん\(\,S\,\)につながっている辺は\(\,N_G(S)\,\)につながっている辺なので(下図参照)，次の式変形が成り立ちます。
つまり\(\,w|N_G(S)|\geq w|S|\,\)で\(\,w\gt 0\,\)より，\(\,|N_G(S)|\geq |S|\,\)が示されました。
したがって題意は示されました。\(\quad\square\)
群論への応用
続いてホールの結婚定理の群論への応用を見ていきましょう。
次のことをホールの結婚定理を用いて示していきます。
\(K\,\)を有限群とし\(\,H\,\)をその指数\(\,n\,\)の部分群とする。
このとき左剰余類・右剰余類のどちらの完全代表系となるような元\(\,z_1,z_2,\ldots,z_n\,\)をうまく取ることができる。
つまり\(\,K=z_1H\cup z_2H\cup\cdots \cup z_nH=Hz_1\cup Hz_2\cup \cdots \cup Hz_n\,\)とできる。
\(H\,\)が正規部分群の場合，\(\,kH=Hk\,\,(\forall k \in K)\,\)なので上のことは明らかです(左剰余類における完全代表系を取れば，それは右剰余類の完全代表系になるから)。
\(H\,\)が正規部分群でない場合にも成り立つのは非常に面白いですね。
それでは証明です。
群\(\,K\,\)とその部分群\(\,H\,\)から\(\,2\,\)部グラフ\(\,G=G(X,Y)\,\)を次のように構成しましょう。
\(X=\{x_1H,x_2H,\ldots x_nH\}\,\)：左剰余類の集合
\(Y=\{Hy_1,Hy_2,\ldots,Hy_n\}\,\)：右剰余類の集合
※このときの代表元は適当でよい。
辺\(\,x_iH\cdot Hy_j\,\,(x_iH\in X,Hy_j\in Y)\,\)が存在する\(\,\Leftrightarrow x_iH\cap Hy_j\not= \emptyset\)
このように定めた\(\,2\,\)部グラフ\(\,G\,\)がホールの結婚定理の条件
「\(\,X\,\)の任意の部分集合\(\,S\not=\emptyset\,\)について\(\,|N_G(S)|\geq |S|\,\)が成り立つ」ことを確認しましょう。
\(\,X\,\)の任意の部分集合\(\,S\not=\emptyset\,\)について\(\,|S|=k\,\)とすると，
\(\,\displaystyle \bigcup_{x_iH\in S} x_iH\,\)の元の数は，ラグランジュの定理より\(\,k|H|\,\)です。
これらの\(\,k|H|\,\)個の\(\,K\,\)の元を右剰余類の中に収めるには，位数の比較から明らかに\(\,k\,\)個以上の右剰余類が必要です。
つまり\(\,\displaystyle \bigcup_{x_iH\in S} x_iH \sub \bigcup_{Hy_j\in T}Hy_j\,\)とするには，
\(T\sub Y\,\)は\(|T|\geq k\)でなければならないということです。
これは\(\,|N_G(S)|\geq |S|\,\)が成り立つことを意味します。
よってホールの結婚定理と\(\,|X|=|Y|\,\)であることより，グラフ\(\,G\,\)は完全マッチングを持ちます。
つまり必要なら\(\,Hy_1,Hy_2,\ldots,Hy_n\,\)の番号を振りなおすことで，各\(\,i\,\,(1\leq i \leq n)\,\)について
\(x_iH\cap Hy_i\not=\emptyset\,\)とできるということです。
そこでそれぞれの\(\,i\,\)に対して，\(z_i\in x_iH\cap Hy_i\,\)となる\(\,z_i\,\)を取れば，代表元を取り換えただけなので，
\(K=z_1H\cup z_2H\cup\cdots \cup z_nH=Hz_1\cup Hz_2\cup \cdots \cup Hz_n\,\)となり，題意は示されました。\(\quad\square\)
証明を見ていただければ分かるように，証明に群構造をあまり用いていません(主に位数の比較のみでした)。
そのためこの命題をやや一般化することも可能です。
気になる方は参考図書\([1]\)のTheorem 3.をご覧ください。
その他の応用
ホールの結婚定理はその他，
長方形の欠けたラテン方陣を正方形のラテン方陣に拡張できることの証明や
\((0,1)\,\)行列に関するKönig-Egerváryの定理の証明などにも用いられます。
これらの応用はご要望があれば，改めて別の記事として書くので，ご意見お待ちしてます。
もちろんマッチングで解説したような，日常的な問題(男女のお見合い，係決め)に対しても使えるので，日常生活で考えてみるのも良いでしょう。
まとめ
今回の記事ではホールの結婚定理(Hall’s marriage theorem)の応用を解説いたしました。
応用の奥深さを味わっていただけたでしょうか？
説明を省略した部分(バーコフ-フォンノイマンの定理や\(\,1\sim 13\,\)のカードをどうやって見つけるかなど)がありますので，そちらが気になる方などは
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
参考図書
- \([1]\) Hall, P. (1935), On Representatives of Subsets. Journal of the London Mathematical Society, s1-10: 26-30. https://doi.org/10.1112/jlms/s1-10.37.26
