图的Pfaffian定向相关问题及应用研究

The Pfaffian orientation problem is to determine whether a graph has a Pfaffian orientation. This hard problem is greatly concerned in matching theory. It is one of the problems in the book "10,000 Selected Problems in Science(Mathematics)". R.Thomas introduced the progress of Pfaffian orientation problem in the 45-minute lecture of International Congress of Mathematicians in 2006. In this project, we will focus on the structure of Pfaffian graphs, especially graphs with given genus and highly symmetric; the property of Brick and the Pfaffian numbers, which are related to Pfaffian orientation problem, including the property of 3-regular Bricks, minimal Bricks and the classification of Bricks; and the numbers of perfect matchings for graphs, which is NP-hard for general graphs, by Pfaffian orientation theory and Algebra method, especially lattices in Physics and Chemistry. Research on these problems will promote the progress of Pfaffian orientation problem and enrich the matching theory of graphs.

图的Pfaffian定向问题是判定一个图是否有Pfaffian定向的问题。它是匹配理论中备受关注的困难问题，已被收集在《10000个科学难题（数学卷）》中。R.Thomas曾在2006年世界数学家大会上的45分钟报告中介绍了该问题的研究进展。本项目重点研究若干图类的Pfaffian结构性质，特别是亏格给定的图类及具有强对称性的图类；研究与图的Pfaffian定向问题密切相关的Brick图的结构特征和图的Pfaffian数，包括三正则Brick、极小Brick的结构特征及Brick的分类；运用图的Pfaffian定向理论，结合代数的方法研究NP－困难的完美匹配计数问题，特别是对物理或化学中有应用背景的网格图。这些问题的研究将促进图的Pfaffian定向问题的进展，丰富图的匹配理论。

图的Pfaffian定向问题是匹配理论中备受关注的困难问题，已被收集在《10000个科学难题（数学卷）》中。本项目研究了若干图类的Pfaffian结构性质；给出了匹配覆盖图中等价边集合最大基数的界，并刻画了匹配覆盖图中的可行边集，并以此构成了一类图，分别回答了He等人，Lukotka和Rollova提出的问题；否定了Carvalho,Lucchesi和Murty关于三正则solid bricks图的猜想；证明了Kothari,Carvalho,Lucchesi和Little关于essentially 4-edge-connected near-bipartite cubic bricks的一类可去边下界的猜想，推动对匹配覆盖图结构和Pfaffian图性质的研究进展。另外，在消防员问题、纽结染色、树相关问题和圈基等问题也取得了一些成果。