完全被覆問題

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

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

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

ダイマー (dimer) はモノマーと呼ばれる分子が2つ重合した形の分子を意味する。ダイマー模型はダイマーのさまざまな配置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) 全体の集合を表す。

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

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集