有向图和定向图的边连通性和点连通性研究

摘要

近年来，随着大规模集合电路，微电子技术，大规模互联网络的飞速发展，人们对网络的拓扑结构要求越来越高.图的理论及其在各个领域的广泛应用越来越受到数学界和其他科学界的重视.网络的可靠性和容错性受到人们的普遍关注.图论中图的连通性分析为此类问题的研究提供了重要的理论依据.
　　设计和分析多处理机互联网络时，通常会涉及某些类型的网络模型，利用图的点和边来代替网络的节点和连线，以此构成相互连通的网络的拓扑结构.通常将网络的拓扑结构抽象成图或有向图（此处公式省略）.这时D的顶点代表处理机，连接顶点的边表示一对处理机之间的直接通信联系(有向边则表示只能进行单向联系).在研究这种模型时，经常假设其节点不会失效，但每条边相互独立地以相等的概率pG(0,1)失效.用m表示D的边数，A(D)表示D的边连通度，Q(D)表示D的边数为i的边割数目，则D连通的概率为：（此处公式省略）要准确的计算出D的可靠度，需要计算出每个系数.但是，Provan和Ball在1983年指出计算出所有这些系数是困难的.对此作了进一步阐述.
　　但是，在精确刻画图或有向图的连通性方面，边连通度或点连通度存在一些不足：首先，边连通度或点连通度相同的图或有向图的可靠性可能有所不同.其次，不能区分删掉A-割或k-割后的图或有向图的不同类型，即未考虑网络的破坏程度.第三，默认图或有向图的任何子集中所有元素可能潜在地同时失效.为克服以上缺陷，自1983年Harary提出了条件边连通度的概念，为该领域的研究开辟了新的道路.经过二十多年的发展，边连通性所涉及的内容日益丰富和具体，包括超级边连通性、极大局部边连通性和超级局部边连通性等.类似的，在图的点连通性方面，也出现了极大连通性、极大局部连通性等概念.这些参数都能更深刻地刻画图或有向图的边、点连通性质.本人在前人工作的基础上，继续研究图或有向图的超级边连通性以及图的的超级局部连通性等相关性质.
　　在第一章中，主要介绍本文的研究背景和一些已有的结果，以及文章中涉及的一些基本概念、术语符号.
　　在第二章中，主要研究定向图极大与超级局部边连通的充分条件，首先，给出了利用度序列的低度端保证定向图是极大和超级局部边连通的充分条件.
　　定理2.1.3设D为n阶定向图，度序列（此处公式省略）.
　　(1)若（此处公式省略）则D是极大局部边连通的.
　　(2)若（此处公式省略）则D是超级局部边连通的.
　　其次，给出了二部定向图极大局部边连通的度和条件.
　　定理2.2.4设D为n阶二部定向图，最小度5>2.若对任意同部顶点u,v,有（此处公式省略）,则D是极大局部边连通的.
　　在第三章，主要研究有向图与定向图的依赖团数的局部边连通性.首先给出有向图依赖团数的极大局部边连通的充分条件.
　　定理3.1.3设D为n阶有向图，团数w(D)< p,度序列为（此处公式省略）.若（此处公式省略）或（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是极大局部边连通的.
　　定理3.1.4设D为n阶有向图，团数w(D)< p,度序列为（此处公式省略）,（此处公式省略）（此处公式省略）.若（此处公式省略）,或n>2L吳」且对某整数k,（此处公式省略）,有（此处公式省略）则D是极大局部边连通的.
　　然后，又给出了依赖团数的超级局部边连通的充分条件，即有如下结果：
　　定理3.2.4设D为n阶有向图，团数（此处公式省略）,最小度6>3,度序列为（此处公式省略）.右（此处公式省略），或（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是超级局部边连通的.
　　定理3.2.5设D为n阶定向图，团数（此处公式省略）,最小度为5>2，度序列为（此处公式省略）,（此处公式省略）.若（此处公式省略），或（此处公式省略）且对某整数（此处公式省略）,有（此处公式省略）则D是超级局部边连通的.
　　在第四章中，主要研究有向图极大边连通的倒数度条件.得到如下结果：
　　定理4.1.2设D是n>2阶强连通有向图，最小度（此处公式省略）若（此处公式省略），或（此处公式省略）且（此处公式省略）则D是极大边连通的.
　　定理4.2.2设D是n阶强连通无三角形有向图，最小度（此处公式省略）若（此处公式省略），或（此处公式省略）且满足（此处公式省略）则D是极大边连通的.
　　在第五章中，得到保证无p-钻图与不含K2,3图局部连通性的充分条件.
　　定理5.2设p>2为整数，G是n阶连通无p-钻图，（此处公式省略）,贝忆是超级局部连通的，若（此处公式省略）其中（此处公式省略）.
　　定理5.5不含化3，最小度6>2的n阶连通图G为极大局部连通的，若阶数n35-3.

目录

封面

声明

目录

中文摘要

英文摘要

第 一 章 引 言

第 二 章 定 向 图 的 局 部 边 连 通 性

§ 2 .1 定 向 图 极 大 与 超 级 局 部 边 连 通 性 的 度 序 列 条 件

§ 2.2 二 部 定 向 图 极 大 局 部 边 连 通 性 的 度 和 条 件

第 三 章 依 赖 团 数 的 局 部 边 连 通 性

§ 3 .1 有 向 图 极 大 局 部 边 连 通 性 依 赖 团 数 的 度 序 列 条 件

§ 3 .2 超级局 部边连通性依赖团数的度序列条件

第 四 章 有 向 图 极 大 边 连 通 性 的 倒 数 度 条 件

§ 4.1 一 般 有 向 图 极 大 边 连 通 性 的 倒 数 度 条 件

§ 4 .2 无 三 角 有 向 图 极 大 边 连 通 性 的 倒 数 度 条 件

第 五 章 图 的 局 部 点 连 通 性

参考文献

致谢