图的因子及相关问题研究

来源 :北京交通大学 | 被引量 : 0次 | 上传用户:wushenjian
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论是离散数学的一个分支,广泛地应用于许多领域,同时,交叉运用多学科知识又衍生出了极值图论、超图论、复杂网络、算法图论、模糊图论等许多的分支.因子理论是图论中活跃的研究课题之一,近年来受到了极大的关注,它在计算机科学,网络设计和编码设计中有着广泛的应用.本文主要研究图的因子与图的参数之间的联系,从而给出图因子的存在性条件.由于图的各种参数可以从不同的侧面反映出图的内在结构与性质,因此本文侧重借助图的一些参数来刻画分数临界图和分数覆盖图的存在性,这些参数包括韧度、联结数、连通度、最小度和邻域并等.本文的结构如下:第一章是绪论部分.第1.1节简单介绍了图因子理论的研究背景和意义;第1.2节分析了相关领域的研究历史和最新研究现状,比如图的连通因子、配类因子、分数因子和超图匹配等;第1.3节给出了本文的主要结论.第二章是预备知识部分.我们首先介绍了图论中用到的一些概念和符号,然后给出了图因子理论研究中常用的参数,比如韧度,联结数以及邻域并等.第三章主要讨论了所有分数临界图存在的韧度和连通度条件,得到了下列的结果:·借助于韧度我们给出了所有分数(a,b,k)-临界图存在的充分条件,证明了当韧度τ(G)≥(b2-1)+ak/a 时,G是所有分数(a,b,k)-临界的;并进一步证明韧度的界是紧的(见第3.2节).·利用连通度我们得到了所有分数(a,b,k)-临界图存在的充分条件,证明了若κ(G)≥max{((b+1)2+2k/2,(b+1)2α(G)+4ak/4a},则G是所有分数(a,b,k)-临界的;并讨论了连通度的下界是紧的(见第3.3节).第四章研究了分数ID-[a,b]-因子临界图存在的判定条件,主要结果如下:若图中任意独立集{x1,x2,…,xr}的邻域并满足|NG(x1)∪ NG(x2)∪…∪NG(xr)|≥(a+b)n/a+2b,则该图是分数ID-[a,b]-因子临界的.同时,我们证明了邻域并的界是紧的.本结果改进了Zhou,Yang和Sun[Discuss.Math.Graph Theory,2016,36(2):409-418]的下列结果:若任意不相邻的点对x,y满足|NG(x)∪NG(y)|≥(a+b)n/a+2b,那么G是分数ID-[a,b]-因子临界的(见第4.3节).在第五章,我们用度、邻域并和联结数条件给出分数覆盖图存在的充分条件,主要得到了以下结果:·运用顶点度给出了分数[a,b]-覆盖图存在的充分条件,证明了若图中任意不相邻的点对x,y满足max{dG(x),dG(y)}≥a(n+1)/a+b 那么该图是分数[a,b]-覆盖的.此结果推广了[Ars Comb.,2015,118:135-142]中关于分数k-覆盖图的结论.最后也证明了所给顶点度的下界是紧的(见第5.2节).·利用邻域并给出了分数[a,b]-覆盖图存在的充分条件,证明了对于给定的整数r≥2,当G中任意独立集{x1,x2,…,xr}的邻域并满足|NG(x1)∪NG(x2)∪…∪ NG(xr)|≥a(n+1)/a+b聲时,G是分数[a,b]-覆盖的.当a= = 且r=2时,作为主要结果的推论,我们可以推出[Ars Comb.,2015,118:135-142]中的结论.此外,证明了邻域并的下界a(n+1)/a+b是紧的(见第5.3节).·借助于联结数给出了分数k-覆盖图存在的充分条件,证明了若bind(G)>(2k-1)(n-1)/kn-2k,那么G是分数k-覆盖的.本节最后讨论了联结数的界(2k-1)(n-1)/kn-2k是紧的(见第5.4节).第六章主要探究了二部(0,mf-m+ 1)-图G的随机正交因子化问题,给出了G存在(0,f)-因子化随机r-正交于任意给定的若干个点不交的mr-子图的充分条件.第七章是结语与展望,包括本文的主要内容以及可以进一步研究的问题.
其他文献
学位
学位
云计算的发展和普及,使越来越多的用户感受到了云服务的便利。如何高效调度云任务已成为云提供商为用户提供服务时需要面对的一大问题。任务调度算法是云计算的关键技术,论文针对已有任务调度方法中准确预测任务执行时间难度大、无法同时满足任务全局优先级和任务依赖关系的问题,提出基于资源感知的动态云任务调度算法TPN-GA,旨在提高云计算环境中的任务调度效率。论文工作有以下几方面的创新之处。1.提出一种基于弹性网
学位
学位
作业是连接课程、课堂和评价的关键环节。"双减"背景下的作业设计成为当下关注的热点和焦点。文章从地理作业设计的依据、理念、目标、理论、原则、路径、框架七个方面展开探讨,绘制了"轻负优质""减负增效"的作业设计图景。
学位
基础施工质量是保障桥梁整体结构安全的关键因素,钻孔灌注桩在保障基础稳定性和提高基础承载力方面效果显著,是桥梁基础加固中常用的技术之一。为保证施工质量,必须要在施工期间落实精细化管理,在施工结束后及时开展质量检验。本文以某桥梁工程为例,首先介绍了工程基本信息和钻孔灌注桩施工流程,随后重点分析了施工准备、埋设护筒、旋挖钻孔、吊放钢筋笼、浇筑混凝土等施工环节的技术要点。最后随机选取10根桩进行质量检验,
学位