交叉立方體連通圈網絡的Hamilton分解

張欣++師海忠

摘要：交叉立方體連通圈網絡CQCC（n）（n≥3）是一類典型的互連網絡，它是3正則的，在2010年，師海忠提出如下猜想：CQCC（n）（n≥3）是Hamilton可分解的，也就是說，交叉立方體連通圈網絡CQCC（n）（n≥3）可分解為邊不交的一個Hamilton圈和一個完美對集的并，在這篇文章中，證明了當n=3；4；5；6時猜想成立，即交叉立方體連通圈網絡CQCC（n）（n=3；4；5；6）可分解為邊不交的一個Hamilton圈和一個完美對集的并。

關鍵詞：互連網絡；交叉立方體連通圈網絡；Hamilton圈；完美對集

中圖分類號：PT393

文獻標識碼：A

DOI：10.3969/j.issn.1003-6970.2015.08.020

0 引言

超級計算機為實現高性能計算提供了硬件支持，為了滿足對計算能力日益增長的需求，需要設計出更好性能的超級計算機?；ミB網絡是超級計算機的重要組成部分，互連網絡的性能在很大程度上決定超級計算機的性能?；ミB網絡常常模型化為一個無向圖，頂點對應處理機，邊對應通信鏈路。在文獻[12-15]中設計出了具有小的固定的度（為3）的多種互連網絡。受細胞分裂生長過程的啟發(fā)，在文獻[16]中，提出了互連網絡的細胞分裂結構圖模型，在文獻[15； 17-18]中研究了多種互聯(lián)網絡的Hamilton分解。

在文獻[15]中，師海忠設計出了一類互連網絡l{交叉立方體連通圈網絡CQCC（n）（n≥3），也就是用連通圈替代交叉超立方體網絡中的結點設計出的網絡，改進了交叉超立方體網絡的度隨著其規(guī)模（頂點個數）的增大而增大的缺點。交叉立方體連通圈網絡具有小的固定的度（為3）這一良好的性質，并且CQCC（n）的頂點數為n·2n個。

交叉立方體連通圈網絡CQCC（n）（n≥3）是3正則的，在文獻[15]中師海忠提出如下猜想：交叉立方體連通圈網絡CQCC（n）（n≥3）可分解為邊不交的一個Hamilton圈和一個完美對集的并，在本文中給出了交叉立方體連通圈網絡CQCC（n）（n≥3）當n=3；4；5；6時的Hamilton圈和相應的完美對集，也就是說，對n=3；4；5；6猜想成立。endprint