黑白顶点数目相等的无完美匹配四角系统

The Polyominoes with the Same Number of Blackand White Vertices Without Perfect Matching

四角系统是一个二部图 .二部图有完美匹配的一个必要条件是对其顶点进行正常着色后 ,两个色类所含的顶点数相等 ,然而这一条件并不充分 .本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是 1 4 ,并且只有 3种非同构的形状 .由本文的方法还可以进一步构造出 1 5阶和 1 6阶无完美匹配四角系统的所有非同构形状 ,它们的数目分别是 2 2与 1 55.

A polyomino is a bipartite graph. A necessary condit io n for a bipartite graph to have a perfect matching is |B(G)|=|W(G)|, where |B(G)| denote the number of black vertices and |W(G)| the number of whit e vertices. Considering the polyominoes with |B(G)|=|W(G)| but have no perfe ct matching. Using construction method we show that the smallest order of such p olyomino graphs is exactly 14 and there are 3 non-isomorphic forms. Using the s ame mothod we can construct all such non-isomorphic polyomino graphs of order 1 5, 16, their number are 22 and 155, respectively.