扭n立方體邊不交Hamilton圈的研究.pdf

1、互連網(wǎng)絡(luò)是數(shù)學(xué)和計算機科學(xué)的一個研究熱點，它在圖論、算法設(shè)計與分析、計算機體系結(jié)構(gòu)、并行與分布計算、計算機網(wǎng)絡(luò)與通信以及大規(guī)模集成電路的設(shè)計等諸多方面起著非常重要的作用.超立方體及其變體是一類具有良好的拓撲性質(zhì)和網(wǎng)絡(luò)參數(shù)的互連網(wǎng)絡(luò)模型，關(guān)于它們的研究與應(yīng)用在互連網(wǎng)絡(luò)的研究中備受青睞. 本文主要研究超立方體的一種變體——扭n立方體中邊不交Hamilton圈問題.邊不交Hamilton圈問題指的是在圖G中尋找盡可能多的Hamilto

2、n圈，且各Hamilton圈的邊互不相交. 首先，在充分考慮4元n立方體中邊不交Hamilton圈的算法的基礎(chǔ)上，本文結(jié)合Lee距離Gray碼理論，利用其結(jié)構(gòu)的遞推性，證明了它的一個重要性質(zhì)，即：當(dāng)n為偶數(shù)時，由Bae和Bose提出的Gray碼生成函數(shù)h0生成的Hamilton圈H0一定含有路<0n-200，0n-201，0n-202，0n-203>；當(dāng)n為奇數(shù)時，由h0生成的Hamilton圈H0'經(jīng)“邊變換”后得到的Hami

3、lton圈H0也一定含有此路.然后，利用這個性質(zhì)，構(gòu)造了2m維超立方體與4元m立方體的同構(gòu)映射f，并將兩者聯(lián)系起來研究，得出了n維超立方體中的Hamilton圈H0一定含有路<0n-200，0n-201，0n-211，0n-210>的結(jié)論.最后，依據(jù)扭n立方體與n維超立方體的關(guān)系，通過作相應(yīng)的頂點對應(yīng)變換，給出了扭n立方體中存在[n/2]個邊不交Hamilton圈的結(jié)論，同時對這[n/2]個邊不交Hamilton圈的生成算法進行了具體的