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

完全二部图和Harary图的λ_k最优性

作　者: 马增盛
导　师: 张昭
学　校: 新疆大学
专　业: 运筹学与控制论
关键词: 限制性边割 完全二部图 Harary图
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 14次
引　用: 0次
阅　读: 论文下载
 

内容摘要


随着信息网络的飞速发展,许多与之相关的理论性问题越来越引起人们的重视,其中之一就是网络稳定性.一个网络的稳定性是在已知某些网络节点损坏的情况下衡量该网络是否能够正常工作的能力.这是网络设计和构造的基本思想之一.一个网络可以模型为一个图,网络的稳定性可以由该图的各种连通性指标来衡量.在本文中我们研究了其中一个参数,就是限制性边连通度.一个连通图G = (V,E)的一个边子集S叫做一个k限制性边割,如果G ? S是不连通的,并且G ? S的每一个分支至少含有k个点.一个图的k限制性边连通度,记为λ_k(G),就是最小的k限制性边割所含边的数目.从这个参数的最近一些研究结果来看,λ_k越大,网络就越稳定.定义ξ_k(G) = min{ω(S) : ,|S| = k且G[S]连通},这里ω(S) = |[S,V (G)\S]|是一端点在S中,另一端点在V (G)\S中边的数目.在大多数情况下,ξ_k(G)是以λ_k(G)为上界的.因此在这种意义下一个图G称做λ_k最优的,如果λ_k(G) =ξ_k(G).问题的关键是对于一般的k,一定存在λ_k最优图吗?如果是,那么问题就是找到一些λ_k最优图使得它们可以作为比较好的网络拓扑结构.这个问题可以通过研究完全二部图得到肯定的回答.而且,我们发现Harary图的第一类和第二类也是λ_k最优的.事实上,λ_k的具体数值可以精确的计算出.论文组织结构如下.在1.1节,我们主要介绍稳定性参数的一些背景和一些基本概念. 1.2节介绍本文所做的主要结果.第2章证明我们的主要结果.完全二部图,第一类Harary图(我们所熟悉的圈的幂图),第二类Harary图的λ_k最优性分别在2.1, 2.2, 2.3节中证明.本文证明过程中所用到的主要方法是数学归纳法.

全文目录


中文摘要  2-3
英文摘要  3-5
第1章 引言  5-7
  1.1 网络稳定性参数最优化的介绍和研究现状  5-6
  1.2 本文主要工作  6-7
第2章 完全二部图和Harary图的λ_k最优性  7-16
  2.1 完全二部图的λ_k最优性  7-8
  2.2 圈的幂图的λ_k最优性  8-9
  2.3 第二类Harary图的λ_k最优性  9-16
参考文献  16-18
攻读硕士学位期间的研究成果  18-19
致谢  19-20

相似论文

  1. 图的偶匹配可扩性的若干结论,O157.5
  2. 局部2-弧传递的完全二部图,O157.5
  3. k-正则双轨道图的条件连通度,O157.5
  4. 一些图的断裂度和孤立断裂度,O157.5
  5. 完全二部图K_（n，n）的循环圈分解及边—平衡指数集,O157.5
  6. 关于k阶限制边连通度若干问题的研究,O157.5
  7. 图的泛宽度染色和（p，1）—全标号,O157.5
  8. 几类Seidel整谱图,O157.5
  9. 图的高阶连通性,O157.5
  10. 图的3-限制性边连通度和3-限制性连通度,O157.5
  11. 二部图的列表着色问题,O157.5
  12. 图的k次方图的宽直径,O157.5
  13. 一些八边图的填充与覆盖,O157
  14. 图的四阶限制边连通度的研究,O157.5
  15. 关于图的交叉数问题研究,O157.5
  16. 完全二部图的单色树划分和单色树覆盖,O157.5
  17. 图的交叉数问题研究,TP391.72
  18. 复杂布尔网络稳定性问题的研究,O157.5
  19. 复杂网络的建模分析及其应用,O157.5
  20. 关于特征多项式的两个参数及其应用,O157.5
  21. 工件排序问题的若干研究,O157.5

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