图的因子及相关问题研究

论文摘要

图论是离散数学的一个分支,广泛地应用于许多领域,同时,交叉运用多学科知识又衍生出了极值图论、超图论、复杂网络、算法图论、模糊图论等许多的分支.因子理论是图论中活跃的研究课题之一,近年来受到了极大的关注,它在计算机科学,网络设计和编码设计中有着广泛的应用.本文主要研究图的因子与图的参数之间的联系,从而给出图因子的存在性条件.由于图的各种参数可以从不同的侧面反映出图的内在结构与性质,因此本文侧重借助图的一些参数来刻画分数临界图和分数覆盖图的存在性,这些参数包括韧度、联结数、连通度、最小度和邻域并等.本文的结构如下:第一章是绪论部分.第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-子图的充分条件.第七章是结语与展望,包括本文的主要内容以及可以进一步研究的问题.

论文目录

• 致谢
• 摘要
• ABSTRACT
• 1 绪论
•   1.1 研究背景及意义
•   1.2 相关领域的研究动态
•     1.2.1 图的连通因子
•     1.2.2 图的配类因子
•     1.2.3 图的分数因子
•     1.2.4 超图的匹配
•   1.3 本文的研究内容
• 2 预备知识
•   2.1 图的基本概念和符号
•   2.2 因子理论中的常用参数
•     2.2.1 韧度
•     2.2.2 联结数
•     2.2.3 其他参数
• 3 所有分数（a,b,k）-临界图存在的条件
•   3.1 预备知识
•   3.2 所有分数（a,b,k）-临界图存在的韧度条件
•     3.2.1 主要结论
•     3.2.2 注记
•   3.3 所有分数（a,b,k）-临界图存在的连通度条件
•     3.3.1 主要结论
•     3.3.2 注记
•   3.4 小结
• 4 分数ID-[a,b]-因子临界图存在的邻域并条件
•   4.1 引言
•   4.2 预备知识
•   4.3 主要结论
•   4.4 注记
•   4.5 小结
• 5 分数覆盖图存在的条件
•   5.1 预备知识
•   5.2 分数[a,b]-覆盖图存在的度条件
•     5.2.1 主要结论
•     5.2.2 注记
•   5.3 分数[a,b]-覆盖图存在的邻域并条件
•     5.3.1 主要结论
•     5.3.2 注记
•   5.4 分数k-覆盖图存在的联结数条件
•     5.4.1 主要结果
•     5.4.2 注记
•   5.5 小结
• 6 二部图的随机正交因子化
•   6.1 引言
•   6.2 预备知识
•   6.3 主要结果及证明
•   6.4 小结
• 7 结语与展望
• 参考文献
• 作者简历及攻读博士学位期间取得的研究成果
• 学位论文数据集

文章来源

类型: 博士论文

作者: 袁园

导师: 郝荣霞

关键词: 分数因子,所有分数,临界图,分数,因子临界图,分数覆盖图,随机正交因子化

来源: 北京交通大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 北京交通大学

分类号: O157.5

总页数: 106

文件大小: 3608K

下载量: 39