几类网络图的广义连通度

论文摘要

当今社会是由各种网络构成的社会,例如,铁路网络,公路网络,通信网络和无线传感器网络等等.为了达到运输和通信等目的,网络通常要满足特定的参数要求.一个网络通常可以抽象成一个图,从而对网络参数的要求可以转化为对图参数的要求,例如,欧拉性,哈密尔顿性和连通性.连通度是图论的基本概念之一,它可以衡量一个通讯网络的可靠性.如果一个图的连通度越高,则在图的顶点和边发生故障时,该网络仍然可以运转的可能性越大.由于经典连通度衡量网络连通性有缺陷,近年来,数学家们又引入了一些新的连通度概念,例如限制连通度,本质连通度,和广义连通度等.本文主要研究几类网络图的广义连通度.给定一个图G,S是图G的一个至少包含两个顶点的集合.如果集合S中的顶点包含在某棵树T中,则树T称为一棵S-斯坦纳树.如果两棵S-斯坦纳树T1和T2的边的交集为空,即E（T1）∩E（T2）=?,则称T1和T2是边不交的;类似地,如果两棵S-斯坦纳树T1和T2的边的交集为空且顶点的交集为S,即E（T1）∩E（T2）=?和V（T1）∩V（T2）=S,则称T1和T2是内部点不交的.定义λG（S）（κG（S））为图G中边（内部点）不相交的S-斯坦纳树的最大棵数,并且当S取遍图G中所有的k元子集时,定义λk（G）（κk（G））为λG（S）（κG（S））中的最小值.显然,λ2（G）（κ2（G））就是经典的边（点）连通度λ（G）（κ（G））.本文我们主要通过递归循环图的循环结构和哈密尔顿性质,根据S中的点的分布情况,构造出边不交的S-斯坦纳树的最大棵数,进而确定该递归循环图G（N,d）的λ3-连通度;类似地,根据S中的点的分布情况,构造出点不交的S-斯坦纳树的最大棵数,进而确定该递归循环图G（N,d）的κ3-连通度.另外,我们还通过树的卡氏积的结构及其性质,构造出边不交的S-斯坦纳树的最大棵树,最终确定树的卡氏积(Tn1（?）Tn2（?）···（?）Tnk)的λ4-连通度.

论文目录

文章来源

类型: 硕士论文

作者: 王佳佳

导师: 李恒哲

关键词: 斯坦纳树,广义边连通度,广义点连通度,递归循环图,卡氏积

来源: 河南师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 河南师范大学

分类号: O157.5

DOI: 10.27118/d.cnki.ghesu.2019.000726

总页数: 54

文件大小: 2240K

下载量: 9

相关论文文献

• [1].水文连通度对湿地生态系统服务功能影响综述[J]. 南京师范大学学报(工程技术版) 2020(01)
• [2].交换折叠超立方体的超连通度[J]. 安徽师范大学学报(自然科学版) 2020(03)
• [3].秦淮河流域水系结构及连通度变化分析[J]. 水利水电科技进展 2020(05)
• [4].完全对换图的广义3-连通度（英文）[J]. 曲阜师范大学学报(自然科学版) 2019(01)
• [5].完全对换网络的嵌入连通度[J]. 新疆大学学报(自然科学版) 2019(01)
• [6].交换折叠交叉立方体的连通度和超连通度（英文）[J]. 吉首大学学报(自然科学版) 2019(05)
• [7].交叉立方体的限制性连通度（英文）[J]. 曲阜师范大学学报(自然科学版) 2018(03)
• [8].给定团数的连通图的最小代数连通度[J]. 应用数学学报 2016(06)
• [9].有向笛卡尔积图的k-限制弧连通度[J]. 河南科学 2017(03)
• [10].星型网络的额外连通度[J]. 广西科技大学学报 2015(03)
• [11].一种基于时间演化模型的机会网络连通度测度[J]. 青海师范大学学报(自然科学版) 2019(01)
• [12].基于序列连通度的睡眠分期算法研究[J]. 电子学报 2017(01)
• [13].机会传感网络连通度影响因素与连通度模型[J]. 北京邮电大学学报 2015(06)
• [14].线图的限制性邻域连通度[J]. 山东大学学报(理学版) 2012(02)
• [15].道路网的实况连通度指标[J]. 测绘与空间地理信息 2010(01)
• [16].线图的邻域连通度(英文)[J]. 新疆大学学报(自然科学版) 2009(04)
• [17].平衡立方体的h-额外连通度及h-额外条件诊断数[J]. 高校应用数学学报A辑 2019(01)
• [18].基于网络拓扑图的树的代数连通度[J]. 计算机工程与应用 2017(03)
• [19].给定控制数的树的代数连通度[J]. 西安文理学院学报(自然科学版) 2016(01)
• [20].基于自然连通度的复杂网络抗毁性分析[J]. 复杂系统与复杂性科学 2014(01)
• [21].东圳水库流域的景观连通度分析[J]. 亚热带资源与环境学报 2014(01)
• [22].正则图的代数连通度[J]. 四川师范大学学报(自然科学版) 2012(02)
• [23].网络连通度算法的性能分析与比较[J]. 福州大学学报(自然科学版) 2012(03)
• [24].基于社团连通度的复杂网络抗毁性分析[J]. 军事运筹与系统工程 2019(04)
• [25].基于建筑倾倒优势方向的疏散路网连通度模型[J]. 重庆交通大学学报(自然科学版) 2018(12)
• [26].图的代数连通度[J]. 亚太教育 2016(14)
• [27].定向图弧连通度的下界[J]. 晋中学院学报 2015(03)
• [28].有向线图的等周弧连通度(英文)[J]. 新疆大学学报(自然科学版) 2014(02)
• [29].给定控制数的树的代数连通度的上界[J]. 吉首大学学报(自然科学版) 2008(02)
• [30].土壤侵蚀研究中的景观连通度:概念、作用及定量[J]. 地理研究 2016(01)

标签：斯坦纳树论文;  广义边连通度论文;  广义点连通度论文;  递归循环图论文;  卡氏积论文;