图的匹配理论的多面体方法

图的匹配理论有着广泛的应用背景、丰富的研究课题及深刻的理论结果。由Edmonds创立的匹配多面体理论被认为是数学规划理论与图论的完美结合。本项目旨在探讨用多面体方法研究匹配理论，推进若干方面的理论发展。 第一，研究Fan-Raspaud猜想（任意无割边3-正则图中存在三个完美匹配其交集为空）。我们已初步确立运用完美匹配多面体证明此猜想的途径，取得部分结果，并实现了与刻面刻画、brick分解、可去边存在性等理论课题的联系。第二，对已有匹配可扩结构，尚有不少未解问题，包括Plummer猜想（存在多项式时间算法确定一个图的可扩度）。这个兼有算法与结构特征的问题也是本项目的主攻方向之一。第三，关于唯一可扩问题，研究PM-紧邻图，即除去一个交错圈后，具有唯一完美匹配的图。一方面这是完美匹配多面体具有直径一的刻画问题，具有独立的学术价值，另一方面也是证明Fan-Raspaud猜想的一个难点。

图论与组合最优化是两个交融渗透，互相促进发展的研究领域。匹配理论是图论与组合最优化的核心课题之一。而匹配多面体是整数规划与图论的完美结合。本项目研究与完美匹配多面体相关的匹配问题，包括图的结构性质和算法。研究成果如下：受本项目资助共发表学术论文22篇，其中16篇论文发表于SCI期刊上，包括1篇发表在数学类一区期刊上。本项目的代表性成果如下：（1）对于图的匹配覆盖问题（用最少的匹配覆盖图的顶点），给出了多项式时间算法：一般图的时间界是O(n3)，树的时间界是O(n)；同时给出匹配覆盖数的界和树情形匹配覆盖数的精确刻画。该论文2014年发表在数学类一区top期刊Mathematical Programming, Ser. A。（2）对于三匹配交猜想（范-Raspaud猜想），证明当完美匹配多面体的维数小于等于10的情况猜想成立；并把猜想归到完美匹配多面体是3-平坦的情形；（3）对于有唯一完美匹配的图，推广前人的成果给出了一个具有结构特性的充分必要条件，利用该条件对具有唯一完美匹配的一些特殊图类给出了结构刻画；（4）关于可去边的存在性，Carvalho, Lucchesi及 Murty (2002) 证明Lovasz的猜想：在brick中存在两条边，对于每一条边的边删子图其brick-分解只有一个Brick。我们把这个结果推广到near-brick的情形。