点不可靠多项式及交错群图的限制性连通度

论文摘要

随着信息网络的飞速发展,网络的可靠性问题开始引起人们的重视,即网络在它的某些部件（节点或者连接）发生故障的条件下仍能工作的能力.网络拓扑结构通常被模型成为一个图.假定图G的边完全可靠,而顶点都以相同的概率ρ∈（0,1）各自独立地发生故障.那么图G不再连通的概率为:其中, n为G的顶点个数, ni（G）是G的顶点数为i的顶点割的个数,κ为G的连通度.我们称UR（G）为图G的点不可靠多项式.图论中的一些经典概念,如连通度和边连通度,很早就被用来研究网络的可靠性.为了进一步研究,人们提出了各种各样的高阶连通性的概念,如super-κ性、k-限制性连通度等.点集F是连通图G的k-限制性点割,如果G - F不连通并且G - F的每个点在G - F中至少有k个好邻点.图G的基数最小的k-限制性点割为G的k-限制性连通度,记作κ<sup>k（G）.这个系数衡量了网络的一种条件性容错度.交错群图被证明了有许多很好的性质,比如说具有强分层性,较高的连通性,较小的直径和较小的平均距离等.这些优点使得它成为一个较受欢迎的网络拓扑结构.本文共分三章.第一章,我们介绍了研究背景以及本文的主要结果.第二章,我们给出了图的点不可靠度多项式的递推公式.利用这个公式,我们确定了一些特殊图类的不可靠度多项式,包括完全图、星、完全图和空图的联图、完全二部图、路、及圈.第三章,我们证明了对n-阶交错群图AGn,κ1（AG4） =κ2（AG4） = 4且当n≥5时κ1（AGn） = 4n - 11,κ2（AGn） = 6n - 18.

论文目录

• 摘要
• Abstract
• 第一章 引言
• 第二章 图的点不可靠多项式的递推公式
• 2.1 背景, 定义和符号
• 2.2 点不可靠多项式的递推公式
• 2.3 一些图类的点不可靠多项式
• 第三章 交错群图的限制性连通度
• 3.1 背景和定义
• 3.2 分层结构和圈结构
• 1（AG_n） 的确切值'>3.3 κ¹（AG_n） 的确切值
• 2（AG_n） 的确切值'>3.4 κ²（AG_n） 的确切值
• 参考文献
• 硕士期间发表论文清单
• 致谢