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

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

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

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