图的消圈数与不可分独立数

发布时间：2020-11-21 07:36

　　 图的消圈数和不可分独立数是图划分理论的两类经典问题,两者之间有着千丝万缕的联系.它们在无线传感器网络和组合电路设计等领域中有着广泛的应用,近些年来受到了极大关注.本文主要研究图的消圈数和不可分独立数及其应用.具体内容如下:1.首先对图论的一些基本概念和术语做了介绍.随后,比较全面地列举了与本文相关的消圈数和不可分独立数问题的研究背景、发展现状.最后给出了本文的主要结论.2.首先运用图嵌入的方法给出了一个计算次3-正则图的消圈数的公式.进一步,给出了在3-正则图中(?)成立的充分必要条件.3.借助消圈数这一参量分别建立了满足条件(?)的图是Hamilton图、泛圈图和边-Hamilton图的充分条件.4.首先给出一个计算图的不可分独立数的公式,然后借助这个公式求得了超立方体(?)的不可分独立数.随后,利用两个圈的笛卡尔积(?)的消圈数,给出了(?)的不可分独立数.与此同时,找到了(?)的最大不可分独立集.最后,刻画了次3-正则图的最大不可分独立集的分布,并对图的最大亏格和不可分独立数这两者的关系做了进一步讨论.5.首先借助最大割给出了计算图二部顶点挫败指标的具体公式,然后利用此公式得到了一些图类(包括稠密图)的二部顶点挫败指标的上界或者精确值.同时,我们研究了五类组合图的二部顶点挫败指标.最后,对稠密图的消圈数问题进行了探讨.
【学位单位】：华东师范大学
【学位级别】：博士
【学位年份】：2020
【中图分类】：O157.5
【部分图文】：

第二章图的消圈数与连通消圈数假设是这个点且()={,},易证=+连通且无三角形.若()≤2,通过归纳假设,它有一个森林满足||≥12(1)929≥()1.否则,是3-正则图.而Bondy等人[12]证明了对任一个无三角形的次3-正则图,()≥2|()|313.从而有一个森林满足||≥23(1)13≥()1.在以上任何一种情形中,均有∪{}是中阶数≥()的森林.断言5.若有一个2-度点,则()≥().假设是个2-度点且()={,}.由断言4可知和还有另外一个共同的邻居,记为.结合断言1,2,3,我们可以推导出()=()=()=3.接下来,分如下两种情况来讨论情况1.顶点和有除和外的第三个共同邻居,记为.在这种情形下,由断言3,()=3.假设和有除和以外的第三个共同邻居,记为.若()=2,那么是由{,,,,,}作为顶点集构成的边数为8的次3-正则图,并且={,,,}诱导出的一个森林(见图2.2.3).不难验证||≥62×8929.若()=3,则与的某条割边关联,这与是2-连通这一假设矛盾.所以,顶点对与只有两个共同的邻居,那就是和.这样,={,,}+连通且无三角形,从而它有森林满足||≥32(5)929≥()2.因此,∪{,}是的一个诱导森林且||≥().图2.2.3:()=2的情形.情况2.顶点和只有两个共同的邻居和.令和分别是和的第三个邻居.从断言3可知()=()=3.假设/∈(),={,,}++.显然,连通且无三角形.由归纳假设,有一个森林满足||≥32(5)923≥()2.从而∪{,}是的一个森林·19·

第二章图的消圈数与连通消圈数图2.3.1展示了当()的一个分支分别是4-圈,5-圈,4-路和5-路时,1,2,1的选取方式.图2.3.1:的选取方法.接下来,我们利用定理2.10来证明()=()在3-正则Halin图和广义Petersen图中均成立.Halin图是由德国数学家Halin提出的极小3-连通平面图.给定一棵树,其内部顶点度数至少为3.将嵌入到一个平面中,然后添加一些依次连接的叶子的边来组成一个圈.由此得到的图=∪即为Halin图,其中称为的特征树,为的伴随圈.我们把定理2.10应用到3-正则Halin图上,很容易得到()=().这是因为选取作为的一棵Xuong-树后,()的唯一可能的奇连通分支至少包含3条边.广义Petersen图,是由顶点集(,)={,:1≤≤}和边集(,)={,+1,+:1≤≤}构成的阶数为2的图,其中,正整数且>2.这里所有的下标均取模.令是和的最大公约数.为方便起见,记={:1≤≤},={:1≤≤}.Gao等人在文献[33]中刻画了广义Petersen图的内部结构.引理2.3(Gao等[33])[]是由长度为的个圈组成,且每个圈均可表示为如下形式=++2···+(1),下标取模,=1,2,...,.·21·

