论文部分内容阅读
随着现代科研、医学、工程、军事等行业的迅猛发展,各种信息数据量大规模膨胀,这对处理这些数据的计算机性能提出极高的要求,所以建造高性能、大规模的超级计算机来处理这些“天量”的信息数据势在必行。超级计算机系统的实现最主要是依赖处理器之间的连接方式,这些连接方式被称为该系统的互连网络。互连网络的性能对整个并行计算机系统的性能起着重要的作用,决定着整个系统的安全性、实用性和可靠性。本文研究的对象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。