ノート:完全被覆問題
項目名も含めた全面見直しの提案
[編集]被覆（cover）と、マッチング（matching）は全く異なる概念です。
被覆問題は、一般に平面上の領域を図形で覆い尽くしたり、平面上の複数の点を図形で隠すというような問題を指し、多くの場合被覆する側の図形の重なりを許すような問題となっています。ここで紹介されているチェス盤のドミノによる完全被覆問題も被覆問題の１つと位置づけてもよいかもしれませんが、重複を許さずぴったり領域を被覆する問題は一般には「敷き詰め」「タイリング」というカテゴリーに入るのではないでしょうか。「完全被覆問題」というカテゴリーが、その問題を代表格とする独立したカテゴリーとして存在するとは思えません。
一方、グラフ理論のマッチングは、2013年1月11日の版の「定義」において「被覆（matching）」というあまり一般的ではない（おそらくは間違った）訳語で紹介されている通りの内容であり、Wikipedia上にも「マッチング (グラフ理論)」というエントリーが存在します。
現在このエントリーで紹介されている内容のつながりを整理すると、
・グラフのマッチングの中でもグラフ全体をカバーするものが「完全マッチング」
・「ダイマーモデル」は、平面に描かれた格子状のグラフにおける完全マッチングをモデル化したものとみなすことができる
・「チェス盤のドミノによる完全被覆」は、チェス盤のマスの双対グラフ上でのダイマー配置と１対１に対応するので、その数え上げはダイマー配置の数え上げと一致する
・m×nマスの長方形領域のドミノによる完全被覆の数、すなわち、m×n点からなる格子状のグラフ上でのダイマー配置の数については、一般的な公式が存在し（Kasteleyn，Fisher＆Temperleyによる）、8×8マスのチェス盤の場合は12988816個となる
ということだと理解しています。
以上のようなことから、「完全被覆問題」という項目名のままこの内容を存続させるのは不適切だと考えます。
変更案としては、
案１：項目名を「完全マッチング」として「マッチング (グラフ理論)」からのリンクを張り、その中で「ダイマーモデル」について紹介し、さらにその応用として「チェス盤のドミノによる完全被覆」について触れる。
案２：項目名を「ドミノによる完全被覆問題」ぐらいにして、その解法としてダイマーモデルを紹介する。
案３：英語版Wikipediaにある「FKT algorithm」のエントリーを翻訳してそこに集約する。
このぐらいでしょうか。
当方は、Kasteleyn，Fisher＆Temperleyの論文も読んでおらず、結論部分を少し知っているだけの門外漢であり、力不足なので、どなたか上記を踏まえて適切な修正ができる方がおられましたら、お願いします。
現状のエントリーは、coverとmatchingが混乱しており、問題の解決者もKasteleyn，Fisher＆Temperleyではなく「Fischer」になっているなど、明白な不具合もいくつかありますが、方向性を整理しないとどこから着手していいかもわからなかったので、何も変更していません。
なお、記事中の非表示コメントで「ロバート・ジェームス・フィッシャーですか？」とありましたが、Michael Fisherという別人です。