平行四边形六角系统-的完全强迫数

平行四边形六角系统的完全强迫数2.1平行四边形六角系统六角系统是一个有限的2-连通可平面图，其每个内面边界是边长为单位1的正六角形。其六角形的顶点和边构成了该图的顶点和边。为叙述简单起见，我们总是令所讨论六角系统放置在平面上，且六角系统中每一个正六角形都恰好有一对平行边是竖直的。六角系统的对偶图是以六角系统中所有六角形的中心为顶点集，两个顶点之间连边当且仅当所对应的六角形有公共边。显然，一个六角系统的的对偶图仍然是一个可平面图，其外部面边界称作是对偶图的边界。我们通常用六角系统对偶图边界的形状来命名六角系统。即如果一个六角系统的对偶图是一条直线段，则称其为六角链；而如果一个六角系统对偶图的边界是一个平行四边形，则称这个六角系统为平行四边形六角系统。形如：图1： 由定义可知，平行四边形六角系统是有限且连通的，其每个内面被单位正六边形（称为一个单位）所连区域包围，且每条边至少属于一个单位。本文我们研究平行四边形六角系统，其中m，n分别表示m列n行。如图1，即为m=4，n=3的平行四边形六角系统。基于在第一部分中的定义和上述研究平行四边形网格的方法、步骤，在这一部分我们给出平行四边形六角系统的明确公式。对于一个m列n行的平行四边形六角系统有以下几条重要结果：定理4.1：每个平行四边形六角系统都是一个基本图（P中所有允许边组成P的一个连通子集），且它至少包含个完美匹配。 的一种完美匹配如图8所示，可以看出每一行有且仅有一行竖直边，我们可以推广到一般结论。图8：引理4.2：每个平行四边形六角系统中，每行都有且仅有一条竖直边。首先寻求平行四边形六角系统坐标化的办法，这里我们给出竖直边的标记。在中，每行有m+1个竖直边，从左往右依次标记为。对于给定的完美匹配，用表示中第p列的竖直边，。引理4.3：对平行四边形六角系统中的每个完美匹配，结果是非减的引理4.4：设是中的一个完美匹配，第p列包含的竖直边为。则中在第p+1,.m列的部分，各自所包含的竖直边是唯一确定的。类似的，在第1,2.p-1列的部分也是唯一确定的。定理4.5：在中所有的完美匹配组成的集合和长度为n的非减数列0,1.m之间存在一一对应关系。通过上述定理易知，中每n条非减的竖直边可以唯一确定一种的完美匹配M,且中所有的完美匹配都可以用n条非减的竖直边限制得到。定理4.6：设是一个平行四边形六角系统，边集为E（G）。是的完全强迫集当且仅当，和中每个六角形h的两组type-edges中任意一组都有非空交集。证明：必要性可以通过定理2.8直接得到，事实上每个六角形都是nice的。以下我们证明充分性。 设是E（G）的一个子集，和中每个六角形h的两组type-edges中任意一组都有非空交集。由定理2.8的充分性可知，对任意非六角形的nice圈,设其中一组type-edges为，和的两组type-edges都是相交非空的，即。而无论如何取，它其中必然会包含至少一个六角形，记为h，则是h其中一组type-edges。再由的选取可知，。则。结论得证。图9：引理4.7：设是一个m列，n行的平行四边形六角系统，则。证明：只要给出一个完全强迫集，使其势为即可。首先，可以给出这样的一个集合，其势为，再证明它是完全强迫集。设为 一个3行4列的平行四边形六角系统的取法如图9所示，即为所有的竖直边。由的取法可直接计算得到集合的势为。以下证明是的一个完全强迫集。由定理4.6可知，只需证明和中每个六角形h的两组type-edges中任意一组都有非空交集。对于每个六角形h而言，和的交集恰好只有两条边，记为，且每个正六角形都是一个偶长圈，显然这两条边属于h的不同type-edges，如图9右图所示。得证。引理4.8：设是一个m列，n行的平行四边形六角系统，则。证明：设S是中任意一个完全强迫集。由定理4.6可知，和中每个六角形h的两组type-edges中任意一组都有非空交集。则对一个六角形而言，最少含有两条在h中的竖直边。已知对于一个平行四边形六角系统，每一行含有m个六角形，每一列含有n个六角形。则每一行的竖直边至少有条。而含有m列n行，则至少包含条边。定理4.9：设是一个m列，n行的平行四边形六角系统，则。4、 总结和展望本文主要研究了平行四边形网格和平行四边形六角系统的完全强迫数，根据它们的结构特点给出了其完全强迫数的计算公式。两个特殊图的完全强迫数的计算公式由定理3