平行四边形网格百度nmR-的完全强迫数

平行四边形网格的完全强迫数1、 预备知识及初步设计2.2平行四边形网格及其坐标化 首先根据近期研究出来的长方形网格的完全强迫数计算方法，我们先研究一个长为列（每一行正方形个数）、宽为行，其中m、n为正整数且的正方形网格来研究，定义为，最后再推广到平行四边形六角系统的情形。平行四边形网格如图2所示：图2为方便起见，我们总是把所研究平行四边形网格放在平面上，这样规则正方形网格中两条相反的边的方向是可坐标化的。这样就可在上建立一个坐标系，左下角延长线的点设为（1,1），右上角的点坐标即为（m，n），把图2所示平行四边形网格建立坐标系如图3所示：图3：可知，平行四边形网格中的所有圈均为偶长圈，则平行四边形网格是一个二部图（基于同样的理由，平行四边形六角系统也同样是一个二部图）。在这篇文章中，我们有必要强调m为奇数，否则没有任何完美匹配（见下述定义），所以我们在求解平行四边形网格完全强迫数中总是假设m为奇数。2.3相关概念一个图的完美匹配（或凯库勒结构）是中不相交的边组成的集合，它要求覆盖中所有点。中一条边称为允许边，如果它属于中的一个完美匹配；否则就称为的禁止边。一个图称为基本的，如果中所有允许边组成的一个连通子集。注意，如果一个二部图是基本的，则其所有边都是允许边。设，是一个集合的两个子集，则两个集合的对称差分，可表示为，是一个集合，其中的元素需要确切的一个属于一个属于。设是一个连通图，它有一个完美匹配。的一个子集H是nice的，如果也含有一个完美匹配。显然，中的偶长圈C是nice的当且仅当C刚好是中两个完美匹配的对称差分，即；我们称和是C的两组type-edges。或者，的一个nice圈的每个type-edges都是C的一个完美匹配。对于一个长方形网格的设置与平行四边形网格相同），如图4，以下有一个基础的性质：图4：2.4引入定理及证明引理2.4：设对一个长方形网格来说，其是偶数。则存在一个完美匹配，且是基本的。定理2.5：设对一个平行四边形网格来说，其是偶数。则存在一个完美匹配，且是基本的。证明：首先我们按上述方法对平行四边形六角系统建立坐标系，由上述假设可知，m，n中至少一个为偶数，不妨令n取整数，则可定义边集的一个子集：显然，是的一个完美匹配。取法如图5所示，图中加粗线组成的集合即为一个完美匹配。定理前半部分得证。下证是基本的。由引理2.4可知一个长方形网格是基本的，则其所有边都是允许边。对于一个长方形网格，对其中每个小正方形，如果一条边确定，则所对应的完美匹配中的其他边也是唯一确定的。对于一个平行四边形网格，情况也是一样，它相当于一个长方形网格把从上往下数第二行之后每一行都相对于前一行向右平移一个单位正方形得到，若m为奇数，则其完美匹配的取法不变。则平行四边形网格的每条边也都是允许边，即它是基本的。图5：引理2.6：设是一个平面二部图，其顶点数大于等于2，则的每个面的边界都是nice的当且仅当是基本的。定理2.7：设是一个平行四边形网格，其m是奇数，则中每一个正方形区域都是nice的。证明：是一个平面二部图，且由定理2.5知是基本的，则由引理2.6可直接得到。2.5完全强迫集和完全强迫数 设G是一个连通图，它的边集设为E(G)，它有一个完美匹配。的强迫集是的一个子集，它不属于中其它任何一个完美匹配。由其定义易得，一个空集是的强迫集当且仅当是中唯一一个完美匹配。的一个完全强迫集S是边集的一个子集，其对任何完美匹配，的限制是M的一个强迫集。显然，任何包含的一个完全强迫集的集合，尤其是，也是的一个完全强迫集。一个具有最小势的完全强迫集叫做最小完全强迫集，而这个最小势就叫做的完全强迫数，定义为。 图6：如图6所示，包含三个不同的完美匹配：容易看出，每个完美匹配的限制，在上是的一个强迫集。因此，S是的一个完全强迫集。因为S和每个完美匹配的交集都是非空的，且是边集的一部分，则S势为3，是一个最小完全强迫集，。我们下面给出一个含有完美匹配的连通图的完全强迫集的充分必要条件：定理2.8:设是一个连通图，边集为E(G)，且含有完美匹配。是的一个完全强迫集当且仅当，对G中任何一个nice圈C，S和C的每组type-edges的交集是非空的。 在这部分，给出平行四边形网格的完全强迫数关于其边长m，n的表达式。定理3.1（Picks theorem）：设P是在多联骨牌上的一个简单多边形，这样所有P上的点是四边形上的点，设在P的内部四边形上的点的数量为i，设在P的边界上的四边形上的点为b，则P的区域含四边形的个数为 图7： 引理3.2：设是一个平行四边形网格，其m为奇数，则。证明：只要给出一个完全强迫集，使其势为即可。首先，可以给出这样的一个集合，其势为，再证明它是完全强迫集。设为 其中（1）为中水平边的边集，（2）中竖直边的边集，出现不属于原图的边则忽略不计。例子如图7所示，S即为图中加粗边。若把图7中的第7，8，9列平移到第1，2，3列的下方，则拼成一个规则的长方形网格，平移过来的加粗边的数量刚好能使整个加粗边变成一个规则的网，其水平边数量为，竖直边数量为通过直接的计算可证明集合的势为。以下证明是的一个完全强迫集。由定理2.8可知，只需证明与中每个nice圈中的两组type-edges相交非空。情形1：是中任意nice圈，最小的应该是一个单位正方形，对每个单位小正方形，和有且仅有两条相邻边，且属于中不同的type-edges。则和中两组type-edges相交非空，情形2：是不规则的圈。即证非空。假设为空集，设是中通过删除中的边得到的图，然后删除中所有悬挂边（边的终边是1度点），最后删除所有的孤立点。能发现具有和平行四边形网格相同的结构，只是每个单位小正方形从变长为1变成了变长为2 。则由假设可知，是完全包含在中的。假设封闭一些平面区域R，则R的外部点b是四可分的。由定理3.1可知，内部点i是奇数，则是没有完美匹配的，与为nice圈矛盾。引理3.3：设是一个平行四边形网格，其m为奇数，则。证明：设是中任意一个完全强迫集。由定理2.7和定理2.8可知，与中任意一个正方形区域h的两组type-edges是相交非空的。则最少含有一条