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

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

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

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