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

超立方体和蜂窝矩形环托中的圈和路嵌入

作　者: 姚晓盼
导　师: 陈协彬
学　校: 漳州师范学院
专　业: 基础数学
关键词: 超立方体蜂窝矩形环托圈嵌入哈密尔顿圈哈密尔顿可迹性容错互连网络
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 21次
引　用: 0次
阅　读: 论文下载

内容摘要

图的嵌入问题是衡量一个互连网络的中心问题之一,它的重要性在于我们可以将关于客图的已有算法应用到主图中.环和线性阵列由于通信成本低廉,因而是并行处理和分布计算中的两个基本网络结构.一个网络若含有哈密尔顿圈或哈密尔顿路,就能够有效模拟许多为环和线性阵列设计的算法,因此有效的圈或路嵌入是设计网络拓扑结构的基本要求.大型系统在使用过程中它的某些连线或结点难免发生故障,因此在并行计算中,一个互连网络的容错能力是一个关键性的因素.研究存在故障的系统具有重要的实际意义.超立方体和蜂窝矩形环托是两种常见的互联网络拓扑结构.n维超立方体(记为Q_n)是含有2~n个顶点的n正则二部图,蜂窝矩形环托(honeycomb rectangulartorus,记为HReT(m,n))是由环托(torus,一种网络拓扑结构,即两个圈的笛卡尔乘积)适当删除一些边后得到的3正则图.它们都具有许多优良的拓扑性质,已被应用于并行处理和分布计算系统中.本文研究了以下两个问题:(1)在有故障边的超立方体中通过给定线性森林(即每个分支是路的子图)的无故障圈的嵌入问题;(2)在有故障边的蜂窝矩形环托HReT(m,n)中的无故障哈密尔顿圈嵌入和蜂窝矩形环托HReT(m,n)中哈密尔顿可迹性(Hamiltonian-laceability)问题,并得到了以下结果:1、在超立方体中通过给定3条边的圈嵌入;2、在有故障边的超立方体中通过给定线性森林的无故障圈嵌入;3、在有故障边的蜂窝矩形环托HReT(m,n)中的无故障哈密尔顿圈嵌入;4、蜂窝矩形环托HReT(m,n)的强哈密尔顿可迹性.

全文目录

中文摘要  6-7
英文摘要  7-9
第1章引言  9-15
  1.1 图和互连网络  9
  1.2 图的嵌入  9-10
  1.3 容错性  10
  1.4 其它相关概念  10-11
  1.5 超立方体  11-12
  1.6 蜂窝矩形环托  12-14
  1.7 本文的主要工作  14-15
第2章若干引理  15-19
第3章在超立方体中的圈嵌入  19-29
  3.1 在超立方体中通过给定3条边的圈嵌入  19-22
  3.2 在有故障边的超立方体中通过给定边集的的无故障圈嵌入  22-29
第4章在蜂窝矩形环托中的哈密尔顿圈和哈密尔顿路嵌入  29-37
参考文献  37-41
致谢  41-42
攻读硕士学位期间完成的学术论文  42

超立方体和蜂窝矩形环托中的圈和路嵌入

内容摘要

全文目录

相似论文