匹配理论的若干新结果

论文摘要

匹配理论是图论的一个基础分支，同时在理论化学、组合优化等研究中有十分重要的应用。目前匹配理论的主要研究方向之一是具有特定性质的存在完美匹配的图的构造和性质，比如：基本图、n-可扩图、k-临界图、k-圈共振图等，以及如何计算图的完美匹配数。本文主要研究一些在进行特定的顶点收缩运算后仍具有完美匹配的图的性质，并得到了一些特殊图类完美匹配数的上、下界。 下面是本文的一些主要结果。 1．通过引入两种图的收缩运算：α（2n+1）-收缩运算和β2n-收缩运算，定义了两类新的图类，即（2n+1）-可收缩图和2n-对可收缩图。(令G是一个图。设S（?）V（G）且|S|=2n+1。将S收缩为一个顶点后所得到的图记α（2n+1）（G，S）。若G有完美匹配且对于任意S（?）V（G），|S|=2n+1，图α（2n+1）（G，S）仍有完美匹配，则称G是一个（2n+1）-可收缩图。设S1，S2，…，S2n是V（G）的两两不相交的子集，将Si，i=1，2，…，2n，分别收缩为一点所得到的图记β2n(G，S1，S2，…，S2n)。若G有完美匹配且对于V（G）的任意2n个两两不相交的子集S1，S2，…，S2n，其中|S1|=|S2|=…=|S2n|=2，图β2n(G，S1，S2，…，S2n)仍有完美匹配，则称G是一个2n-对可收缩图)．我们利用Tutte定理给出了这两类图的充要条件和基本性质，讨论了它们与n-可扩图及2n-临界图间的关系。 2．利用α（2n+1）-收缩运算和β2n-收缩运算，给出n-可扩二部图的一些新刻划。 3．确定了具有某些结构性质的图的完美匹配数紧的上界，其中，连通度为k的2n阶图的完美匹配数紧的上界为k[（2n-3）!!]，独立数为k的2n阶图的完美匹配数紧的上界为[（?）（2n-k-i）][（2n-2k-1）!!]，而色数为k的2n阶图的完美匹配数紧的上界为Turan图Tk，2n的完美匹配数φ(Tk，2n)。 4．分别确定了偶阶极大外平面图与树状三角系统和四角系统的完美匹配数的紧的上、下界。另外运用组合递推法和匹配因子定理给出了若干四角系统的完美匹配数的显式表达式。

论文目录

• 中文摘要
• 英文摘要
• 第一章 序言
• 1.1 匹配理论研究的一些背景及进展
• 1.2 本文的主要结果
• 第二章 （2n+1）-可收缩图和2n-对可收缩图
• 2.1 引言
• 2.2 （2n+1）-可收缩图的刻划及其性质
• 2.3 2n-对可收缩图的刻划及其性质
• 第三章 n-可扩图的若干新性质
• 3.1 引言
• 3.2 n-可扩二部图的若干新刻划
• 3.3 1-可扩图的去边分解
• 第四章 若干图类的完美匹配数的上、下界
• 4.1 具有某些结构性质的图的完美匹配数的紧的上界
• 4.2 偶阶极大外平面图与树状三角系统的完美匹配数的紧的上、下界
• 4.3 树状四角系统的完美匹配数的紧的上、下界
• 第五章 一些图类的完美匹配数的计算
• 5.1 若干四角系统的完美匹配数
• 5.2 计算路状四角系统的完美匹配数的标数字法
• 5.3 计算完美匹配数的有限域法
• 参考文献
• 作者在攻读博士学位期间完成的有关学术论文
• 致谢