サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

対称グラフの完全マッチング数について

完全マッチングについて面白い定理を見つけたので、ご紹介します。

まず、完全マッチングについて、

グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。

「マッチング (グラフ理論)」『フリー百科事典 ウィキペディア日本語版』より

完全マッチングとはグラフの全てのノード(点)が唯一つのエッジ(枝)の端点となっていると、言うことも出来ます。



例として、左図のグラフの完全マッチングを考えます。 f:id:inarizuuuushi:20170513122815p:plain:w700

各格子がノード、線分がエッジを表しています。
右の図の赤色で示したエッジの集合が完全マッチングの一例です。
どのノードも唯一つの赤色エッジの端点になっていることが分かりますね。

さて、このとき左のグラフについて、完全マッチングは幾つ存在するだろうか?というのが今回のテーマになります。


以下扱うグラフは全て、格子状の対称グラフとします。


グラフの分解

唐突ではありますが、以下のようなグラフの分解を考えます。
f:id:inarizuuuushi:20170513123641p:plain:w300
まず、対称軸をひとつ見つけ対称線を引きます。
そしてグラフを"対称線より右側の部分"と"対称線より左側の部分"で分かれていると見做します。

f:id:inarizuuuushi:20170513124017p:plain:w300
次に対称線と重なるノードについて上から順に見ていきます。(図中緑点)
まず、“対称線より右側の部分"について、緑点を端点にもつエッジを削除します。
図中赤バッテンが上に当てはまるエッジになるので、これを削除します。

f:id:inarizuuuushi:20170513124404p:plain:w300
次にその下のノードに移ります。今度は“対称線より左側の部分"について、緑点を端点にもつエッジを削除します。(左側になっていることに注意して下さい)
図中赤バッテンがそれに当たります。

f:id:inarizuuuushi:20170513124654p:plain:w300
次にその下のノードに移ります。今度は“対称線より右側の部分"について、緑点を端点にもつエッジを削除します。

f:id:inarizuuuushi:20170513124823p:plain:w300
今度は左側。

f:id:inarizuuuushi:20170513124844p:plain:w300
そして最後まで行くと、上のようなグラフが出来上がります。


定理

このとき、元々のグラフを G、上図のプロセスで出来上がるグラフを \bar{G}
グラフ Gにおける完全マッッチング数を M\left(G\right)
と表すと、以下の定理が成り立ちます。

 M\left(G\right) = 2^{\frac{k}{2}} M\left(\bar{G}\right)

ここで kは対称線と重なるノードの個数になります。

簡単な例から見ていきましょう。
f:id:inarizuuuushi:20170513125839j:plain
まず、正方形の格子グラフについて、この完全マッチング数は普通に数えて、2つであるとすぐに分かります。(上)
では、定理を使うとどうなるかというと、それが(下)になります。
確かに定理を用いた場合も2になっていることが分かりますね。

次は f:id:inarizuuuushi:20170513130345j:plain
定理を用いた場合、正方形とL字型を反転させた2つのグラフが出てきますが、簡単な考察からL字型(の反転)のグラフの完全マッチング数は1つになります。

どんどんグラフを大きくしていきます。 f:id:inarizuuuushi:20170513130615p:plain

f:id:inarizuuuushi:20170513130822p:plain

f:id:inarizuuuushi:20170513130909p:plain

以上になります。

(参考)
http://gcoe-mi.jp/temp/publish/b484e6492e396aff6512ae7a2bdf5560.pdf