几类图的连通性和控制集

论文摘要

最近三十年里随着计算机科学、大规模网络技术、电子和计算机工程的飞速发展,许多相关理论问题,如网络的可靠性和可控性开始引起人们的重视.网络的可靠性即网络在它的某些部件（结点或连接）发生故障的条件下仍能正常工作的能力.网络拓扑结构通常被模型化为图或有向图.因此,图论中的一些经典概念,如连通度和边（弧）连通度,就常被用来研究网络的可靠性.图的控制理论就可以用来研究网络的可控性.为了进一步研究相关问题,人们提出了各种高阶连通度和条件性控制集的概念.如超点连通性（超边连通性）、限制性边连通性（限制性弧连通性）、全控制集、限制性控制集和全限制性控制集等.在大规模网络的设计中往往采用有规律的递归方法来构造其拓扑结构.并因此产生了很多基于Cartesian积图、Hierarchical积图、线图、跳图等有递归结构的图.本文主要研究了几类图及有向图的连通性问题和一些特殊Cartesian积图的限制性控制数和全控制数.第一章,我们介绍了图的连通性和控制集的研究背景和一些基本概念,给出了线图、跳图、Cartesian积图、Hierarchical积图、控制集、全控制集及限制性控制集等的定义.并且对各类连通性问题和控制理论研究的历史与现状进行了综述.第二章,研究了跳图的连通性、边连通性和超边连通性.确定了推广的Hierarchical积图的连通度,并且给出了判断二部图是最优限制性边连通的充分条件.第三章,研究了有向Cartesian积图的一种限制性弧连通度,二部有向图的λ′-最优性并且刻画了满足λ（D）<3的3-正则双轨道强连通有向图D的弧原子,得到3-正则双轨道强连通有向图的弧连通度.第四章主要研究了关于控制集的问题.我们刻画了全限制控制数为n或n-2的图并且确定了一些特殊Cartesian积图的限制性控制数和全控制数.

论文目录

• 中文摘要
• Abstract
• 第一章 引言
• 一.研究背景
• 二.基本概念
• 三.研究综述
• 四.本文的研究内容及主要结果
• 第二章 几类图的条件连通性
• 一、研究现状及预备知识
• 二、跳图的边连通度和超边连通性
• 三、推广的Hierarchical积图的连通度
• 四、二部图的λ′-最优性
• 第三章 几类有向图的条件连通性
• 一、有向图的Cartesian积的限制性弧连通度
• 二、二部有向图的λ′-最优性
• 三、3-正则双轨道强连通有向图的弧连通度
• 第四章 图的控制集
• 一、图的全限制性控制数
• m□P_n的限制性控制数'>二、P_m□P_n的限制性控制数
• k□P_n的全控制数'>三、C_k□P_n的全控制数
• 参考文献
• 攻读博士学位期间的主要研究成果
• 致谢