完全被覆問題

完全被覆 (perfect matching) に関する問題の多くは組合せ論やグラフ理論などの離散数学と関わりがある。

定義

頂点の集合をV、辺の集合を E = {(i,j)| i,j ⊆ V} とすると、無向グラフGは G = (V,E) と書ける。グラフGの被覆 (matching) Mとは、(i,j), (r,s) ⊆ M ならばi, j, r, sが全て異なる頂点となる、という条件を満たすEの部分集合のことである。頂点の集合Vの要素の数が2k個で、被覆 (matching) Mがk個の要素を持つ場合、Mは完全 (perfect) であるという。

チェス盤の完全被覆

普通のチェス盤は8×8の64のマス目がある。チェス盤の隣り合う2マスを覆うことのできるドミノが十分に与えられたとする。チェス盤に次のように32個のドミノを並べることは可能かを考える。

• ドミノ同士が重ならないようにする。
• ドミノはチェス盤の2マスを覆う。
• チェス盤の全てのマスを覆うようにする。

このような並べ方をドミノによるチェス盤の「完全被覆（perfect matching）」と言う。これは簡単な並べ方の問題で、すぐに様々な完全被覆を作れるだろう。大変ではあるが異なる完全被覆の数を数えることもできる。ちなみにその数は、1961年にフィッシャー（Fischer）によって12988816個と解っている。また3×3の盤で完全被覆がない。少なくとも縦と横のどちらかが偶数の場合ならば、つまり、チェス盤のマス目の数が偶数の場合ならば、そのチェス盤が完全被覆を持っている。一般的にはm×nのmnマスで完全被覆が存在するかについて議論される。また、フィッシャーはm×nのチェス盤の異なる完全被覆の数を数えるための三角関数による一般的公式を見いだした。

ダイマー問題

ダイマー (dimer) はモノマーと呼ばれる分子が2つ重合した形の分子を意味する。ダイマー模型はダイマーのさまざまな配置Cに関する状態和

$Z=\sum _{C}e^{-E(C)}$

で定義される統計力学的模型である。統計力学的重み (Boltzmann weight) e^-E(C) が1の場合にはダイマー配置の数え上げ問題になる。2部グラフの言葉を用いれば、ダイマー模型は以下のように定式化される。

• 2部グラフG = (V₁,V₂,E)を指定する。
• 各辺(i,j) ⊆ E = V₁×V₂に対して統計力学的重み (Boltzmann weight) w(i,j)を指定する。
• 分配関数 Z = Z(G) を以下のように定める。PはGの完全被覆 (perfect matching) 全体の集合を表す。

$Z=\sum _{M\in P}\prod _{(i,j)\in M}w(i,j)$

関連項目

• 安定結婚問題
• 最小頂点被覆問題
• ポリオミノ