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

图的宽直径与相关参数的关系

作　者: 江小平
导　师: 张先迪
学　校: 电子科技大学
专　业: 应用数学
关键词: 连通度直径宽直径 Rabin 数
分类号: O157.5
类　型: 硕士论文
年　份: 2005年
下　载: 47次
引　用: 0次
阅　读: 论文下载

内容摘要

图的某些参数,如连通度和直径,不仅在图论和组合数学本身十分重要,而且因他们与通信网络的容错性和传输延迟密切相关而在其它领域被广泛研究. 随着超大规模集成电路技术和光纤材料科学的发展,使我们有能力设计大型并行处理计算机系统和快速,复杂的通信网络. 这些系统不仅要求我们研究涉及图的连通度和直径的网络中两个节点间的单条路径,而且要研究两个节点或两个节点集间的内部点不交的多条路径. 这自然引导人们把图的直径推广,而宽直径,容错直径和Rabin 数等概念都是直径的推广.本文主要研究网络图特别是环网络的宽直径及其相关参数之间的关系. 其主要工作包括以下几个方面.1. 得到了双环网G（n;1,s）的2-宽直径和Rabin 数. d₂ （G（n;1, s）） ≤d_L +1, r₂（G（n;1,s）） ≤d_L +12. 得到了无向双环网C（n;a,b）（其中a,b 是n 因子且互素）的不同构的图的个数和4-宽直径3. 根据双环网的对称性和传递性得到了另一类循环网C（n;1,a）的4-直径的上下限,同时通过计算特殊点间（0 到1,2,a）的宽距离的运算得到当给定步长时C（n;1,a）的4-宽直径的准确值.4. 得到了循环网C（2n;1,n）的容错直径. 5. 讨论了函数h（n,k,d）

全文目录

中文摘要  4-5
英文摘要  5-6
目录  6-7
常用符号表  7-8
第一章绪论  8-19
  1.1 背景介绍  8-10
  1.2 几类常用网络的宽直径  10-18
  1.3 内容简介  18-19
第二章环网络  19-39
  2.1 定义及基本定理  19-20
  2.2 双环网G(N;51, s 2 )  20-24
  2.3 无向双环网C(N;51, s 2 )  24-33
  2.4 环网C(211;1,n)  33-35
  2.5 多环网  35-39
第三章宽直径及相关参数的关系  39-46
  3.1 宽直径及相关参数的关系  39-43
  3.2 优化问题  43-46
第四章结论  46-47
参考文献  47-51
论文创新点摘要  51-52
致谢  52-53
个人简介  53
硕士期间发表论文情况  53

图的宽直径与相关参数的关系

内容摘要

全文目录

相似论文