題-1_100_100.jpg)
基本信息
- 項目名稱：
- 超級立方體Qｎ的hamilton圈研究
- 小類：
- 信息技術(shù)
- 簡介：
- 本作品利用圖的笛卡爾積的概念來定義超級立方體Qn，討論圖的同構(gòu)與圖的笛卡爾積之間的關(guān)系，證明Qn中存在Hamilton圈，給出Qn中Hamilton圈的生成算法，從理論和實(shí)踐上解決了Qn中Hamilton圈問題。
- 詳細(xì)介紹：
- 給定一個圖G，我們并不是直接討論它的Hamilton圈的存在性，而是討論笛卡爾積H=G?K2的Hamilton圈的存在問題，如果圖G存在Hamilton圈，那么G?K2也存在Hamilton圈，這樣使得我們可以把一些特殊的圖分解成某一個圖G和K2的笛卡爾積，從而由G的Hamilton性來得出特殊圖的Hamilton。 多處理器網(wǎng)絡(luò)是由圖的笛卡爾積構(gòu)造的，如網(wǎng)格，超立方體等。積網(wǎng)絡(luò)組成了非常重要的一類互聯(lián)網(wǎng)產(chǎn)品的網(wǎng)絡(luò)構(gòu)成了非常重要的類互連網(wǎng)絡(luò)[1]。無向圖中Hamilton圈是遍歷圖中每個頂點(diǎn)恰好一次又返回起點(diǎn)的圈。確定一個圖中這樣的圈是否存在就是Hamilton圈問題，它是一個NP完全問題。實(shí)際應(yīng)用（特別是計算機(jī)網(wǎng)絡(luò)中的應(yīng)用）和計算復(fù)雜性的研究推動了Hamilton圈問題的研究[1][2][3][4]。Hamilton圈問題的研究由來已久。Dirac于1952就證明了：如果G是至少有三個頂點(diǎn)的簡單圖且每個頂點(diǎn)的度數(shù)大于等于n/2存在Hamilton圈; Bondy-Chvátal1972年給出了定理：一個圖存在Hamilton圈的充要條件是它的閉包存在Hamilton圈；Tutte也于1956年證明每一個4-連通的平面圖存在Hamilton圈[5]。宋玉梅在1999年證明：一個簡單圖存在Hamilton圈的充要條件是其PerGR非零[6]。與此同時，對一些特殊圖的Hamilton圈問題的研究也很活躍。例如，F(xiàn)leischner研究了圖的平方中Hamilton圈問題，并于1974年證明了：如果G是一個2-連通的圖，那么G2存在Hamilton圈[5]；Chvátal于1985年研究了旅行商問題中Hamilton圈[7]；Jackson1980年證明了度數(shù)至少為n (G) / 3的任意簡單正則圖存在Hamilton圈[8]， 這一結(jié)論由Zhu Y. J., Z. H. Liu和 Z. G. Yu等人進(jìn)行了改進(jìn)[9]。本文研究超立方體網(wǎng)絡(luò)中的Hamilton圈。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 本作品利用圖的笛卡爾積的概念來定義超級立方體Qn，討論圖的同構(gòu)與圖的笛卡爾積之間的關(guān)系， 證明Qn中存在Hamilton圈，給出Qn中Hamilton圈的生成算法，從理論和實(shí)踐上解決了Qn中Hamilton圈問題。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 超級立方體是納米計算機(jī)的基本結(jié)構(gòu)，作為多核計算機(jī)技術(shù)的中間體系結(jié)構(gòu)，研究超級立方體Qn的性質(zhì)無疑具有重要意義。本作品從理論上證明了Qn中存在Hamilton圈，揭示了Qn中Hamilton圈的生成過程，全面系統(tǒng)討論了圖的笛卡爾積和圖的同構(gòu)的關(guān)系，為尋找圖中的Hamilton圈問題開辟了新的方法和思路。
應(yīng)用價值和現(xiàn)實(shí)意義
- 本作品系統(tǒng)地運(yùn)用圖理論分析了圖的笛卡爾積和圖的同構(gòu)的關(guān)系, 對Qn中的Hamilton圈問題, 既有理論證明, 又有具體的生成算法, 徹底解決了Qn中Hamilton圈問題, 將為設(shè)計互聯(lián)網(wǎng)算法提供更好的思路。在容錯超立方體網(wǎng)絡(luò)中，為滿足局部連通性條件的超立方體網(wǎng)絡(luò)中高效的容錯路由算法，提供了一種新思路。在超立方體多微處理機(jī)系統(tǒng)以及超立方體計算機(jī)網(wǎng)絡(luò)中有很好的應(yīng)用價值。
學(xué)術(shù)論文摘要
- 給定一個圖G，我們并不是直接討論它的Hamilton圈的存在性，而是討論笛卡爾積H=G?K2的Hamilton圈的存在問題，如果圖G存在Hamilton圈，那么G?K2也存在Hamilton圈，這樣使得我們可以把一些特殊的圖分解成某一個圖G和K2的笛卡爾積，從而由G的Hamilton性來得出特殊圖的Hamilton。 超立方體是互聯(lián)網(wǎng)的一種基本類型, 作品利用圖的笛卡爾積的概念來定義超立方體Qn, 討論了圖的同構(gòu)與圖的笛卡爾積之間的關(guān)系, 證明了超立方Qn (n≥1)中存在Hamilton圈, 給出Qn中Hamilton圈的生成算法, 同時對Qn的其他性質(zhì), 如歐拉性和二部性等也進(jìn)行了介紹。
獲獎情況
- 無
鑒定結(jié)果
- 無
參考文獻(xiàn)
- 參考技術(shù)： Lih-Hsing Hsu, Cheng-Kuan Lin寫了一本關(guān)于圖論和互聯(lián)網(wǎng)的專著, 宋玉梅在1999年證明: 一個簡單連通圖存在Hamilton圈的充要條件是其鄰接矩陣的恒式PerGR非零, Jackson1980年證明了度數(shù)至少為n (G) / 3的任意簡單正則圖存在Hamilton圈，這一結(jié)論由Zhu Y.J.，Z.H.Liu和 Z.G.Yu等人進(jìn)行了改進(jìn)，王艷芳給出了2npm階群上Caylay圖的Hamilton圈分解， Yan zhong Hu, Hao Li對8階立方圖(3正則圖)進(jìn)行了分類，并證明了它們的hamilton性。 主要參考文獻(xiàn)： [1] Lih-Hsing Hsu, Cheng-Kuan Lin, Graph Theory and Intrerconnection Networks, New York: CRC Press, Sept. 2008, pp. 171–221. [2] Gary Chartrand and Ping Zhang(美).范益政, 汪毅, 龔世才, 朱明譯.圖論導(dǎo)引.北京: 人民郵電出版社, 2007, pp. 122–132. [3] J Douglas B.West(美).李建中, 駱吉州譯.圖論導(dǎo)引.北京: 機(jī)械工業(yè)出版社, 2006, pp. 229–231. [4] Bondy, J. A. and Murty, U. S . R. , Graph Theory with Applications, Macmillan Press Ltd. , 1976, pp.3–5. [5] Reinhard Diestel, Graph Theory 3rd ed, Beijing: , Mar. 2008, pp.275–278. [6] 宋玉梅, 關(guān)于 Hamilton 圖的充分必要條件, 長春大學(xué) 學(xué)報, Vol.19, No.13, June, 1999, pp. 15-16.
同類課題研究水平概述
- 無向圖中Hamilton圈是遍歷圖中每個頂點(diǎn)恰好一次又返回起點(diǎn)的圈。確定一個圖中這樣的圈是否存在就是Hamilton圈問題，它是一個NP完全問題。實(shí)際應(yīng)用（特別是計算機(jī)網(wǎng)絡(luò)中的應(yīng)用）和計算復(fù)雜性的研究推動了Hamilton圈問題的研究。 Hamilton圈問題的研究由來已久。 Bondy-Chvátal1972年給出了定理: 一個圖存在Hamilton圈的充要條件是它的閉包存在Hamilton圈; Tutte也于1956年證明每一個4-連通的平面圖存在Hamilton圈。宋玉梅在1999年證明: 一個簡單連通圖存在Hamilton圈的充要條件是其鄰接矩陣的恒式PerGR非零。與此同時，對一些特殊圖的Hamilton圈問題的研究也很活躍。例如， Fleischner研究了圖的平方中Hamilton圈問題，并于1974年證明了; 如果G是一個2-連通的圖，那么G2存在Hamilton圈; Chvátal于1985年研究了旅行商問題中Hamilton圈; Jackson1980年證明了度數(shù)至少為n (G) / 3的任意簡單正則圖存在Hamilton圈，這一結(jié)論由Zhu Y.J.， Z.H.Liu和 Z.G.Yu等人進(jìn)行了改進(jìn)。 王艷芳2009年給出了2npm階群上Caylay圖的Hamilton圈分解。 2011年，Yan zhong Hu, Hao Li對8階立方圖(3正則圖)進(jìn)行了分類，并證明了它們的Hamilton性。 國內(nèi)外研究圖的Hamilton圈十分活躍，但是關(guān)于Qn中Hamilton圈的研究的報告還未見到，作品提到的方法和思想具有創(chuàng)新獨(dú)特之處，有很好的借鑒作用。
