图的连通与广义连通度研究

来源 :天津大学 | 被引量 : 0次 | 上传用户:zgkjzh1
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着信息科学与互联网技术的迅猛发展,各种网络相互交织形成一个庞大的信息服务系统,为人们的生活、工作提供了各种便捷.但是随着网络结构和网络环境的日益复杂,各种网络故障也是时有发生且后果愈加严重.研究表明,网络内部设施或组织失效导致的网络故障的几率随着网络硬件技术的提高而逐步降低,而自然灾害或人为破坏造成的重大事故却成了故障发生的主要原因.为了减少故障,降低危害,在网络结构的设计、建造及维护中提高网络可靠性、稳定性和抗毁性成了学界理论研究的一个重要的课题.网络从本质上讲就是一种抽象意义上的结构,一般用连通图来描述.通常用图的顶点表示通信站点,用边表示两个通信站之间的通信线路.显然,网络结构的抗毁性与其对应的图的连通性有十分密切的关系.一般来讲,一个图的连通性越好,它代表的网络的抗毁性就越强.而图的连通性作为反映图结构特征的基本属性,是结构图论研究的重要课题,而且图的连通性在组合优化和算法分析方面也有非常广泛的应用.早期人们利用图的连通度和边连通度来度量图的连通性.随着研究工作的不断推进,人们发现这两个参数在刻画图的连通性方面存在着明显的不足,于是学者们便对这两个参数做了一些合理扩充和自然推广.一方面,基于连通度是反映破坏图的连通性所需移除的最少节点或链路数,人们考虑增加一些其他度量指标来合理扩充连通度概念,使其既能反映破坏连通性的难度,又能反映破坏的程度.于是便相继提出了坚韧度、离散数、完整度、粘连度以及毁裂度等重要的连通性刻画参数.另一方面,基于Whitney所给的连通度的“路”定义和著名的Menger定理,Chartrand等人于1984年将图的连通度定义做了一种自然推广,引入了图的广义连通度的概念.图的完整度、离散数、粘连度、毁裂度以及广义连通度和圈重数都是反映图的连通性和结构性质的重要参数和指标.本文围绕这些参数的定值计算、极值定界和优化设计等问题展开相关研究工作.主要内容包括以下四部分.在第二章,围绕图的完整度、离散数、粘连度、毁裂度及边毁裂度等连通性参数展开相关研究.首先利用图谱理论为正则图的完整度给出一个新的界值,给出了分离图和k-叉树的完整度的定值计算公式;利用图的亏格和连通度给一般图的离散数做定界讨论,对正则图的离散数给出了一个特征值意义的上界,丰富了相关结果;讨论了分离图的离散数的计算复杂度问题,确定了k-叉树的离散数的定值计算公式;然后讨论了分离图、k-叉树以及路、圈、完全二部图的全图的粘连度计算问题和全图及正则图的粘连度定界问题,研究了粘连度意义下最大图结构的构造问题及优化设计问题;本章最后给出了图的毁裂度和边毁裂度的一些基本结果,并对这两个参数的定值、定界问题做了相关讨论,为树结构的毁裂度计算给出了的一个递归算法,并探讨了树结构毁裂度的极值问题和毁裂度意义下的最值网络结构的构造问题.在第三章,首先基于D.Bauer和R.Tindell关于图及其线图的连通度关联关系的一个结果,就图的广义k-连通度提出了类似问题并展开讨论,随后解决了k=3的情形,推广了D.Bauer和R.Tindell的结果.然后确定了一些图类,诸如树、单圈图、完全图、完全二部图的线图和全图的广义连通度和广义边连通度的定值计算公式,并对一般图的线图和全图的广义连通度的取值定界问题做了相关讨论.在第四章,围绕图中边不交圈的计数问题展开讨论,研究了一系列卡氏积图的圈重数(边不交圈的最大数目)的定值问题,在此基础上确定了一些全图的圈重数计数公式,特别是完全二部图的全图的圈重数计数公式推广了Akbar Ali等人的前期结果.在第五章,基于Hajo Broersma和Balakrishnan关于k-树和弦图的Hamilton性研究结果,从两种图结构入手展开研究,讨论了这两类图中存在连通[2,2k]-偶因子的相关条件,推广了Hajo Broersma和Balakrishnan等人相关结果.
其他文献
随着工农业生产的飞速发展,重金属污染问题日益严重,镉(Cd)因毒性高、移动性大、易进入食物链而备受关注。近些年来,欧美等国家广泛应用柳树修复土壤重金属污染,柳树还能取代煤和油作燃料,使生物质生产和植物修复相结合。本论文选用Cd为胁迫因子、苗期旱柳为研究对象,开展Cd胁迫下旱柳吸收、积累、毒害和抗性等的研究工作。结果如下:1.Cd抑制了旱柳的生长,引起ROS的积累,同时启动抗氧化酶系统保护植物免受过
学位
能源和环境问题是影响社会可持续发展的重要因素,建筑的居用环境是人们追求幸福生活的重要落脚点,根据建筑使用人的需求进行建筑节能,一方面可以满足建筑的使用功能,同时从能源需求产生的机理上挖掘节能潜力。本文以人员用能行为为核心,沿人员用能需求产生和流动的方向,将建筑用电需求分别在单人层面、单体建筑层面和多建筑耦合层面进行诠释。本文以多Agent建模为研究方法,组建了多层递阶Agent模型,获得了各层面电
学位
随着后基因组时代,蛋白质组学的相关研究已经如火如荼的展开。由于高通量实验技术的发展,科研人员已经获得了大量的蛋白质组学数据。过去的十余年内,大量的基于计算手段的研究方法已经被开发和使用。这些计算工具可以分析和研究已有蛋白质相互作用数据,为生物实验提供了可信度较高的分析预测结果,从而提高了生物科研人员的实验效率,减少了不必要的人力和财力。蛋白质是生命活动的主要载体,是功能的主要执行者。蛋白质之间的相
学位
目的·探索现场快速评估法(rapid on-side evaluation,ROSE)辅助超声引导下甲状腺细针穿刺(ultrasound-guided fine needle aspiration cytology,US-FNAC)的临床效果。方法·回顾性分析2019年1月—2022年12月于上海市浦东新区公利医院确诊的甲状腺结节患者资料(n=874)。根据细胞学检测方法分为ROSE+液基薄层细胞
期刊
安全管理是企业生产管理的重要组成部分,是企业实现高质量发展的前提和基础。本文以烟草企业为例,对企业常见的安全管理问题进行了分析,并提出了加强企业安全管理的实施路径,以供借鉴和参考。
期刊
本篇文章主要是对序列空间上加权伪移位算子,L~2(K)空间上算子加权移位以及局部紧Hausdorff空间上加权平移算子这三类算子的动力学性质进行刻画.具体分为如下几个方面:首先,我们将讨论序列空间上加权伪移位算子的动力学性质.目前,前人已经对此算子的超循环性和亚超循环性给出了完整的刻画.在第三章我们将继续前人的研究给出Banach序列空间上加权伪移位算子是圆盘超循环、余圆盘超循环、不交超循环以及不
学位
单峰型问题是近年来组合数学家研究的热点问题之一。通过对单峰型问题的解决使得离散数学和分析之间的联系更加紧密。在解决单峰型问题的时候经常使用的工具涉及到分析,代数,对称函数等。但是大部分时候证明序列单峰型的问题并没有系统的方法,而且主要靠人工计算。这很大程度限制了该问题的进一步发展和深化。本文中我们首次尝试使用符号计算的方法来解决一些具有代表性的序列的高阶对数凹凸性。符号计算是最近兴起的主要用计算机
学位
目的 探讨超声引导下甲状腺结节细针穿刺细胞学诊断准确度临床分析。方法 选取我院收治的甲状腺结节患者106例,均行超声引导下细针穿刺细胞学检查(UG-FNAC),以病理组织学结果为诊断金标准,分析UG-FNAC诊断的准确率,采用Logistic回归方程分析可能影响UG-FNAC诊断准确率相关因素。结果 术后病理组织检查显示93例为恶性结节,13例为良性结节,最终确定UG-FNAC诊断甲状腺结节的准确
期刊
本博士论文研究了二次互补问题的理论与算法。二次互补问题是一类特殊的非线性互补问题,其非线性映射是二次多项式函数映射;是连接线性互补问题和非线性互补问题的一个重要桥梁;是广义Markowitz经济组合问题等重要实际问题的重要理论基础。本博士论文将分别从三个方面来研究二次互补问题的理论与算法,对进一步研究二次互补问题甚至非线性互补问题具有基础理论作用,对于设计高效的数值算法求解广义Markowitz经
学位
目的:探讨使用25G穿刺针进行甲状腺结节细针穿刺活检能否满足细胞学检查要求,以及穿刺针型号对甲状腺结节细针穿刺活检标本满意度的影响。方法:选取2019年10月1日~10月30日福建省第二人民医院收治的10例术后病理确诊为甲状腺乳头状癌患者为研究对象。切取甲状腺标本中癌结节的最大切面,分别于新鲜切除时及脱水后测量横径和纵径,计算癌结节的皱缩率,后制成病理切片,通过数码显微镜于癌结节内随机截取图片,每
期刊