2:8,2与其Xuong-树.
【相似文献】

相关期刊论文 前10条

1 常立婷;师海忠;;基于超立方体和圈的细胞分裂生长网络及其性质[J];软件;2017年09期

2 赵学峰,李喜平;广义超立方体的点扩张[J];西北师范大学学报(自然科学版);2002年04期

3 王晓迪;;最优对称拉丁超立方体的构造[J];系统科学与数学;2020年02期

4 陈浩;张艳;;投影均匀分片拉丁超立方体设计[J];系统科学与数学;2020年02期

5 金丹;刘红美;张艳娟;;交换超立方体结构性质的一些注记[J];南阳理工学院学报;2018年02期

6 高炜;梁立;;块转换网络和分级超立方体网络的化学指标计算[J];苏州科技大学学报(自然科学版);2017年03期

7 曹瑾;肖力;徐俊明;;变形超立方体的圈和路嵌入(英文)[J];中国科学技术大学学报;2014年09期

8 蒋鲁威;梁家荣;;扭立方体网络到交换超立方体网络嵌入问题研究[J];广西科技大学学报;2014年03期

9 范漪涵;刘红美;刘敏;;故障折叠超立方体中的路和圈(英文)[J];数学杂志;2013年03期

10 梁锦叶;梁家荣;;交换超立方体网络的网络嵌入研究[J];计算机工程与科学;2011年08期

相关博士学位论文 前9条

1 曹法赟;图的消圈数与不可分独立数[D];华东师范大学;2020年

2 樊卫北;交换超立方体和3-元n-立方体在网格与环绕中的嵌入[D];苏州大学;2019年

3 刘晗;超立方体排队均衡下消防协同救援设施选址配置优化研究[D];哈尔滨工业大学;2018年

4 齐豪;扭曲超立方体和平面图的结构研究[D];浙江师范大学;2018年

5 陈浩;复杂结构拉丁超立方体设计的构造[D];南开大学;2013年

6 尹玉辉;拉丁超立方体设计的构造与超饱和设计的分析[D];南开大学;2013年

7 杜正中;容错网络的路和圈研究[D];中国科学技术大学;2006年

8 王国军;具有大量错误结点的超立方体网络容错模型和容错路由算法研究[D];中南大学;2002年

9 李显勇;几类光互连网络的诊断性与容错性[D];重庆大学;2014年

相关硕士学位论文 前10条

1 景小飞;类超立方体关于极大局部连通性的容错度[D];山西大学;2019年

2 杨进霞;广义b-基超立方体的控制参数及其圈积的Hamilton分解[D];西北师范大学;2019年

3 殷世德;图上的几类量子游荡的相关性质研究[D];西北师范大学;2019年

4 王垚;正交拉丁超立方体设计的子设计选择[D];东北师范大学;2019年

5 许萍;增增强超立方体的谱及其基尔霍夫指标[D];新疆大学;2019年

6 于雪;投影均匀下基于正交表的拉丁超立方体设计[D];东北师范大学;2018年

7 李德赛;大规模网络的容错性分析[D];清华大学;2017年

8 张伟华;两类网络的容错偶泛圈性研究[D];兰州理工大学;2018年

9 范娜琪;类超立方体的限制弧连通度[D];山西大学;2018年

10 李莉莉;超立方体及其变体结构网络的可靠性研究[D];西安电子科技大学;2018年

本文编号：2892741