图的λ3，q-连通性和传递图的局部最优性研究

论文摘要

随着信息网络的飞速发展,很多相关的理论问题逐渐地被人们重视起来,其中之一就是网络可靠性,即网络在其某些部件损坏或故障的情况下,网络本身仍能正常工作的能力.利用图来研究互联网络的拓扑结构已经被很多计算机工作者接受并使用,图论中经典的（边）连通度是刻画互联网络可靠性的一个重要参数.但经典的（边）连通度有一个很大的局限性,容易低估大规模网络的可靠性.随着大规模网络的不断发展,我们有必要对经典的（边）连通度进行改进.基于上述理由, Harary在文献中给出了条件连通度的概念.一个更有效的被称为限制性边连通度的概念在1988年由Esfahanian和Hakimi提出,此概念又由F′abrega和Fiol推广为k-限制性边连通度.此后Hellwig等人进一步将它推广为（p,q）-限制性边连通度: G的一个边子集S称为（p,q）-限制性边割,如果G ? S有两个连通分支分别至少含有p和q个顶点.最小（p,q）-限制性边割所含顶点数称为G的（p,q）-限制性边连通度,记为λp,q（G）.此外,图的局部点（边）连通度也是刻画网络可靠性的一个重要参数.图的两个顶点u和v的局部点连通度κ（u,v）等于G中点-不交的u-v路的最大条数.这样,点连通度可以定义为κ（G） = min{κ（u,v） | u,v∈V （G）,u = v}.显然,对于G的任意一对顶点u和v,我们有κ（u,v）≤min{d（u）,d（v）}.我们称图G是局部最优点连通的,如果对于G的任意一对顶点u和v,都有κ（u,v） = min{d（u）,d（v）}.类似地可以给出局部边连通度λ（u,v）以及局部最优边连通的定义.本文主要研究两方面内容:第一,从生成树的角度给出图是λ3,q-连通的一些充分条件及必要条件。第二,证明了边传递图的局部边最优性.

论文目录

• 中文摘要
• Abstract
• 第一章 序言: 研究背景
• 3,q-连通图'>第二章 λ_3,q-连通图
• 2.1 相关概念
• 2.2 相关结果综述
• 2.3 本文主要结果
• 第三章 传递图的局部最优性
• 3.1 相关概念
• 3.2 相关结果综述
• 3.3 本文主要结果
• 参考文献
• 硕士在读期间完成论文清单
• 致谢