Pfaffian图的结构性质及相关问题研究

本项目研究近年来图论领域备受关注的图的Pfaffian性问题。Thomas 2006年世界数学家大会上45分钟的报告（A survey of Pfaffian orientations of graphs）介绍了图的Pfaffian定向方面的研究成果和相关问题的进展。Pfaffian定向是物理学家 Kasteleyn为解决NP-难的完美匹配计数问题（统计物理中称为Dimer问题）提出来的。如果图有Pfaffian定向，那么它的完美匹配计数问题可以在多项式时间内解决。本项目将从结构上研究图的Pfaffian性，重点研究可定向闭曲面上Pfaffian图的结构性质、极小Brick(3-连通双临界图)的结构特征（在紧割分解的意义下图的Pfaffian性可归结为Brick 的Pfaffian性）、k-圈可扩图与图的Pfaffian性的内在联系、结构刻画以及Permanent多项式的计算方法。

本项目重点研究图的Pfaffian性的结构性质及相关的问题。一个无向图的一个Pfaffian定向是指图的的一个定向使得这的斜邻接矩阵的行列式等于它的完美匹配数的平方。一个Pfaffian图是指它有一个Pfaffian定向的图。一般图的完美匹配计数问题是NP－难的，但如果一个图有Pfaffian定向，那么它的完美匹配计数问题可以在多项式时间内解决。本项目研究主要包含以下几个方面。.图的Pfaffian性的结构性质研究。主要研究结果包含：（1）得到了可嵌入在环面上的Pfaffian图的一些充分条件，应用这些充分条件，我们证明了可嵌入在环面上的若干网格子图是Pfaffian图的充分必要条件是图非二部图，并给出了这些图Pfaffian定向的方法：（2）证明了S. Norine 和 R. Thomas提出的一个猜想：每一个极小３－连通双临界图含有四个３度顶点。（3）从匹配minor的角度刻画了任一个图与偶长路的乘积图是Pfaffian图的和充分必要条件；（4）证明了循环图Ｃn(a1,a2,…,ak)是Pfaffian图当且仅当 k 等于１, 或 k=2 并且 a1+a2 为奇数这一性简洁的刻画与判定.（5）给出了含有一个顶点的度为点数的一半的1-可扩二部图的一个定向是Paffian的判定，同时给出了一个多项式时间算法。.完美匹配计数问题的研究。我们用图的Pfaffian定向的方法进行研究，分别得到了嵌入在克莱因瓶上的8.8.4网格和8.8.6网格图的完美匹配数的显式表达式和嵌入在环面上的几类4-正则网格图的完美匹配数的显式表达式等。.线图的哈密顿性和超欧拉图的性质等问题的研究。主要研究结果包含：（1）证明了有至多9个3度顶点的图的3-连通、实质4-连通线图是哈密顿的，并且所有条件是紧的；（2）证明了每一个边度至少7的3-边连通、实质6-边连通图或每一个边度至少6, 至多24个3度顶点的3-边连通、实质5-边连通图是collapsible；（3）证明了每一个3-连通、实质11-连通线图或每一个7-连通线图是哈密顿连通的，并基于图的最小边度和限制性边连通度等参数证明了一个3-边连通图是collapsible的若干充分条件等。

内容获取失败，请点击重试