多米诺骨牌的最大数量可以放置一个数字里面 [英] maximum number of dominoes can be placed inside a figure

问题描述

假设的平方纸上的一些数字。图中双方就方格纸的线条直奔主题。图可以具有任何（即使不是凸面）的形状。如何找到骨牌（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.

推荐答案

看起来像<一个href="http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs">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.

这篇关于多米诺骨牌的最大数量可以放置一个数字里面的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！