星连通圈网络和三角塔网络的若干性质研究

发布时间：2017-08-22 01:03

  本文关键词：星连通圈网络和三角塔网络的若干性质研究

  更多相关文章： 互连网络 星连通圈网络 三角塔网络 图的嵌入 直径 Hamilton圈 条件连通度

【摘要】：互连网络是超级计算机的重要组成部分.在设计和选择一个互连网络的拓扑结构时,Hamilton性和可靠性是评估网络性能的重要指标,而条件连通度和限制连通度为衡量网络的可靠性提供了度量参数.本文讨论了星连通圈网络和三角塔网络拓扑结构中的几个问题,主要结果如下：1.星连通圈网络的主要结论：2010年,师海忠提出了一个猜想：星连通圈网络n-SCC(n≥4)可分解为边不交的一个Hamilton圈和一个完美对集的并.在本文中证明当n=4时是成立的,另外得到如下结果：(1)星连通圈网络中存在3·2l(3≤l≤nl/2)圈,且当n=4时,4-SCC是Hamilton图,当n=5时,发现5-SCC中存在18-400的偶圈.(2)完全二叉树可以嵌入到星连通圈网络,且该嵌入的膨胀数为1,同时给出了完全二叉树嵌入星连通圈网络的构造算法.(3]通过分析和研究,我们得到了星连通圈网络n-SCC的条件连通度和简单的限制连通度如下：当n=3时,κ1(3-SCC)=2,当n=4时,κ1(4-SCC)=3,当n5时,κ1(n-SCC)=4而当n4时,κ2(n-SCC)=n-1.并且星连通圈网络的1-条件连通度与2-限制连通度是相等的.2.三角塔网络的主要结果：(1)分析了一种新的互连网络-三角塔网络.当n4时,它是极大连通的,紧的超连通的,即三角塔网络的连通度κ(TTn)=2n-3星网络是三角塔网络的子网络,说明Sn能以膨胀数1嵌入TTn.(2)给出了三角塔网络的直径和平均距离分别是「3(n-1)-1/2」和n+2/n-1-2Hn/n(n-1)-Hn. (3)提出了关于三角塔网络Hamilton性的一簇猜想：当n3时,三角塔网络TTn可以分解成k(1kn-2)个边不交的哈密顿圈和2n-3-2k个完备匹配的并,且这个完备匹配和哈密顿圈是边不交的.并且证明这个猜想对于n=3,4以及n=5,6,k=1,2时是正确的.
【关键词】：互连网络 星连通圈网络 三角塔网络 图的嵌入 直径 Hamilton圈 条件连通度
【学位授予单位】：西北师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP338
【目录】：

• 摘要8-10
• Abstract10-12
• 第1章 研究背景12-14
• 1.1 研究背景12-13
• 1.2 本文的主要工作13-14
• 第2章 基本知识14-21
• 2.1 图论的有关术语及符号14-15
• 2.2 有关连通性方面的概念及一些引理15-17
• 2.3 星连通圈网络的概念和若干性质17-18
• 2.4 三角塔网络的概念和若干性质18-21
• 第3章 星连通圈网络的主要结果21-38
• 3.1 星连通圈网络n-SCC的泛圈性21-29
• 3.2 完全二叉树到星连通圈网络的嵌入29-32
• 3.3 星连通圈网络的条件点连通度32-38
• 第4章 三角塔网络的主要结果38-44
• 4.1 三角塔网络的直径和平均距离38-41
• 4.2 三角塔网络的Hamilton性41-44
• 第5章 结束语44-45
• 参考文献45-49
• 攻读硕士学位期间发表的论文49-50
• 致谢50

【相似文献】

中国期刊全文数据库 前10条

1 李炯生,范益政;关于图的代数连通度的注记(英文)[J];中国科学技术大学学报;2002年01期

2 刘凤霞;孟吉翔;;线图和有向线图的第二等周点连通度(英文)[J];新疆大学学报(自然科学版);2006年03期

3 雷澜;李霄民;;关于广义棱连通度的一个注记[J];西南师范大学学报(自然科学版);2008年03期

4 蔡华;;图有较高连通度的一个充要条件[J];昌吉学院学报;2009年02期

5 林辉球;孟吉翔;田应智;;立方体的线图的限制性连通度(英文)[J];新疆大学学报(自然科学版);2010年01期

6 萨如拉;阿勇嘎;;三次图的完全扩容图的连通度(英文)[J];宝鸡文理学院学报(自然科学版);2012年01期

7 王国亮;师海忠;;完全对换网络的限制连通度[J];运筹学学报;2013年03期

8 孙惠泉;线图的连通度[J];数学年刊A辑(中文版);1986年05期

9 周永生，，林秀琴，李唐芬;环网的强连通度与最佳强连通性[J];计算机应用;1995年01期

10 吴强;独立数、连通度及r－消去图[J];山东工业大学学报;1995年02期

中国重要会议论文全文数据库 前1条

1 吴俊;邓宏钟;谭跃进;;基于自然连通度的随机网络抗毁性研究[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

中国博士学位论文全文数据库 前9条

1 杨超;乘积图的连通度和容错直径的研究[D];中国科学技术大学;2007年

2 李莎莎;图的广义连通度若干问题的研究[D];南开大学;2012年

3 田应智;图的超连通性和限制性连通度[D];新疆大学;2012年

4 李玮;完全多部图的广义连通度[D];南开大学;2012年

5 熊玮;几类图参数的研究[D];新疆大学;2014年

6 洪艳梅;图连通度与非分离子图[D];上海大学;2012年

7 缪惠芳;图的连通度、强定向及无线传感器网络[D];厦门大学;2008年

8 顾磊;社会网络：拓扑性质与代数性质[D];上海交通大学;2011年

9 郭龙坤;基于不相交路径技术的可靠网络设计[D];中国科学技术大学;2011年

中国硕士学位论文全文数据库 前10条

1 万敏;星图的一种条件连通度[D];新疆大学;2008年

2 刘晓妍;2-连通[4，2]-图中的圈与高连通度图的完全圈可扩性[D];山东师范大学;2006年

3 刘凤霞;一些重要图类的条件连通度[D];新疆大学;2006年

4 雷泓昊;图的连通度与其路圈可扩性[D];山东师范大学;2007年

5 赵雪冰;（有向）图的邻域连通度的研究[D];新疆大学;2012年

6 林辉球;k-正则双轨道图的条件连通度[D];新疆大学;2010年

7 刘振华;全图的圈连通度[D];新疆大学;2011年

8 段晋芳;图的等周边连通度的最优化[D];太原科技大学;2011年

9 管宇;树的代数连通度[D];上海交通大学;2007年

10 王可可;一些特殊图的群连通度[D];北京交通大学;2011年

本文编号：716139