特殊图类的偶匹配可扩性

来源 :新疆大学 | 被引量 : 3次 | 上传用户:nothingme
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
匹配理论是图论的核心内容之一.由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论结果.例如,刻画偶图具有完美匹配的Hall定理、刻画一般图具有完美匹配的Tutte定理、不具有完美匹配图的Gallai-Edmonds结构定理、求偶图最大权匹配的匈牙利方法、求非偶图最大权匹配的开花算法等,都是影响深远的传世之作.同时关于匹配的一系列研究专题不断涌现出来.例如,匹配多面体、基本图(elementary graph)、因子临界图、完美匹配计数等都成为活跃的研究领域.匹配可扩性―包括k-可扩性、导出匹配可扩性和k-因子临界性―也是其中之一. k-因子临界图和k-可扩图有密切的关系: 2k-临界图是k-可扩的;对于每一个连通的非偶图,如果它是k-可扩的,k是偶数,那么它是k-因子临界的.在k-可扩图、导出匹配可扩图和k-因子临界图的研究工作基础上,考虑到非偶图匹配问题与偶图匹配问题有本质差别的事实,王秀梅[1]在2005年提出另外一个新的概念―偶匹配可扩图.称图G的匹配M是偶匹配,是指M关联的顶点集在G中的导出子图是偶图.称图G是偶匹配可扩的(简称BM-可扩的),是指G的每一个偶匹配都可以扩充为G的一个完美匹配.基于以下两方面的动机,BM-可扩图是值得深入研究的.一方面,BM-可扩图与其他匹配可扩图的关系很密切,构成了一个整体:其中m(G)是图G的最大匹配的基数.事实上,对BM-可扩图的任何研究进展都是对整个匹配可扩性理论的贡献.特别地,揭示从偶图匹配到非偶图匹配的演变规律也是有重要意义的.另一方面,BM-可扩图在化学图论中也有潜在的应用.在量子化学中,一个分子图G的Kekul′e结构就是完美匹配M;所谓共振圈就是M-交错圈.共振圈中的匹配实际上是一个偶匹配,它包含于G的完美匹配之中.因此共振圈概念与BM-可扩图有着自然的联系.正因如此,在已知的BM-可扩图中,其Clar指标(两两不相交的共振圈的最大数目)达到最大,可见对应分子结构具有最大可能的谐振能量.从Kekul′e结构计数的观点上看,这类分子结构由于完美匹配数目很大,也有良好的稳定性.在已有的理论中,关于k-可扩图、导出匹配可扩图、k-因子临界图的研究内容,除了基本性质外主要集中在:结构特征、与图参数的关系、特殊图类的刻画、极图问题等.在系统地掌握该领域的文献资料和前沿工作的基础上,本学位论文对王秀梅提出的新概念― BM-可扩图的研究也是围绕上述主流课题(特殊图类Halingraphs、K1,3-free bicritical graphs)进行的,本学位论文主要取得如下两个方面的创新成果.1.哈林图是偶匹配可扩的充要条件本文证明了判定哈林图H = (T C)是否为偶匹配扩图的充分必要条件问题:哈林图H = (T C)是BM-可扩的充分必要条件是它的特征树T同构于K1,3、K1,5或者K1,7.2.无爪双临界偶匹配可扩图的结构特征本文主要证明了无爪双临界偶匹配可扩图的几个性质.所有的这些结果在以后的研究中会起到基础作用.关于BM-可扩图与因子临界图及双临界图的关系,王秀梅已经证明了:如果G是BM-可扩图,那么G或者是双临界的或者是可均衡分解的.如果G是可均衡分解的,那么G?S的每一个分支都是因子临界的,其中S是G的一个极大屏障.本文得到的结果如下: (1.)对于任意临界偶匹配可扩图G,如果{u,v}是G的点割,那么点{u}邻接点{v}. (2.)无爪双临界偶匹配可扩图是3连通的. (3.)对于任意无爪临界偶匹配可扩图G,如果{x,y,z}是G的点割,那么点割{x,y,z}是G的独立集,并且G?{x,y,z}仅有两个分支,奇分支G1、偶分支G2,这里|G1| = 1、|G2|≥6.
其他文献
种群动力学就是通过对所研究的生态学问题进行大量的实验,并施行统计分析以及合理细致的机理分析,建立微分积分方程形式的数学模型,来研究一个生态系统中相互作用的一些或所有种群的长期变化规律,如:种群的持久性,持续生存性,灭绝性和全局渐近稳定性等等.本文分别对两个单种群模型进行研究讨论,具体内容如下:第一节为绪论,介绍了反馈控制种群模型产生的生物背景及其意义,以及单种群反馈控制种群动力学模型的研究发展情况
众所周知,利用伪随机数的传统蒙特卡罗(MC)方法收敛速度比较慢,收敛速度为O(N-1/2)。为了克服这个缺点,我们利用超均匀随机数来代替伪随机数以取得较好的效果。在MC方法中利用超均匀序列称为拟蒙特卡罗(QMC),我们可以给出QMC的理论上确界,但不能计算它的误差估计。为了弥补MC收敛速度慢和QMC不能计算误差的缺点,我们可以通过对拟随机数进行随机化(加扰),这种方法我们称之为随机化拟蒙特卡罗(R
众所周知,研究各种离散时间的种群动力学模型不仅具有广泛的生物理论意义,还具有重要的实际应用价值.近年来,越来越多的学者对离散时间种群动力学模型的研究产生了兴趣,得到了非常多的研究成果.本文,我们将继续这类研究,讨论一般的非自治离散时间多种群Kolmogorov模型的持久性以及两类离散周期模型的周期解的存在性.主要内容可以概述如下:在第一节中,我们首先介绍了离散时间种群模型的生物背景.然后介绍了各种
本文共分二章.第一章分二节.第一节回顾可靠性理论的历史.第二节中首先介绍补充变量方法,然后提出本文要研究的问题.第二章共分二节.第一节首先介绍由一个可靠机器,一个不可靠机器与一个缓冲库构成的系统的数学模型,接着引入状态空间,算子及其定义域,然后将该模型转化成Banach空间中的抽象Cauchy问题,最后介绍其他学者有关于此模型的研究成果.第二节首先研究此模型主算子的特征值,证明±(?)-γη1-μ
随着信息网络的飞速发展,许多与之相关的理论性问题越来越引起人们的重视,其中之一就是网络稳定性.一个网络的稳定性是在已知某些网络节点损坏的情况下衡量该网络是否能够正常工作的能力.这是网络设计和构造的基本思想之一.一个网络可以模型为一个图,网络的稳定性可以由该图的各种连通性指标来衡量.在本文中我们研究了其中一个参数,就是限制性边连通度.一个连通图G = (V,E)的一个边子集S叫做一个k限制性边割,如
在本文中我们考虑的都是有限的无向简单图.一个图G的全图T(G)的顶点集是V (G)∪E(G),其中任意的两个点相邻当且仅当它们在G中相邻或关联.吴和孟把全图进行推广提出了变换图的概念.在本文中,我们将研究一个图G的一种变换图G+??.变换图G+??的顶点集是V (G)∪E(G),两个点u和v在G+??中相邻如果满足下面的任何一个条件:(i) u,v∈V (G)并且它们在G中是相邻的, (ii) u
本文建立了一类带有漏隙接种的非终生免疫的年龄结构的SEIR传染病模型,讨论了这个模型的解的适定性.首先把问题(P)化为等价的积分方程组(H),通过定义算子将问题(H)转化成一个算子不动点的唯一性问题;然后利用算子不动点证明积分问题(H)局部解的存在唯一性,进而得到积分问题(H)的解的整体存在唯一性、解关于初值的连续依赖性及C1光滑性,从而得到问题(P)的解的适定性.在对模型稍作简化的情况下讨论了无
本文只考虑简单图,有向图可以有环,但没重弧(弧具有相同的头和尾)。网络往往模型化为无向图或有向图。衡量网络稳定性的经典参数为图的连通度和边连通度,为了进一步研究,人们提出了各种各样的高阶连通度概念,如超点连通性、超边连通性、超混合连通性、hyper-连通性、限制性边连通度等等。本论文主要研究图图的高阶连通性。本文共分三章。第一章引言主要介绍稳定性参数的一些背景和一些基本概念。第二章主要研究了两种特
一个网络可以模型为一个图,网络的稳定性可以由该图的各种连通性指标来衡量.在本文中我们研究了其中一个参数,就是3-限制性点边连通度.一个连通图G = (V,E)的一个边集S叫做一个k-限制性边割,如果G ? S是不连通的,并且G?S的每一个分支至少含有k个点.一个图的k-限制性边连通度,记为λk(G),就是最小的k-限制性边割所含边的数目.从这个参数的最近一些研究结果来看,λk越大,网络就越稳定.定