论文部分内容阅读
匹配理论,或更广的因子理论,是图论的—个基本研究领域.因子理论在最优化、网络设计、社会经济等领域中均有许多现实的应用.自从Lovasz和Plummer的经典著作《匹配理论》问世二十多年以来,因子理论蓬勃发展,取得了许多新的和有趣的进展,其中包括对各类因子的刻画.通常来说,验证图参数条件比验证其他刻画条件更为简单,并且图参数条件从不同角度反映了图的结构和性质,因此很多已有结果都试着探究图参数和因子存在性之间的关系,用图参数条件来刻画各类因子.本文主要考虑了满足规定性质的因子的存在性问题,研究这些因子与韧度、捆绑数和特征值这三个图参数之间的关系,本文有两个主要任务,其一是用韧度或者捆绑数条件来刻画具有包含/不包含性质的因子;其二是讨论特征值和诸如1-因子、[1,n]-奇因子、星因子这样的特殊因子之间的关系。此外,本文还研究了一些特殊图类中满足规定性质的1-因子的存在性问题.
整篇论文的架构如下.第一章先介绍了本文用到的一些符号和术语.1.2节致力于介绍图参数和因子的研究背景。首先我们给出了以韧度或捆绑数为条件的关于f-因子和[a,b]-因子的刻画,然后我们例举出一些已知结果,这些结果与韧度或捆绑数相关,也与具有边(或者顶点)包含/不包含性质的因子相关.最后,我们简要给出了本文的基本框架。
第二章主要给出了基于韧度的满足规定性质的f-因子存在的充分条件.对于—个含有至少五个顶点的2-坚韧图G和—个函数f:V(G)→{1,2},任给两条边el,e2∈E(G),我们证明了G中存在—个包含e1和e2的f-因子;—个不包含e1和e2的f-因子;以及—个包含e1、且不包含e2的f-因子。2.2节讨论了满足给定性质的1-因子.首先,我们介绍了一些关于k-因子和图参数的相关结果,以及具有边包含性质(可扩性)或顶点不包含性质(因子临界性)的1-因子的相关结果.然后,我们主要研究了乘积图中具有边包含性质和顶点不包含性质的1-因子的存在性问题,即乘积图的可扩性和因子临界性.在2.3节,我们给出了一些关于f-因子的后续研究问题,第三章致力于研究[a,b]-因子中的类似问题.3.1节研究了韧度条件下满足规定性质的[a,b]-因子,我们证明了如下结果:对于一个不完全图G,如果其韧度t(G)≥(a一1)+a/b,其中a,b是满足b>a>1的整数,那么对于任意给定的两条边e1和e2,存在—个包含e1,e2的[a,b]-因子;—个包含e1且不包含e2的[a,b]-因子;以及一个不包含e1,e2的[a,b].因子,除非a=2且e1和e2具有一个公共顶点.对于完全图,我们同样得到了一个类似结果.3.2节讨论了用捆绑数刻画满足规定性质的[a,b]-因子的问题.在3.3节,我们首先给出了包含任意七条独立边的[1,2]-因子存在的充分条件,然后考虑了在韧度条件下,包含任意一条边的[2,b]-因子的存在性问题,在本章结尾,我们给出了两个可以继续研究的问题。
第四章讨论了特征值和[1,n]-奇因子之间的联系,以及Laplacian特征值和星因子之间的联系.一直以来,图的特征值被广泛地用来研究图的性质和图的核心参数,这些参数包括染色数、独立数、团数等.Brouwer和Haemers[13]最首先考虑了用图的特征值来研究因子,类似地,我们得到了基于特征值的[1,n]-奇因子存在的充分条件,并构造了一些例子来证明这些结果在某种程度上是紧的.最后一节给出了关于星因子的类似结果.