我必须要么用多米诺骨牌将下图平铺，要么证明这是不可能的。
我认为要实现这一点，我必须找到图形关联图的完美匹配（每个空间都是图形的一个节点，它们以垂直和水平方式通过边连接）。所以图是无向的，不是二分的。节点数为 42，因此可能由于节点数为偶数，但我认为这是不可能的。我想到了一个图有一个完美匹配的定义（图的匹配数在|V|=2·v(G)哪里）。v(G)
如果它存在，你能帮我找到瓷砖或继续证明它是不可能的吗？
问问题
750 次
3 回答
4
根据霍尔匹配定理，如果从二部图的一个“部分”中选择任何一个子集，并且与该子集的顶点相邻的顶点数小于子集的大小，则不存在完美匹配。
如果我们选择如下所示的 11 个绿色瓷砖，我们只会得到 10 个相邻的瓷砖。这意味着没有完美的匹配，你不能用多米诺骨牌覆盖这个数字。
于 2013-08-10T16:46:14.157 回答
1
那是不可能的。
每个多米诺牌由一个偶数和一个奇数组成。
蓝色区域包含相同数量的奇数和偶数正方形。
黄色方块是偶数，绿色是奇数。
考虑一组在蓝色+黄色区域内至少有一个正方形的多米诺骨牌。
它们也可能覆盖绿色区域的一些广场。
但无论如何，这组多米诺骨牌的偶数和奇数平方数是不可能相等的。
于 2013-08-10T16:46:18.250 回答
0
我选择使用案例证明来解决这个问题。我还没有走到每个案例的尽头，但到目前为止的工作表明，每一种可能性都会导致死胡同，所以我认为平铺应该是不可能的。填写其余的证明，玩得开心。=)
于 2013-08-10T16:21:59.713 回答