完全かんぜん被覆ひふく問題もんだい

完全かんぜん被覆ひふく (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)$

関連かんれん項目こうもく

• 安定あんてい結婚けっこん問題もんだい
• 最小さいしょう頂点ちょうてん被覆ひふく問題もんだい
• ポリオミノ