下の図をドミノで並べるか、それが不可能であることを証明しなければなりません。
これを達成するには、図の関連グラフの完全な一致を見つける必要があると思います（すべてのスペースはグラフのノードであり、垂直方向と水平方向のエッジで接続されています）。したがって、グラフは無向であり、二部グラフではありません。ノード数が42なので、ノード数が偶数なので可能かもしれませんが、無理だと思います。グラフが完全に一致する iff を持つという定義について考えてみました|V|=2·v(G)(グラフの一致する数はどこですかv(G))。
タイリングが存在する場合は見つけるのを手伝ってくれますか、それとも不可能であるという証明を続けてくれますか?
ホールのマッチング定理によれば、2 部グラフの 1 つの「部分」から任意のサブセットを選択し、このサブセットの頂点に隣接する頂点の数がサブセット サイズよりも小さい場合、完全なマッチングはありません。
以下に示すように 11 個の緑のタイルを選択すると、隣接するタイルは 10 個しか得られません。つまり、完全に一致するものはなく、ドミノでフィギュアを覆うことはできません。
それは不可能です。
各ドミノ タイルは、1 つの偶数と 1 つの奇数の正方形で構成されます。
青い領域には、奇数と偶数の正方形が同数含まれています。
黄色の四角は偶数、緑は奇数です。
青と黄の領域内に少なくとも 1 つの正方形があるドミノ牌のセットを考えてみましょう。
また、緑の領域のいくつかの正方形を覆うこともあります。
しかし、いずれにせよ、このドミノ牌のセットの偶数と奇数の正方形の数を等しくすることは不可能です。
