论文部分内容阅读
互连网络是超级计算机的重要组成部分.在设计和选择一个互连网络的拓扑结构时,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,当n>5时,κ1(n-SCC)=4而当n>4时,κ2(n-SCC)=n-1.并且星连通圈网络的1-条件连通度与2-限制连通度是相等的.2.三角塔网络的主要结果：(1)分析了一种新的互连网络-三角塔网络.当n>4时,它是极大连通的,紧的超连通的,即三角塔网络的连通度κ(TTn)=2n-3星网络是三角塔网络的子网络,说明Sn能以膨胀数1嵌入TTn.(2)给出了三角塔网络的直径和平均距离分别是「3(n-1)-1/2」和n+2/n-1-2Hn/n(n-1)-Hn. (3)提出了关于三角塔网络Hamilton性的一簇猜想：当n>3时,三角塔网络TTn可以分解成k(1<k<n-2)个边不交的哈密顿圈和2n-3-2k个完备匹配的并,且这个完备匹配和哈密顿圈是边不交的.并且证明这个猜想对于n=3,4以及n=5,6,k=1,2时是正确的.