对缺失n可扩图的研究

Defect n-extendable graphs are the extention of n-extendable graphs on graphs with odd order. If a vertex in the bipartion with more vertecies of a defect 2-extendable bipartigrah is deleted, the remaining graph is an elemantary graph. Elemantary graphs are the basic classs of graphs in matching theory. So the study of defect n-extendable graphs will contribute to the development of matching theory. In the mean time, defect n-extendable bipartite graphs are the mathematical model of the problem of distributing resources to tasks when the number of resources is exactly one more than the number of task. The study of defect n-extendable graphs helps to solve this type of application. It's known from the current result that the results of defect n-extendable graphs are not a simple extension of those of n-extendable graphs. So it is worth to study defect n-extendable graphs individually. But the existing results about defect n-extendable graphs mainly focus on defect 1-extendable bipartite graphs. This project plans to study the structure, characterization, effective algorithm and properties of defect n-extendable bipartite graphs. And then study the structure and characterization of general defect n-extendable graphs. The research results will fill in the blank of the researches in these area and will be a foundation for the further study of general defect n-extendable graphs. Moreover, the study of this project will help a further development of matching theory.

缺失n可扩图是对n可扩图在奇数顶点的图上的扩展。在连通度不小于2的缺失2可扩偶图顶点数较多的分类中任意删除一个顶点，剩下的图是基本图，而基本图是匹配理论中的基础图类，因此对缺失n可扩图的研究进展也是对整个匹配理论的贡献。同时，缺失n可扩偶图是任务数与资源数相差1的资源可扩分配问题的数学模型。对缺失n可扩图的研究，有助于解决这类应用问题。此外，从已有的关于缺失n可扩图的结论可知，缺失n可扩图的结论并不是n可扩偶图的已知结论的简单移植。因此，缺失n可扩图是值得研究的。现有的对缺失n可扩图的结论主要集中在缺失1可扩偶图。本项目拟从缺失n可扩偶图的结构、刻画、有效判定算法和图参数性关系等方面对缺失n可扩偶图进行研究，进而研究缺失n可扩一般图的结构和刻画。研究成果将填补当前对缺失n可扩图以上方面研究的空白，为进一步研究缺失n可扩一般图奠定基础，使可扩图理论更为充实和完整，促进匹配理论的发展。

缺失n可扩图是对Plummer提出的n可扩图在奇数顶点的图上的扩展，是匹配理论中的基础图类，因此，对缺失n可扩偶图的研究进展也是对整个匹配理论的贡献。同时，缺失n-可扩偶图是任务数与可用资源数相差1的可扩资源配置问题的数学模型，对缺失n-可扩偶图的研究，不但有助于解决这类应用问题，而且对于解决任务书和资源数相差大于1的资源分配问题也有一定的辅助作用。本项目对极小缺失n可扩偶图的刻画、有效判定算法、最小点数的缺失n-可扩偶图的刻画、平面图缺失n-可扩图的性质进行研究。用M-交错路以及通过删除割点得到的连通分支的性质分别刻画了不同连通度和n值的极小缺失n-可扩偶图，找到了比极小缺失n-可扩偶图定义更有效判定算法；通过构造图例证明了连通度为1的平面图可能为任意缺失n-可扩图；此外，在对缺失n-可扩图哈密顿性研究过程中也得到了有向图存在有向哈密尔顿圈的充分条件以及存在完美对集M的偶图G包含M-交错哈密顿圈的充分条件并揭示了1-可扩图与完美2-对集覆盖图之间的关系以及极小1-可扩图与极小完美2-对集覆盖图的关系。研究成果填补了当前对缺失n-可扩图以上方面研究的空白，为进一步研究缺失n-可扩一般图以及两个分类的顶点数相差大于1的可扩图的研究奠定基础，使可扩图理论更为充实和完整。