k次Herschel—师连通圈网络

师海忠，陈璐璐



k次Herschel—师连通圈网络

师海忠，陈璐璐

（西北师范大学 数学与统计学院，甘肃 兰州 730070）

互连网络是超级计算机的重要组成部分，片上互连网络是当前研究的热点课题之一。2010年师海忠提出互连网络的正则图连通圈网络模型。在这篇文章中利用此模型设计出了k次Herschel-师连通圈网络HSCC(1,k),证明了HSCC(1,0)是3正则3连通平面Hamiton图，且HSCC(1,k)是3正则3连通平面Hamiton图。利用笛卡尔乘积设计出了互连网络HSCC(1,k)×K2和HSCC(1,k)´Cm，进一步研究了HSCC(1,k)´K2和HSCC(1,k)´Cm的一些性质。

HSCC(1,k)；Hamilton图；笛卡尔积；完美对集

0 引言

互连网络是超级计算机的重要组成部分，片上互连网络是当前研究的热点课题之一，它的性能在某种程度上决定着超级计算机的性能。互连网络通常被模型化为一个图，图的结点对应处理机，图的边对应通信全过程。各种已有互连网络参见[1,2,4-12]。根据师海忠在中国运筹会第十届学术交流会上提出的超级计算机多种互连网络统一体——正则连通圈网络，且它的度为3。在这篇文章中，师海忠设计出了互连网络HSCC(1,0)：将Herschel图经过4度顶点用4圈代替、3度顶点用3圈代替原来顶点构造了新的网络HSCC(1,0)，陈璐璐证明了HSCC(1,0)是3正则3连通平面Hamilton图，师海忠进一步提出了k次Herschel—师连通圈网络HSCC(1,k)：用3长的圈代替HSCC(1,0)中的每个顶点构造了新的网

络HSCC(1,1)，重复k次，我们得到的新的网络HSCC(1,k)，陈璐璐证明了k次Herschel—师连通圈网络为3正则3连通平面Hamilton图。师海忠还设计出了HSCC(1,k)´K2和HSCC(1,k)´Cm，并提出了如下猜想：

猜想1：HSCC(1,k)´k2是边不交的两个Hamilton的并；

猜想2：HSCC(1,k)´Cm（k=0, m≥3）是边不交的两个Hamilton圈和一个完美对集的并。

陈璐璐证明了HSCC(1,0)´k2是一个边不交的Hamilton圈和两个完美对集的并，还给出了HSCC (1,k)´K2和HSCC(1,k)´Cm的一些性质。……