找到一个完美的匹配或证明这是不可能的
斯特拉特福
我要么用多米诺骨牌对下图进行平铺，要么给出不可能的证明。 
我认为要实现这一点，我必须找到图形关联图的完美匹配（每个空间都是图形的一个节点，并且它们通过垂直和水平方式通过边连接）。因此，该图是无向的，不是二分的。节点数为42，因此由于节点数为偶数而可能，但我认为这是不可能的。我考虑了图具有完美匹配iff的定义|V|=2·v(G)（这里v(G)是图的匹配数）。
您能帮助我找到该图块是否存在，或继续证明它不可能吗？
叶夫根尼·克鲁维（Evgeny Kluev）
根据霍尔的匹配定理，如果您从二部图的一个“部分”中选择任何子集，并且与该子集的顶点相邻的顶点的数量小于子集的大小，那么就没有完美的匹配。
如果我们选择11个绿色磁贴，如下所示，则只能获得10个相邻磁贴。这意味着没有完美的匹配，并且您无法用多米诺骨牌覆盖该图。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
在 ruby 的字符串中找到一个完美的子字符串
- 2
聪明地投射到“ ObserverT !!” 这是不可能的，因为“ item.get（）”是一个复杂的表达式
- 3
不可能删除一个ppa
- 4
聪明地投射到“位图！” 这是不可能的，因为'bitmap1'是一个可变的属性，这一次可能已经更改了
- 5
根据用户输入从一系列数字中找到一个完美的数字
- 6
图像视图不是一个完美的圆圈
- 7
检查数字是否是一个完美的平方
- 8
想要一个完美的圆圈来通知数量
- 9
检查一个完美的立方体
- 10
内容在一个完美的圆圈内的 Div
- 11
判断一个数是否完美的程序
- 12
在两个数组中找到对，使得相乘时成为一个完美的正方形
- 13
如何将这两个独立的程序集成到一个程序中？或者这是不可能的？
- 14
由于Rust只能有一个所有者，这是否意味着不可能进行浅拷贝？
- 15
它是不可能有一个@RequestParam作为一个列表？
- 16
如何证明平等是不可能的
- 17
如何检查一个整数是否是一个完美的正方形
- 18
不可能将一个框垂直居中成一列
- 19
如何告诉Java的一个变量不可能为空？
- 20
为什么我不可能写入到一个文件？
- 21
为什么在 VB.NET 中不可能声明一个 NotOverridable 方法？
- 22
为什么不可能实例化一个原子对？
- 23
为什么不可能实现“无限”的一个时间片算法？
- 24
从两个列表中计算对，相乘后得出一个完美的平方
- 25
不可能在另一个组件的左侧获得一个 Angular 组件
- 26
通过移动鼠标指针创建一个完美的圆
- 27
如何打造一个完美的假jQuery的事件对象
- 28
如何编写一个完美的异常映射器？
- 29
找出是否n！+1是一个完美的正方形
我来说两句