图参数和满足规定性质的因子的存在性

来源 :南开大学 | 被引量 : 0次 | 上传用户:xiner1312
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
匹配理论,或更广的因子理论,是图论的—个基本研究领域.因子理论在最优化、网络设计、社会经济等领域中均有许多现实的应用.自从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]-奇因子存在的充分条件,并构造了一些例子来证明这些结果在某种程度上是紧的.最后一节给出了关于星因子的类似结果.
其他文献
作文教学是农村小学语文教学中的一个突出的难点.由于年龄小,智力发展水平较低,思维方式以形象思维为主,对抽象概括的写作,大部分学生觉得吃力.为了让每个学生学习在写作时顺
自从图乘积引入到图论中,它就和图论的许多其他深刻而有趣的问题建立了联系,这个结合不仅使得图乘积成为一种对图操作的重要手段,同时在解决像Hamilton分解和Hadwiger猜想等这样
零和理论是组合数论的一个重要研究分支,它与代数数论,图论,Ramsey理论以及离散几何等领域都有紧密联系。零和理论的主要研究对象是零和序列,也就是在加法有限交换群G中,元素之和
小学语文教育作为小学基础教育的关键环节,发挥着无可替代的作用.如何提高学生的综合素质,扩大学生的思想认识,关键在于小学语文课程的教育创新工作.当今社会以教育为根本,小
本文主要研究的是分形复合油藏非线性渗流解的相似结构,主要从以下四章进行说明:第一章,概述了国内外对分形复合油藏研究现状和发展趋势,并介绍了分形理论的基本概念;第二章,
偏微分方程最优控制理论是一个庞大的数学分支,涵盖了诸如时间控制,稳态控制,回馈控制,流体控制与分析以及用于机械制造的材料设计,晶体增长,化学反应中的最优控制等等许多方面的内
集合的排列是代数和计数组合学上最丰富的研究对象之一。由于排列统计量的信息能帮助我们更好地理解排列的结构,所以对排列上统计量的研究已经持续了很长一段时间,但依旧是当今
在我们研究很多分析问题时,各种各样的覆盖定理都发挥了非常重要的作用。在20世纪40年代,Besicovitch首次论证了今天的Besicovitch覆盖定理在2维平面上的正确性。随后两年,Morse
亲子沟通是实现家庭教育的重要途径。本文从亲子沟通的现状出发,总结了目前亲子沟通中存在的问题,并以心理学为依据,提出了亲子沟通的原则,以及具有操作性和针对性的亲子沟通
作为低年级的老师,应该重视孩子倾听能力的培养。本文将从细化要求,明确倾听的标准;设情境,促进学生倾听;以身作则,感受倾听美妙;适时评价,渗透倾听的方法这四个方面来阐述如