【正文】 、 ADECBA(190) 、 AEBCDA(250) 、 AEBDCA(250)、 AECBDA(270) 、AECDBA(260)、 AEDBCA(190)、 AEDCBA(180)。 如果十個(gè)地點(diǎn)還可以 12 勉強(qiáng)算出來，那么地點(diǎn)數(shù)量達(dá)到 300 個(gè)或者 500個(gè)呢？那時(shí)候的計(jì)算量是我們無法想象的，而這種情況對(duì)于像中國這樣的大國來說，是非?，F(xiàn)實(shí)的問題。本文借鑒總結(jié)了大量前人的結(jié)論 ，著重介紹了哈密爾頓圖判定上的五種方法和結(jié)論，并初步對(duì)這五種方法的應(yīng)用范圍進(jìn)行了分類。 [6] 羅示豐 , 判別哈密爾頓圖的新方法 [J], 廣西科學(xué)院學(xué)報(bào) ,2020 年 2 月第十七卷第 1期。 [15]耿素云 , 屈婉玲 . 離散數(shù)學(xué)基礎(chǔ) , 北京大學(xué)出版社 , 1994 年 7 月第 1 版 。 15 作者簡歷 徐杰一村，男，出生與 1990 年 4月，浙江省寧波市余姚市人， 2020 年 9 月至 2020 年 6 月就讀于中國計(jì)量學(xué)院。 [21]李修睦 , 《 圖論導(dǎo)引 》 ,華中工學(xué)院出版社， 1982， 107— 108。 [13] Liqun Pua, HungLin Fub, Hao Shenc Maximal sets of Hamilton cycles in Dn[ J] scienceDirect 2020。 [4] 尹家洪 , 鄰集并與 hamiltonian 性 [ J] , 東南大學(xué)學(xué)報(bào) , 1991, 21 。 13 4 結(jié)論 哈密爾頓圖相可以應(yīng)用的范圍已經(jīng)越來越廣闊，從工業(yè)鋪路到農(nóng)業(yè)灌溉，航空路線到海底勘探，從國家的發(fā)展到公司的運(yùn)輸，都可以用到哈密爾頓圖的知識(shí)。當(dāng)計(jì)算到 ABEDCA 這條路徑時(shí)，我們發(fā)現(xiàn)數(shù)值是170，那么之后的數(shù)值如明顯大于 170，那么久可以用“ ≥ 170”來替代，這樣可以節(jié)省一定的計(jì)算時(shí)間，加快得出結(jié)果的速度。 見圖 34。 德國是一個(gè)非常嚴(yán)謹(jǐn)?shù)膰?，德國的波恩大學(xué)的一位數(shù)學(xué)家很好的發(fā)揮了這一特點(diǎn)，當(dāng)他知道 西德有 120 個(gè)有鐵路穿過的城市后，就準(zhǔn)備找到一個(gè)最短路程的回路，應(yīng)該怎么樣去跑。 這類的問題還有很多， 而這些問題都可以歸結(jié)為貨郎擔(dān)問題。這個(gè)問題可以表述為：假設(shè)一個(gè)售貨員需要在 n個(gè)城市之間進(jìn)行銷售，現(xiàn)在我們已經(jīng)知道了 這 n個(gè)城市中任意的兩個(gè)城市之間的距離，現(xiàn)在售貨員需要選擇一條路線使得從出發(fā)的城市開始，經(jīng)過其他的城市有且僅有一次，最后回到出發(fā)點(diǎn)，問這個(gè)售貨員應(yīng)該怎么樣選擇路線呢。在應(yīng)用博薩定理時(shí) D(G4)=(3， 3， 3， 3， 3， 3， 3， 3)， P(8)= （ 1，2， 3， 4， 4， 4， 4， 4）；此時(shí)我們是不能說 D(G4)≥ P(8)的，沒辦法判定 G4 是哈密 爾 頓圖。應(yīng)用 狄拉克定理時(shí)， 明顯 n=5 且 D(x)=2≤ 5/2=n/2，不能判 定它是哈密爾頓圖。 若 V1 當(dāng)中的頂點(diǎn)是在 C上彼此相鄰的頂點(diǎn)，那么顯然有： P(CV1)=1≤ |V1|； （ 2） 若 V1 中的頂點(diǎn)是在 C上存在 m個(gè)互不相鄰，那么 就有： P(CV1)=m≤ |V1| 所以無論 V1 中的頂點(diǎn)在 C 上是相鄰或是不相鄰，或者兼有，都可以得到結(jié)論 P(CV1)≤ |V1| 同時(shí)由于 C 是圖 G的生成子圖，所以可以得到： P(CV1)≤ P(GV1) ≤ |V1| 一般時(shí)候定理 5 可以用來判定一個(gè)圖是非哈密爾頓圖 。目前為止，薩瓦達(dá)定理依舊是一種較好的哈密爾頓圖的判定方法。 再假設(shè)有兩個(gè)序列其具有相同個(gè)數(shù)的數(shù)字： X=（ x1， x2， ? ， xn）； Y=（ y1， y2， ? ， yn）。 狄拉克定理 和奧勒定理 最早提出判定哈密爾頓圖的是 英國的數(shù)學(xué)家狄拉克。 一個(gè)圖假如含有哈密爾頓回路，則這個(gè)圖就是哈密爾頓圖 。 本文主要介紹哈密爾頓圖判定的狄拉克定理、奧勒定理、博薩定理、薩瓦達(dá)定理。 第 3 步 : 刪去 kX 以及與 3 kX 關(guān)聯(lián)的所有邊 。 ：對(duì)于頂點(diǎn)個(gè)數(shù)大于 2的圖，如果圖中任意兩點(diǎn)度的和大于或等于頂點(diǎn)總數(shù)，那這個(gè)圖一定是哈密爾頓圖。 其在貨郎擔(dān)問題的研究上，更是進(jìn)幾十年才受到重視，然而他的應(yīng)用卻是非常廣泛的，同樣的方法，可以用以地震搜救，糧食分派，糧食運(yùn)輸，外出旅游等類似的各 個(gè)方面。 他發(fā)現(xiàn)的這個(gè)代數(shù)系統(tǒng)是和正則 12 面體有關(guān)的 。 Traveling salesman problem Classification:O157 III 目 次 摘要： ............................................. 錯(cuò)誤 !未定義書簽。合理的利用哈密爾頓圖的結(jié)論，不僅可以節(jié)約大量的時(shí)間，更可以降低發(fā)展的成本。對(duì)本論文所涉及的研究工作做出貢獻(xiàn)的其他個(gè)人和集體，均已在文中以明確的方式標(biāo)明。 從論文開始到結(jié)束，一直是在陳琴老師的指導(dǎo)下完成的，可以說沒有老師的悉心指導(dǎo)，就沒有這篇論文的誕生，在此，衷心感謝陳琴老師對(duì)我的指導(dǎo)。闡述了哈密爾頓圖的研究現(xiàn)狀和本文研究方向。 1 引言 ............................................................ 1 哈密爾頓圖的起源 ........................................... 1 研究背景和意義 ............................................. 2 哈密 爾 頓圖判定方法的發(fā)展 ................................... 2 本文的研究方向 ............................................. 3 2 哈密爾頓圖的判定 ................................................ 4 哈密爾頓圖的定義 ........................................... 4 哈密爾頓圖的集中判定方法 ................................... 4 實(shí)例解析 ................................................... 6 3 哈密爾頓圖的判定在貨郎擔(dān)問題中的應(yīng)用 ............................ 8 貨郎擔(dān)問題的由來和在現(xiàn)實(shí)中的應(yīng)用 ............................ 8 貨郎擔(dān)問題解決方法 .......................................... 8 樹的搜索法 .................................................. 9 4 結(jié)論 ........................................................... 13 參考文獻(xiàn) ........................................................... 14 作者簡歷 ........................................................... 15 學(xué)位論文數(shù)據(jù)集 ..................................................... 16 63 1 1 引言 在查閱了大量資料后，可以發(fā)現(xiàn)哈密 爾 頓圖在數(shù)學(xué)理論研究和