LHL-立方体互连网络及其性质的研究

发布时间：2020-10-29 21:34

　　 并行计算系统是计算机科学中的重要研究领域,作为并行计算系统中的重要组成部分,互连网络的性质对整个系统的性能在很大程度上起着决定性的作用。迄今已经有多种互连网络被提出,其中超立方体具有对数级的直径、高连通度和对称性等很好的性质,故被用作多种并行机的处理器连接的拓扑结构。然而超立方体并非所有性质都是最优的,超立方体的很多变型具有许多比超立方体更好的性质,其中局部扭立方体已经被证明了在直径、哈密尔顿连通性等方面都优于超立方体。本文给出在超立方体与局部扭立方体的顶点间的一种连接——超连接,从而得到一种称为LHL-立方体的新型网络,并对这种网络的以下性质进行了研究:顶点连通度、边连通度、哈密尔顿连通性、直径、可嵌入性以及容错性,从而证明了LHL-立方体兼有超立方体和局部扭立方体的若干优点。具体研究结果如下: (1)一个n维LHL-立方体是一个具有2n个顶点和n×2~(n-1)条边的n -正则图,其顶点连通度和边连通度都为n;当n≥4时,它是哈密尔顿连通的;它的直径的上界为[n/2] +3。 (2)当n≥4时,n维LHL-立方体能以扩张1嵌入任意长度为l (4≤l≤2 n)的圈;当n≥1和n≥2时,n维LHL-立方体能以扩张1和膨胀1分别嵌入2×2~(n-1)和4×2~(n-2)网格;当n≥6时,n维LHL-立方体不能以扩张1和膨胀1嵌入8×2~(n-3)网格。 (3)在n维LHL-立方体中,当n≥3且故障边的条数小于或等于n-2时,n维LHL-立方体中存在一条哈密尔顿路径;当n≥4且故障边的条数小于或等于n-3时,n维LHL-立方体中存在一条哈密尔顿圈。
【学位单位】：苏州大学
【学位级别】：硕士
【学位年份】：2011
【中图分类】：O157.5;TP338.6
【部分图文】：

局部扭立方体3LTQ和4LTQ

图 3.1 四维 LHL-立方体4LHL体的顶点度数、顶点连通度和边连通度，最小顶点度数即为顶点的度数。根据 Menger 定理通度)为n，当且仅当该图的任意两个顶点之间存在至设一个图的连通度为n，则在该互连网络中只要故障该互连网络中任意两个无故障处理器间必定存在至局部扭立方体都是正则图，每个顶点的度数都相等，高连通(容错)度。一个n维 LHL-立方体是一个具有n2 个顶点和12nn × 条义 2.2.1、2.3.1 和 3.1.1，容易证明一个n维 LHL-立方

由定义 3.1.1 知，3 维 LHL-立方体即是 3 维是哈密尔顿连通的。n维 LHL-立方体中任意两个不同的顶点 u, v，( )0 1nQ，( )1 1∈nv VLTQ。 知，在0n 1Q 中必然存在一个哈密尔顿圈 C ，且在分别记为x和'x 。所以我们总可以从顶点 x 和x在1n 1LTQ 中存在顶点 y ，满足11( )ny V LTQ ∈ ，.1 知，当 n ≥3时，nLTQ 是哈密尔顿连通，故LT条哈密尔顿路径。从而，在1n 1LTQ 中顶点 v 和 y可以得到顶点u 和v之间的哈密尔顿路径为：u ，所示：
【相似文献】

相关期刊论文 前10条

1 王明芝;;例谈正方体数学思想之美[J];西藏科技;2010年10期

2 唐丹妮;;魔方:这就是一个迷[J];学习博览;2011年05期

3 ;巧算电阻值[J];科学大众(中学版);2001年07期

4 周海松;张健;吴志坚;胡雪娇;;联机分析处理在太湖流域水文遥测系统中的应用[J];水电自动化与大坝监测;2009年01期

5 ;娱乐之页[J];科技导报;2009年05期

6 程敏;;基于八叉树的三维形体表示的探讨[J];科技风;2010年10期

7 ;动脑筋[J];科学大众(中学版);1999年08期

8 ;IQ冲浪[J];少年科学;2006年06期

9 ;机智豆冲浪10[J];少年科学;2002年11期

10 唐丹妮;;魔方:这就是一个谜[J];看历史;2010年12期

相关博士学位论文 前10条

1 宁万涛;图中的度、边和圈[D];兰州大学;2011年

2 董强;几类规则互连网络的嵌入与容错嵌入研究[D];重庆大学;2010年

3 李晶;k-元n-立方体的路和圈[D];山西大学;2011年

4 李泽海;数据仓库中多维数据处理与查询相关技术的研究[D];吉林大学;2005年

5 余亮;等球Packing问题的启发式研究[D];华中科技大学;2012年

6 钱立武;稀土化合物纳米材料的液相控制合成、形成机理及性能研究[D];上海交通大学;2009年

7 万卫兵;快速成型在组织工程骨骼修复的应用研究[D];上海交通大学;2007年

8 曹红亮;金属硫族半导体纳米材料的液相控制合成及机理研究[D];上海交通大学;2007年

9 许艳艳;铜基纳米材料的控制合成与性质研究[D];山东大学;2008年

10 熊鹰;磁性纳米材料的合成及磁场诱导组装[D];中国科学技术大学;2007年

相关硕士学位论文 前10条

1 李勇;LHL-立方体互连网络及其性质的研究[D];苏州大学;2011年

2 刘保冬;交换立方体网络的相关性质研究[D];浙江师范大学;2011年

3 胡小兰;焦薄饼图的条件容错性分析[D];湖北大学;2012年

4 庞冬梅;基于Flex的知识立方体可视化设计与实现[D];华南理工大学;2012年

5 叶彩月;局部纽立方体网络的相关性质研究[D];浙江师范大学;2010年

6 王曙毅;具有全互联立方体拓扑结构的移动自组织网络的自适应路由算法研究[D];浙江大学;2005年

7 张震亚;具有全互连立方体结构的移动自组织网络拓扑管理研究[D];浙江大学;2005年

8 张维维;Cu_2O纳米立方体和硅一银核壳结构的合成[D];吉林大学;2006年

9 张馨元;k元n立方体和增广k元n立方体的匹配排除[D];湖北大学;2012年

10 翟文华;局部扭立方体LTQ_n容错性研究[D];大连理工大学;2011年

本文编号：2861485