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

乘积图的连通度和容错直径的研究

作　者: 杨超
导　师: 徐俊明
学　校: 中国科学技术大学
专　业: 应用数学
关键词: 乘积图中国科学技术大学点连通度边连通度博士学位论文容错直径连通分支超连通最小度完全图
分类号: O157.5
类　型: 博士论文
年　份: 2007年
下　载: 146次
引　用: 2次
阅　读: 论文下载

内容摘要

近年来，关于乘积图的研究相当活跃，其中四种常见乘积图的结构刻画与识别算法已经建立了优雅而比较完备的理论。另外关于乘积图的各种图论变量的研究也始终是一个充满具有挑战性问题的领域。2000年，Imrich和Klavzar的专著《Product Graphs》对这些内容都作了详尽的综述。连通度是图论的最基本的参数之一。在互连网络中，连通度以及和连通度相关的各种概念，比如说极大连通和超连通，是衡量互连网络的可靠性和容错性能的重要参数。而且实际中使用的互连网络，大多具有乘积图的结构。研究乘积图的连通度，在乘积图理论里面是一个基本的内容，而且在互连网络中有一定的应用价值。直到2003年，关于各类乘积图的连通度的研究结果不多，文献中可以看到的只有关于笛卡儿乘积图的比较粗糙的界。本文的主要研究了四种常见乘积图（笛卡儿乘积，强乘积，字典乘积图，直接乘积）和一种广义乘积图的连通度和边连通度。对笛卡儿乘积图，我们证明了，λ（G₁□G₂）=min{n₁λ₁，n₂λ₁，δ₁^-+δ₂^-，δ₁⁺+δ₂⁺}，κ（G₁□G₂）=min{n₁κ₁，n₂κ₁，δ₁^-+δ₂^-，δ₁⁺+δ₂⁺}，其中G₁和G₂同时为有限图或同时为无限图。这与之前对笛卡儿乘积图的连通度只有界的估计相比，是一个较大的突破。对另外三种乘积图，我们亦得到一些关于连通度的确切的公式：λ（G₁（?）G₂）=min{λ₁（n₂+2m₂），λ₂（n₁+2m₁），δ₁+δ₂+δ₁δ₂}，κ（G₁（?）G₂）=κ₁v₂，（G₁≠K_n），κ（K_n（?）G₂）=（n-1）v₂+κ₂，λ（G₂（?）G₂）=min{λ₁v₂²，δ₂+δ₁v₂}，λ（K₂×H）=min{2λ，2β，（?）{j+2β_j}}，对于广义乘积图，我们得到紧的（下）界，mim{κ_mv_p，κ_pv_m，δ_m+δ_p)≤κ（G_m*G_p）≤δ_m+δ_p；min{λ_mv_p，λ_pv_m，δ_m+δ_p}≤λ（G_m*G_p）≤δ_m+δ_p对某些乘积图，本文还给出了极大连通或是超连通的充分必要条件（或充分条件）。容错直径办是衡量互连网络可靠性的另一个重要参数。本文最后，还给出了广义乘积图容错直径的一个上界，D_k₁+k₂（G₁*G₂）≤D_k₁（G₁）+D_k₂（G₂）+1；

全文目录

中文摘要  7-9
英文摘要  9-11
记号索引  11-12
第一章图与乘积图  12-22
  §1.1 图和连通度  12-16
  §1.2 四种常见的乘积图  16-22
    §1.2.1 基本概念与性质  16-19
    §1.2.2 研究历史  19-22
第二章笛卡儿乘积图的连通度  22-48
  §2.1 边连通度  22-30
  §2.2 点连通度  30-44
  §2.3 无限图的情形  44-48
第三章强乘积图的连通度  48-60
  §3.1 边连通度  48-57
  §3.2 K_2⊙H的边连通度  57-58
  §3.3 点连通度  58-60
第四章其它类型乘积图的连通度  60-68
  §4.1 字典乘积图的连通度  60-62
  §4.2 直接乘积图的连通度  62-68
第五章广义乘积图的连通度  68-80
  §5.1 引言  68-69
  §5.2 连通度  69-76
  §5.3 边连通度  76-80
第六章乘积图的容错直径  80-84
  §6.1 引言  80-81
  §6.2 主要结果  81-84
第七章结束语  84-87
参考文献  87-90
作者攻读博士学位期间完成论文目录  90-92
致谢  92

乘积图的连通度和容错直径的研究

内容摘要

全文目录

相似论文