完全被覆問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/07/14 01:30 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2024年7月） |
完全被覆 (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に関する状態和
この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。
- 完全被覆問題のページへのリンク
