多米诺骨牌的最大数量可以放置一个数字里面

本文介绍了多米诺骨牌的最大数量可以放置一个数字里面的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

假设的平方纸上的一些数字。图中双方就方格纸的线条直奔主题。图可以具有任何（即使不是凸面）的形状。如何找到骨牌（1×2矩形的），可以放置在该图的最大数目。它不允许把多米诺超过另一个。它允许把多米诺只有在这样的方式，当其两侧正好落在方格纸的行

Suppose some figure on the squared paper. Sides of the figure go straight on the lines of squared paper. Figure may have any (not even convex) shape. How to find the maximum number of dominoes (1x2 rectangular) that can be placed in that figure. It is not allowed to put domino over another one. It is allowed to put domino only in such way, when its sides fall exactly on the lines of squared paper.

推荐答案

看起来像maximum在二分图基数匹配问题。正方形是顶点和多米诺骨牌是属于匹配的边缘。

Looks like the maximum cardinality matching problem in a bipartite graph. The squares are the vertices and the dominoes are the edges that belong to the matching.

要看到，该图是二部图，想象中的正方形棋盘画。黑色的唯一的邻居白色的，反之亦然。

To see that the graph is bipartite, imagine the squares are checkerboard-painted. Black ones only neighbour white ones and vice versa.