假设在方格纸上有一些图形。图的侧面沿方格纸的直线平直。图形可以具有任何形状（甚至不是凸形）。如何查找可以在该图中放置的多米诺骨牌的最大数量（1x2矩形）。不允许将多米诺骨牌放在另一个上。当多米诺骨牌的一面恰好落在方格纸的线条上时，才可以这样放置多米诺骨牌。
看起来像二部图中的最大基数匹配问题。正方形是顶点，而多米诺骨牌是属于匹配项的边。
要查看该图是二部图，可以想象正方形是棋盘形的。黑人只与白人相邻，反之亦然。
