有向图和图的边连通性与点连通性

摘要

随着社会的不断进步,人们的生活、工作和学习与多处理机互联网络的联系越来越紧密.自然,网络的可靠性与容错性倍受关注,进而网络的可靠性与容错性分析就成为近年来国内外研究的热点之一.图论中图的连通性分析为此问题的研究提供了重要的理论支撑.
　　在设计、分析大规模互联网络的可靠性和容错性时,通常将网络的拓扑结构抽象成图或有向图D=(V,E).这里D的顶点代表处理机,连接顶点的边表示一对处理机之间的直接通信联系f有向边则表示只能进行单向联系).在研究这种模型时,经常假设其节点不会失效,但每条边相互独立地以相等的概率p∈(0,1)失效.用m表示D的边数,λ(D)表示D的边连通度,Ci(D)表示D的边数为i的边割数目,则D不连通的概率P(D,p)为（公式略）.
　　从而可用D连通的概率R(D,p)=1-P(D,p)来衡量网络的可靠性.显然P(D,p)越小,网络的可靠性越好.但是对于一般图,确定所有的系数Ci是一个NP-困难问题.对此,colbour做了进一步的阐述.当假设D的边不会失效,但其节点相互独立地以相等的概率p∈(0,1)失效时也有类似的讨论.
　　图或有向图的边连通度与点连通度是反映其连通性质的两个重要参数.但是,在精确刻画图或有向图的连通性方面,边连通度或点连通度存在一些不足:首先,边连通度或点连通度相同的图或有向图的可靠性可能有所不同.其次,不能区分删掉λ-割或K-割后的图或有向图的不同类型,即未考虑网络的破坏程度.第三,默认图或有向图的任何子集中所有元素可能潜在地同时失效.为克服以上缺陷,自1983年Harary提出了条件边连通度的概念,经过三十年的发展,边连通性所涉及的内容日益丰富和具体,包括超级边连通性、极大局部边连通性和超级局部边连通性等.类似的,在图的点连通性方面,也出现了极大连通性、极大局部连通性等概念.这些参数都能更深刻地刻画图或有向图的边、点连通性质.本人在前人工作的基础上,继续研究图或有向图的超级边连通性以及图的超级局部连通性等相关性质.
　　在第一章中,主要介绍本文的研究背景和一些已有的结果,以及文章中涉及的一些基本概念、术语符号.记有限简单图或有向图D=(y(D),E(D)),其中V(D)表示D的顶点集,E(D)表示D的边集,称D的阶数为n=|V(D)|.不含来回边的有向图称为定向图.
　　在第二章中，本文给出了二部定向图极大与超级局部边连通的邻域条件（公式略），然后又讨论了二部定向图超级局部边连通的度序列条件，得到了以下结果（公式略）.
　　在第三章，首先给出了二部定向图超级边连通的度序列条件（公式略）；然后，又讨论了有向图超级边连通的边邻域条件，得到以下结果（公式略）；最后，给出利用度序列的低度端保证图的超级边连通性的依赖团数的度序列条件，并举例说明了最好可能性.
　　笛卡尔乘积是构造大规模网络的常用方法,它可以保持小规模网格的许多性质.在第四章中,我们主要讨论了正则图笛卡尔乘积的超级局部连通性,得到了以下主要结果（公式略）.

目录

封面

声明

目录

中文摘要

英文摘要

第一章 引言

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

第三章 有向图和图的超级边连通性

第四章 正则图笛卡尔乘积的超级局部连通性

参考文献

致谢