Torus网络的不交路覆盖

来源 :太原科技大学 | 被引量 : 0次 | 上传用户:edyzhang1979
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着现代科研、医学、工程、军事等行业的迅猛发展,各种信息数据量大规模膨胀,这对处理这些数据的计算机性能提出极高的要求,所以建造高性能、大规模的超级计算机来处理这些“天量”的信息数据势在必行。超级计算机系统的实现最主要是依赖处理器之间的连接方式,这些连接方式被称为该系统的互连网络。互连网络的性能对整个并行计算机系统的性能起着重要的作用,决定着整个系统的安全性、实用性和可靠性。本文研究的对象Torus网络具有很多优良性质,是目前应用最广的分布式计算机系统互连网络之一。不交路覆盖问题不但与网络的连通度有关,而且与网络的哈密尔顿连通性也密切相关,因此是互连网络设计和分析中重要的研究内容。设S和T={t 1,t2,…,t m}分别是图G中的一个源点和m个汇点,若图G中存在m条内部不相交的路P1,P2,…,P m满足iP连接S和ti,其中i=1,2,…,m,且Umi=1V(P i)=V(G),则称Umi=1 iP是图G的一对多m不交路覆盖。设S={s 1,s 2,…,s m}和T={t 1,t 2,…,t m}分别是图G中的m个源点和m个汇点,若图G中存在m条不相交的路P1,P 2,…,Pm满足iP连接si和t i,其中i=1,2,…,m,且Umi=1V(P i)=V(G),则称Umi=1P i是图G的多对多m不交路覆盖。本文对二维Torus网络的不交路覆盖问题进行了研究,首先分别考虑了二部的二维Torus网络和非二部的二维Torus网络的一对多三不交路覆盖性,接着证明了二部的二维Torus网络具有非指定多对多三不交路覆盖性,最后将结果扩展到高维k元n立方体上,对其多对多不交路覆盖性进行了探讨。本文的主要结果如下:定理1.当k1,k2≥5且均为奇数时,二维环面网络Torus(k1,k2)是一对多m不交路覆盖的,其中1≤m≤3。定理2.当k1,k2≥6且均为偶数时,二维环面网络Torus(k1,k2)是一对多三不交路覆盖的。定理3.当k1,k2≥6且均为偶数时,二维环面网络Torus(k1,k2)中存在非指定多对多三不交路覆盖。定理4.设偶数k≥4和整数n≥2,含f条故障边的k元n立方体Qnk是非指定多对多m不交路覆盖的,其中1≤m≤2n-1,f≤2n-m-1。
其他文献
近年来,我国对新能源汽车的使用也是十分提倡,这也是我国绿色环保意识的体现,随着对新能源汽车的不但研究和发展,新能源汽车产业发展也是逐渐成熟和稳定.在广西南宁地区,新能
利用表面活性剂淋洗的方式,对柴油污染土壤进行修复,已经成为相关领域重点研究的内容,具有良好的应用价值,能够在较短的期限内,实现对大面积污染土壤的修复,修复效果十分显著
近几年,现行的城市集中供热是国家控制的节能、降耗的重要目标,减少污染、降低消耗、节省能源业已成为锅炉供热生产的第一任务.这是国家倡导的建设资源节约、环境友好型社会