学位论文 > 优秀研究生学位论文题录展示

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

作　者: 熊玮
导　师: 张昭
学　校: 新疆大学
专　业: 运筹学与控制论
关键词: 点不可靠多项式 交错群图 限制性连通度
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 12次
引　用: 0次
阅　读: 论文下载
 

内容摘要


随着信息网络的飞速发展,网络的可靠性问题开始引起人们的重视,即网络在它的某些部件（节点或者连接）发生故障的条件下仍能工作的能力.网络拓扑结构通常被模型成为一个图.假定图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.

全文目录


摘要  3-4
Abstract  4-6
第一章 引言  6-8
第二章 图的点不可靠多项式的递推公式  8-12
  2.1 背景, 定义和符号  8
  2.2 点不可靠多项式的递推公式  8-9
  2.3 一些图类的点不可靠多项式  9-12
第三章 交错群图的限制性连通度  12-20
  3.1 背景和定义  12-13
  3.2 分层结构和圈结构  13-15
  3.3 κ~1(AG_n) 的确切值  15-17
  3.4 κ~2(AG_n) 的确切值  17-20
参考文献  20-22
硕士期间发表论文清单  22-23
致谢  23

相似论文

  1. 图的λ_（3，q）-连通性和传递图的局部最优性研究,O157.5
  2. 有向线图和有向笛卡尔积图的限制性连通度,O157.5
  3. 广义Kautz有向图GK（2，n）和交错群图AG_n的反馈数,O157.5
  4. 图的高阶连通性,O157.5
  5. 复杂布尔网络稳定性问题的研究,O157.5
  6. 复杂网络的建模分析及其应用,O157.5
  7. 关于特征多项式的两个参数及其应用,O157.5
  8. 工件排序问题的若干研究,O157.5
  9. 多属性无向加权图上的聚类方法研究,O157.5
  10. 复合型均衡网络的存在性及其算法研究,O157.5
  11. 随机网络模型分离,O157.5
  12. 两类图的色等价图,O157.5
  13. 图谱研究的一般方法,O157.5
  14. 基于复杂网络的供应链建模与网络效率研究,O157.5
  15. 复杂网络可靠性评价指标研究,O157.5
  16. M(?)bius cubes图的交叉数,O157.5
  17. 局部扭立方体LTQ_n容错性研究,O157.5
  18. 增广立方体AQn图的交叉数的界,O157.5
  19. 交叉立方体的容错泛圈性研究,O157.5
  20. 局部扭立方体图的交叉数研究,O157.5
  21. 遇袭有向复杂网络抗毁性修复策略研究,O157.5

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com