论文部分内容阅读
图的完美匹配的计数问题是图论的一个重要研究课题，它在量子化学和统计物理等学科中均有非常重要的应用.一般图，即使是二部图的完美匹配的计数问题是＃P-完全的.本文重点研究了无边界曲面上的四边形网格和六边形网格的完美匹配的计数问题以及一类r-正则图的完美匹配数的下界。 Thomassen在研究无边界曲面上的正多边形的铺砌问题时，证明了四边形网格和六边形网格均只能嵌入在环面或者Klein瓶上.他刻画了嵌入在Klein瓶上的四边形网格的所有图类Qm，n，x(x=a，b，c，f，g，h）以及六边形网格的所有图类Hm，n，x(x=a，b，c，d，f);也刻画了嵌入在环面上的四边形网格的所有图类Qm，n，r与Qk，l以及六边形网格的所有图类H2m，n，r与Hk，l.Lu和Wu，Lu、Zhang和Lin利用图的平面表示和交叉定向分别得到了图Qm，n，a和Qm，n,x(x=b，c，f，g)的完美匹配数的显示表达式.Kaste-leyn，Lu、Zhang和Lin考虑了Qm，n，r的完美匹配数.Klein利用转移矩阵的方法讨论了r与n具有相同的奇偶性时的H2m，n，r的完美匹配的计数问题.本文进一步研究了嵌入在环面上的四边形网格Qk，l和六边形网格日2m，n，r的完美匹配的计数问题.对于Qk,l，通过适当的剖分给出它的一种平面表示和一个交叉定向;证明了这个交叉定向在l为偶数时是一个Pfaffian定向;通过计算图的Pfaffian定向的斜邻接矩阵的行列式得到了Qk，l当k≡0(mod4)和k≡2(mod4)时的完美匹配数的显示表达式;根据嵌入在环面上的四边形网格的完美匹配数的表达式讨论了它当顶点数趋于无穷时的完美匹配的熵（即完美匹配数取对数后与顶点数的一半的比值）.对于H2m，n,r，通过适当的剖分给出它的一种平面表示和一个交叉定向;对所有完美匹配进行分类且给出了它们的符号权重;通过Tesler的交叉定向的方法计算Pfaffian线性组合得到了H2m，n，r当n为偶数和奇数时的完美匹配数的表达式。 对于r-正则图的完美匹配数的下界问题的研究，Lovász和Plummer在20世纪70年代提出了一个猜想:对于r≥3，存在常数c1(r)＞1和c2(r)＞0使得每一个具有2n个顶点的r-正则1-可扩图至少包含c2(r)·c1(r)n个完美匹配，而且当r→∞时c1(r)→∞.对于r-正则二部图和3-正则图，这个猜想被证实是成立的.本文研究了一类r-正则图—r-klee-图的完美匹配数的下界.r-klee-图递归定义如下:(1)r+1阶完全图Kr+1是一个r-klee-图;(2)设G是一个r-klee-图，则通过用一个r阶完全图Kr替换G中的一个顶点u使得Kr的r个顶点分别与u在G中的r个邻点相邻所得到的图G也是一个r-klee-图.删除r-klee-图的一个顶点及其相关联的边后所得到的图H称为几乎r-klee-图.如果树中除了1度顶点以外的所有顶点均为r度，则称之为r-正则树.我们首先给出了r-klee-图与(r+1)-正则树的一个对应关系;其次，通过(r+1)-正则树的结构性质证明了r-klee-图是双临界的和几乎r-klee-图存在唯一的点分解使得这些点子集是孤立点或者导出子图是几乎r-klee-图;最后，利用上述两个结论得到了r-klee-图当r为偶数和奇数时的完美匹配数的两个下界，从而验证了Lovász和Plummer的猜想对于r-klee-图是成立的。