平行四边形网格Rm,n的完全强迫数一、预备知识及初步设计2.2平行四边形网格及其坐标化首先根据近期研究出来的长方形网格的完全强迫数计算方法，我们先研究一个长为m−1列（每一行正方形个数）、宽为n−1行，其中m、n为正整数且m,n≥2的正方形网格来研究，定义为Rm,n，最后再推广到平行四边形六角系统的情形。平行四边形网格如图2所示：图2为方便起见，我们总是把所研究平行四边形网格放在平面上，这样规则正方形网格中两条相反的边的方向是可坐标化的。这样就可在Rm,n上建立一个坐标系，左下角延长线的点设为（1,1），右上角的点坐标即为（m，n），把图2所示平行四边形网格建立坐标系如图3所示：(1,4)(1,3)(2,3)(2,4)(3,3)(3,4)(4,3)(4,4)(5,3)(5,4)(2,2)(3,2)(4,2)(5,2)(6,2)(6,3)(3,1)(4,1)(5,1)(6,1)(7,1)(7,2)1,1图3：R5,4可知，平行四边形网格中的所有圈均为偶长圈，则平行四边形网格是一个二部图（基于同样的理由，平行四边形六角系统也同样是一个二部图）。在这篇文章中，我们有必要强调m为奇数，否则Rm,n没有任何完美匹配（见下述定义），所以我们在求解平行四边形网格完全强迫数中总是假设m为奇数。2.3相关概念一个图G的完美匹配（或凯库勒结构）是G中不相交的边组成的集合，它要求覆盖G中所有点。G中一条边称为允许边，如果它属于G中的一个完美匹配；否则就称为G的禁止边。一个图G称为基本的，如果G中所有允许边组成G的一个连通子集。注意，如果一个二部图是基本的，则其所有边都是允许边。设S1，S2是一个集合的两个子集，则两个集合的对称差分，可表示为S1⊕S2，是一个集合，其中的元素需要确切的一个属于S1一个属于S2。设G是一个连通图，它有一个完美匹配。G的一个子集H是nice的，如果G−V(H)也含有一个完美匹配。显然，G中的偶长圈C是nice的当且仅当C刚好是G中两个完美匹配M1,M2的对称差分，即C=M1⊕M2；我们称M1∩C和M2∩C是C的两组type-edges。或者，C的一个nice圈的每个type-edges都是C的一个完美匹配。对于一个长方形网格(m,n)的设置与平行四边形网格相同），如图4，以下有一个基础的性质：图4：A7,62.4引入定理及证明引理2.4：[2]设对一个长方形网格Am,n来说，其m×n是偶数。则Am,n存在一个完美匹配，且Am,n是基本的。定理2.5：设对一个平行四边形网格Rm,n来说，其m×n是偶数。则Rm,n存在一个完美匹配，且Rm,n是基本的。证明：首先我们按上述方法对平行四边形六角系统建立坐标系，由上述假设可知，m，n中至少一个为偶数，不妨令n取整数，则可定义Rm,n边集的一个子集M：{(i,2j−1)(i,2j),i=1,2,...m;j=n2}∪{(2i−1,j)(2i,j),i=1,2...m−12;j=1,2...n−2}¿{(m,j)(m+1,j+1),j=1,2...n−2}显然，M是Rm,n的一个完美匹配。取法如图5所示，图中加粗线组成的集合即为一个完美匹配。定理前半部分得证。下证Rm,n是基本的。由引理2.4可知一个长方形网格Am,n是基本的，则其所有边都是允许边。对于一个长方形网格Am,n，对其中每个小正方形，如果一条边确定，则所对应的完美匹配中的其他边也是唯一确定的。对于一个平行四边形网格，情况也是一样，它相当于一个长方形网格把从上往下数第二行之后每一行都相对于前一行向右平移一个单位正方形得到，若m为奇数，则其完美匹配的取法不变。则平行四边形网格的每条边也都是允许边，即它是基本的。图5：R5,4引理2.6：[3]设G是一个平面二部图，其顶点数大于等于2，则G的每个面的边界都是nice的当且仅当G是基本的。定理2.7：设Rm,n是一个平行四边形网格，其m是奇数，则Rm,n中每一个正方形区域都是nice的。证明：Rm,n是一个平面二部图，且由定理2.5知Rm,n是基本的，则由引理2.6可直接得到。2.5完全强迫集和完全强迫数设G是一个连通图，它的边集设为E(G)，它有一个完美匹配M。M的强迫集是M的一个子集，它不属于G中其它任何一个完美匹配。由其定义易得，一个空集是M的强迫集当且仅当M是G中唯一一个完美匹配。G的一个完全强迫集S是边集E(G)的一个子集，其对任何完美匹配M，M的限制是M的一个强迫集。显然，任何包含G的一个完全强迫集的集合，尤其是E(G)，也是G的一个完全强迫集。一个具有最小势的完全强迫集叫做最小完全强迫集，而这个最小势...