題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 超級(jí)立方體Qｎ的hamilton圈研究
- 來(lái)源：
- 第十二屆“挑戰(zhàn)杯”省賽作品
- 小類：
- 信息技術(shù)
- 簡(jiǎn)介：
- 本作品利用圖的笛卡爾積的概念來(lái)定義超級(jí)立方體Qn，討論圖的同構(gòu)與圖的笛卡爾積之間的關(guān)系，證明Qn中存在Hamilton圈，給出Qn中Hamilton圈的生成算法，從理論和實(shí)踐上解決了Qn中Hamilton圈問(wèn)題。
- 詳細(xì)介紹：
- 給定一個(gè)圖G，我們并不是直接討論它的Hamilton圈的存在性，而是討論笛卡爾積H=G?K2的Hamilton圈的存在問(wèn)題，如果圖G存在Hamilton圈，那么G?K2也存在Hamilton圈，這樣使得我們可以把一些特殊的圖分解成某一個(gè)圖G和K2的笛卡爾積，從而由G的Hamilton性來(lái)得出特殊圖的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]。無(wú)向圖中Hamilton圈是遍歷圖中每個(gè)頂點(diǎn)恰好一次又返回起點(diǎn)的圈。確定一個(gè)圖中這樣的圈是否存在就是Hamilton圈問(wèn)題，它是一個(gè)NP完全問(wèn)題。實(shí)際應(yīng)用（特別是計(jì)算機(jī)網(wǎng)絡(luò)中的應(yīng)用）和計(jì)算復(fù)雜性的研究推動(dòng)了Hamilton圈問(wèn)題的研究[1][2][3][4]。Hamilton圈問(wèn)題的研究由來(lái)已久。Dirac于1952就證明了：如果G是至少有三個(gè)頂點(diǎn)的簡(jiǎn)單圖且每個(gè)頂點(diǎn)的度數(shù)大于等于n/2存在Hamilton圈; Bondy-Chvátal1972年給出了定理：一個(gè)圖存在Hamilton圈的充要條件是它的閉包存在Hamilton圈；Tutte也于1956年證明每一個(gè)4-連通的平面圖存在Hamilton圈[5]。宋玉梅在1999年證明：一個(gè)簡(jiǎn)單圖存在Hamilton圈的充要條件是其PerGR非零[6]。與此同時(shí)，對(duì)一些特殊圖的Hamilton圈問(wèn)題的研究也很活躍。例如，F(xiàn)leischner研究了圖的平方中Hamilton圈問(wèn)題，并于1974年證明了：如果G是一個(gè)2-連通的圖，那么G2存在Hamilton圈[5]；Chvátal于1985年研究了旅行商問(wèn)題中Hamilton圈[7]；Jackson1980年證明了度數(shù)至少為n (G) / 3的任意簡(jiǎn)單正則圖存在Hamilton圈[8]， 這一結(jié)論由Zhu Y. J., Z. H. Liu和 Z. G. Yu等人進(jìn)行了改進(jìn)[9]。本文研究超立方體網(wǎng)絡(luò)中的Hamilton圈。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 本作品利用圖的笛卡爾積的概念來(lái)定義超級(jí)立方體Qn，討論圖的同構(gòu)與圖的笛卡爾積之間的關(guān)系， 證明Qn中存在Hamilton圈，給出Qn中Hamilton圈的生成算法，從理論和實(shí)踐上解決了Qn中Hamilton圈問(wèn)題。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 超級(jí)立方體是納米計(jì)算機(jī)的基本結(jié)構(gòu)，作為多核計(jì)算機(jī)技術(shù)的中間體系結(jié)構(gòu)，研究超級(jí)立方體Qn的性質(zhì)無(wú)疑具有重要意義。本作品從理論上證明了Qn中存在Hamilton圈，揭示了Qn中Hamilton圈的生成過(guò)程，全面系統(tǒng)討論了圖的笛卡爾積和圖的同構(gòu)的關(guān)系，為尋找圖中的Hamilton圈問(wèn)題開辟了新的方法和思路。
應(yīng)用價(jià)值和現(xiàn)實(shí)意義
- 本作品系統(tǒng)地運(yùn)用圖理論分析了圖的笛卡爾積和圖的同構(gòu)的關(guān)系, 對(duì)Qn中的Hamilton圈問(wèn)題, 既有理論證明, 又有具體的生成算法, 徹底解決了Qn中Hamilton圈問(wèn)題, 將為設(shè)計(jì)互聯(lián)網(wǎng)算法提供更好的思路。在容錯(cuò)超立方體網(wǎng)絡(luò)中，為滿足局部連通性條件的超立方體網(wǎng)絡(luò)中高效的容錯(cuò)路由算法，提供了一種新思路。在超立方體多微處理機(jī)系統(tǒng)以及超立方體計(jì)算機(jī)網(wǎng)絡(luò)中有很好的應(yīng)用價(jià)值。
學(xué)術(shù)論文摘要
- 給定一個(gè)圖G，我們并不是直接討論它的Hamilton圈的存在性，而是討論笛卡爾積H=G?K2的Hamilton圈的存在問(wèn)題，如果圖G存在Hamilton圈，那么G?K2也存在Hamilton圈，這樣使得我們可以把一些特殊的圖分解成某一個(gè)圖G和K2的笛卡爾積，從而由G的Hamilton性來(lái)得出特殊圖的Hamilton。 超立方體是互聯(lián)網(wǎng)的一種基本類型, 作品利用圖的笛卡爾積的概念來(lái)定義超立方體Qn, 討論了圖的同構(gòu)與圖的笛卡爾積之間的關(guān)系, 證明了超立方Qn (n≥1)中存在Hamilton圈, 給出Qn中Hamilton圈的生成算法, 同時(shí)對(duì)Qn的其他性質(zhì), 如歐拉性和二部性等也進(jìn)行了介紹。
獲獎(jiǎng)情況
- 無(wú)
鑒定結(jié)果
- 無(wú)
參考文獻(xiàn)
- 參考技術(shù)： Lih-Hsing Hsu, Cheng-Kuan Lin寫了一本關(guān)于圖論和互聯(lián)網(wǎng)的專著, 宋玉梅在1999年證明: 一個(gè)簡(jiǎn)單連通圖存在Hamilton圈的充要條件是其鄰接矩陣的恒式PerGR非零, Jackson1980年證明了度數(shù)至少為n (G) / 3的任意簡(jiǎn)單正則圖存在Hamilton圈，這一結(jié)論由Zhu Y.J.，Z.H.Liu和 Z.G.Yu等人進(jìn)行了改進(jìn)，王艷芳給出了2npm階群上Caylay圖的Hamilton圈分解， Yan zhong Hu, Hao Li對(duì)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 圖的充分必要條件, 長(zhǎng)春大學(xué) 學(xué)報(bào), Vol.19, No.13, June, 1999, pp. 15-16.
同類課題研究水平概述
- 無(wú)向圖中Hamilton圈是遍歷圖中每個(gè)頂點(diǎn)恰好一次又返回起點(diǎn)的圈。確定一個(gè)圖中這樣的圈是否存在就是Hamilton圈問(wèn)題，它是一個(gè)NP完全問(wèn)題。實(shí)際應(yīng)用（特別是計(jì)算機(jī)網(wǎng)絡(luò)中的應(yīng)用）和計(jì)算復(fù)雜性的研究推動(dòng)了Hamilton圈問(wèn)題的研究。 Hamilton圈問(wèn)題的研究由來(lái)已久。 Bondy-Chvátal1972年給出了定理: 一個(gè)圖存在Hamilton圈的充要條件是它的閉包存在Hamilton圈; Tutte也于1956年證明每一個(gè)4-連通的平面圖存在Hamilton圈。宋玉梅在1999年證明: 一個(gè)簡(jiǎn)單連通圖存在Hamilton圈的充要條件是其鄰接矩陣的恒式PerGR非零。與此同時(shí)，對(duì)一些特殊圖的Hamilton圈問(wèn)題的研究也很活躍。例如， Fleischner研究了圖的平方中Hamilton圈問(wèn)題，并于1974年證明了; 如果G是一個(gè)2-連通的圖，那么G2存在Hamilton圈; Chvátal于1985年研究了旅行商問(wèn)題中Hamilton圈; Jackson1980年證明了度數(shù)至少為n (G) / 3的任意簡(jiǎn)單正則圖存在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對(duì)8階立方圖(3正則圖)進(jìn)行了分類，并證明了它們的Hamilton性。 國(guó)內(nèi)外研究圖的Hamilton圈十分活躍，但是關(guān)于Qn中Hamilton圈的研究的報(bào)告還未見到，作品提到的方法和思想具有創(chuàng)新獨(dú)特之處，有很好的借鑒作用。
