完全マッチングについて面白い定理を見つけたので、ご紹介します。
まず、完全マッチングについて、
グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。
「マッチング (グラフ理論)」『フリー百科事典 ウィキペディア日本語版』より
完全マッチングとはグラフの全てのノード(点)が唯一つのエッジ(枝)の端点となっていると、言うことも出来ます。
例として、左図のグラフの完全マッチングを考えます。
各格子がノード、線分がエッジを表しています。
右の図の赤色で示したエッジの集合が完全マッチングの一例です。
どのノードも唯一つの赤色エッジの端点になっていることが分かりますね。
さて、このとき左のグラフについて、完全マッチングは幾つ存在するだろうか?というのが今回のテーマになります。
以下扱うグラフは全て、格子状の対称グラフとします。
グラフの分解
唐突ではありますが、以下のようなグラフの分解を考えます。
まず、対称軸をひとつ見つけ対称線を引きます。
そしてグラフを"対称線より右側の部分"と"対称線より左側の部分"で分かれていると見做します。
次に対称線と重なるノードについて上から順に見ていきます。(図中緑点)
まず、“対称線より右側の部分"について、緑点を端点にもつエッジを削除します。
図中赤バッテンが上に当てはまるエッジになるので、これを削除します。
次にその下のノードに移ります。今度は“対称線より左側の部分"について、緑点を端点にもつエッジを削除します。(左側になっていることに注意して下さい)
図中赤バッテンがそれに当たります。
次にその下のノードに移ります。今度は“対称線より右側の部分"について、緑点を端点にもつエッジを削除します。
今度は左側。
そして最後まで行くと、上のようなグラフが出来上がります。
定理
このとき、元々のグラフを、上図のプロセスで出来上がるグラフを、
グラフにおける完全マッッチング数を
と表すと、以下の定理が成り立ちます。
ここでは対称線と重なるノードの個数になります。
例
簡単な例から見ていきましょう。
まず、正方形の格子グラフについて、この完全マッチング数は普通に数えて、2つであるとすぐに分かります。(上)
では、定理を使うとどうなるかというと、それが(下)になります。
確かに定理を用いた場合も2になっていることが分かりますね。
次は
定理を用いた場合、正方形とL字型を反転させた2つのグラフが出てきますが、簡単な考察からL字型(の反転)のグラフの完全マッチング数は1つになります。
どんどんグラフを大きくしていきます。
以上になります。
(参考)
http://gcoe-mi.jp/temp/publish/b484e6492e396aff6512ae7a2bdf5560.pdf