图与有向图的高阶连通性

论文摘要

随着信息网络的飞速发展,许多相关的理论问题开始引起人们的重视,其中之一是网络的可靠性,即网络在它的某些部件（节点或者连接）发生故障的条件下仍能正常工作的能力.网络拓扑结构通常被模型化为图或有向图,因此,图论中的一些经典概念,如连通度和边（弧）连通度,就被用来研究网络的可靠性.为了进一步研究相关内容,人们提出了各种各样的高阶连通性的概念,如super-κ性（super-λ性）、限制性边连通性、超限制性边连通性等.本文主要研究某些特殊图类的各种连通性问题.第一章,我们介绍了研究背景和一些基本概念,给出了有向图的线图、Cartesian积、Lexicographic积等的定义.对各类连通度问题研究的历史与现状进行了一定程度的综述.最后介绍了本文的研究内容和主要结果.第二章,我们根据图的局部边连通度定义了图的局部限制性边连通度以及图的最优局部限制性边连通性,证明了一些图类下已知图是最优限制性边连通的充分条件仍能保证图是最优局部限制性边连通的.第三章首先研究了两个无向图的Cartesian积的超限制性边连通性、两个有向图的Cartesian积的super-λ及super-κ性.其次根据全变换图的概念给出了全变换有向图的概念,研究了其中两类全变换有向图以及中间有向图的super-λ及super-κ性.本章最后一节研究了完全二部有向图的迭代线图的一些性质.第四章主要定义了有向图的双超连通性,并且刻划了一些特殊图类,比如说, Abelian Cayley有向图、有向图的线图、Cartesian积及Lexicographic积的双超连通性.

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景
• 1.2 基本概念
• 1.3 研究综述
• 1.4 本文的研究内容及主要结果
• 第二章 图的局部限制性边连通度
• 2.1 准备知识
• 2.2 任意图的局部限制性边连通度
• 2.3 给定团数的图的局部限制性边连通度
• 2.4 无三角形的图的局部限制性边连通度
• 第三章 几类变换图及有向图的高阶点、边连通性
• 3.1 图的Cartesian 积的超限制性边连通性
• 3.2 有向图的Cartesian 积的super-λ及super-κ性
• 3.3 全变换有向图 D++- 的性质
• 3.4 全有向图的super-λ及super-κ性
• 3.5 中间有向图的super-λ及super-κ性
• 3.6 完全二部有向图的线图的性质
• 第四章 有向图的双超连通性
• 4.1 准备知识
• 4.2 Abelian Cayley 有向图的双超连通性
• 4.3 有向图的线图、Cartesian 积、及Lexicographic 积的双超连通性
• 参考文献
• 博士在读期间完成论文清单
• 致谢