[00105266]一致超图 Ore 型问题研究

该项目为中国博士后科学基金资助面上项目（资助编号：2019M660562）。

匹配（完美匹配）和圈（Hamilton 圈）是组合图论中非常重要也是非常基本的两个结构，在过去的几十年里，被证明匹配和圈可以作为很有效的工具去解决一些实际的问题，比如‘Santa Claus’分配问题；在理论上也有很重要的应用，比如组合学中两个公开的问题：组合设计的存在问题和 Ryser 猜想：奇数阶的拉丁方有一个横贯，都可以等价于证明一些特殊的超图有一个完美匹配问题。Edmonds 给出一般图存在完美匹配的有效算法，但是 Karp 证明

3 一致超图的完美匹配存在问题是一个 NP-C 问题。对于 Hamilton 圈，Karp 甚至证明一般图

包含一个 Hamilton 圈是一个 NP-C 问题。因此不期待能够找到一个好的刻画，很多的专家学者把重点放在给出超图存在完美匹配或者 Hamilton 圈的充分条件上。

超图中有几个非常自然的参数（1）最小度；（2）顶点度和最小值，两个独立顶点或者两个相邻顶点或者两个任意顶点的度和最小值；（3）边数。那么一个很自然的问题是最小度（或者两个顶点的最小度和，或者最少的边数）为多少可以确保超图存在一个匹配（完美匹配） 或者 Hamilton（紧）圈。对于一般的图，该问题仍然是一个公开问题。当前专家学者主要从最小度和，边数两个角度研究超图完美匹配或者匹配的存在性；主要从最小度研究超图Hamilton 圈的存在性。该项目主要从两个相邻顶点的最小度和角度研究超图的匹配存在性。另一方面完全一致超图或者完全 n-平衡 r-部 k-一致超图的完美匹配或者 Hamilton 紧圈

分解也吸引了很多专家学者的关注。该项目也给出了 n-平衡k 1-部 k-一致超图存在一个完美匹配或者 Hamilton 紧圈分解的充分条件。