交叉立方體連通圈網(wǎng)絡(luò)的Hamilton分解

張欣++師海忠

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

關(guān)鍵詞：互連網(wǎng)絡(luò)；交叉立方體連通圈網(wǎng)絡(luò)；Hamilton圈；完美對(duì)集

中圖分類號(hào)：PT393

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.3969/j.issn.1003-6970.2015.08.020

0 引言

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

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

交叉立方體連通圈網(wǎng)絡(luò)CQCC（n）（n≥3）是3正則的，在文獻(xiàn)[15]中師海忠提出如下猜想：交叉立方體連通圈網(wǎng)絡(luò)CQCC（n）（n≥3）可分解為邊不交的一個(gè)Hamilton圈和一個(gè)完美對(duì)集的并，在本文中給出了交叉立方體連通圈網(wǎng)絡(luò)CQCC（n）（n≥3）當(dāng)n=3；4；5；6時(shí)的Hamilton圈和相應(yīng)的完美對(duì)集，也就是說，對(duì)n=3；4；5；6猜想成立。endprint