完全被覆問題

完全被覆（パーフェクトマッチング）とは

完全被覆とは、グラフ理論における重要な概念の一つで、特に組合せ論や離散数学の分野で頻繁に登場します。これは、グラフのすべての頂点を、重複することなく辺で結びつけることを指します。具体的に見ていきましょう。

定義

まず、グラフの定義から始めます。頂点の集合をV、辺の集合をEとします。無向グラフGは、G = (V, E) と表現できます。ここで、被覆（マッチング）Mとは、Eの部分集合であり、Mに含まれるどの2つの辺も頂点を共有しない、という条件を満たすものです。さらに、頂点の集合Vの要素数が2k個であるとき、被覆Mがk個の要素を持つ場合、Mは完全であると言います。

チェス盤の完全被覆

具体的な例として、チェス盤の完全被覆を考えてみましょう。通常のチェス盤は8×8の64マスで構成されています。このチェス盤を、隣り合う2マスを覆うドミノを使って完全に覆うことを考えます。

条件は以下の通りです。

1. ドミノ同士が重ならないこと。
2. ドミノはチェス盤の2マスを覆うこと。
3. チェス盤のすべてのマスを覆うこと。

この条件を満たすドミノの配置を、チェス盤の完全被覆と呼びます。このような配置は簡単に見つけることができます。また、異なる完全被覆の数を数えることもできます。例えば、8×8のチェス盤の場合、1961年にフィッシャーによって12,988,816個の異なる完全被覆が存在することが証明されています。一方で、3×3のチェス盤には完全被覆が存在しません。一般的に、少なくとも縦と横のどちらかが偶数の場合、つまりチェス盤のマス目が偶数の場合は、完全被覆が存在することが知られています。m×nのチェス盤での完全被覆の存在や、その数を数える問題は、数学的に興味深い課題です。フィッシャーは、m×nのチェス盤の異なる完全被覆の数を数えるための三角関数を用いた一般的な公式を発見しました。

ダイマー問題

ダイマーとは、モノマーと呼ばれる分子が2つ重合した分子のことです。ダイマー模型は、ダイマーのさまざまな配置に関する統計力学的模型です。具体的には、分配関数は以下のように定義されます。


Z = Σ e^(-E(C))

ここで、Cはダイマーの配置、E(C)はそのエネルギーを表します。統計力学的重みが1の場合、ダイマー配置の数え上げ問題になります。

二部グラフの言葉でダイマー模型を定式化することもできます。二部グラフG = (V1, V2, E) を定義し、各辺(i, j) ⊆ E = V1 × V2に対して統計力学的重みw(i, j)を与えます。分配関数Zは、完全被覆全体の集合Pを用いて次のように表されます。


Z = Σ ∏ w(i,j) (Pに含まれる全ての辺(i,j)について)

完全被覆と関連する問題

完全被覆は、以下のような問題とも関連があります。

安定結婚問題: 男女のペアを組む問題で、全員が不満を持たないようにペアを作ることを目指します。
最小頂点被覆問題: グラフのすべての辺をカバーする最小の頂点集合を見つける問題です。
* ポリオミノ: いくつかの正方形を辺で繋げた図形で、パズルのように特定の領域を埋める問題です。

これらの問題は、組合せ論やグラフ理論の分野で重要であり、完全被覆の概念はその基礎となっています。

まとめ

完全被覆は、グラフの頂点を重複なく辺で結びつけるという、シンプルながらも奥深い概念です。チェス盤のドミノ配置やダイマー模型など、具体的な問題を通じてその応用例を理解することができます。また、関連する問題も多岐にわたり、数学的な興味を引くテーマとなっています。

もう一度検索