【導(dǎo)讀】所取得的成果，所有數(shù)據(jù)、圖片資料真實(shí)可靠。盡我所知，除文中已經(jīng)。對(duì)本論文所涉及的研究工作做出貢獻(xiàn)的其他個(gè)人和集體，均已在文。中以明確的方式標(biāo)明。本學(xué)位論文的知識(shí)產(chǎn)權(quán)歸屬于培養(yǎng)單位。論文的撰寫工作已經(jīng)基本上完成，這段時(shí)間也經(jīng)歷了很多的波折。論文的誕生，在此，衷心感謝陳琴老師對(duì)我的指導(dǎo)。感謝老師不厭其煩的幫我修正論。文中的錯(cuò)誤，也感謝老師在我失去信心時(shí)的諄諄教誨。陳琴老師的嚴(yán)謹(jǐn)教學(xué)，用于創(chuàng)。新，善于發(fā)現(xiàn)的精神不但在學(xué)習(xí)上為我樹立了榜樣，也給我未來(lái)的生活帶來(lái)了幫助。同時(shí)，也感謝理學(xué)院老師的辛勤教育，感謝所有給我?guī)椭耐瑢W(xué)和朋友們。合理的利用哈密爾頓圖的結(jié)論，不僅可以節(jié)約大量的時(shí)間，更可。以降低發(fā)展的成本。圖的研究現(xiàn)狀和本文研究方向。理、博薩定理和薩瓦達(dá)定理，并且補(bǔ)充了一個(gè)判定哈密爾頓圖的必要條件。第三章著重介紹了貨郎擔(dān)問(wèn)題的起源和發(fā)展，并且補(bǔ)充了一種樹的搜索法。

　　

【正文】 部的工作后，我們回過(guò)頭去看這個(gè)方法，可以發(fā)現(xiàn)在最后一步的計(jì)算時(shí)，一部分的工作是可以省略的。比如當(dāng)我們找到第一條回路 ABCDEA 時(shí) ，我們可以知道這條路徑的長(zhǎng)度是 180，那么在之后的計(jì)算中，一旦發(fā)現(xiàn)路徑的長(zhǎng)度明顯大于 180，或者上一層的節(jié)點(diǎn)的數(shù)值已經(jīng)大于 180 了，那么我們直接可以用“ ≥ 180”來(lái)代替具體的數(shù)值。當(dāng)計(jì)算到 ABEDCA 這條路徑時(shí)，我們發(fā)現(xiàn)數(shù)值是170，那么之后的數(shù)值如明顯大于 170，那么久可以用“ ≥ 170”來(lái)替代，這樣可以節(jié)省一定的計(jì)算時(shí)間，加快得出結(jié)果的速度。 在上面方法展示的過(guò)程中我們可以發(fā)現(xiàn)，這樣的搜索方法在地點(diǎn)數(shù)量較少的時(shí)候還比較試用，一旦地點(diǎn)數(shù)量達(dá)到十個(gè)，那么我們的計(jì)算量將變的嚇人，甚至可以說(shuō)是超過(guò)了人腦的計(jì)算能力 ，我們會(huì)感到十分的繁瑣。 如果十個(gè)地點(diǎn)還可以 12 勉強(qiáng)算出來(lái)，那么地點(diǎn)數(shù)量達(dá)到 300 個(gè)或者 500個(gè)呢？那時(shí)候的計(jì)算量是我們無(wú)法想象的，而這種情況對(duì)于像中國(guó)這樣的大國(guó)來(lái)說(shuō)，是非常現(xiàn)實(shí)的問(wèn)題。這個(gè)時(shí)候我們就不得不借助計(jì)算機(jī)的力量。 計(jì)算機(jī)到底可以提升多少的計(jì)算速度呢？一個(gè)例子能夠很好的說(shuō)明問(wèn)題 ：在美國(guó)工作的華籍?dāng)?shù)學(xué)家 Lin Shen及 Hong Saman等人 在 1977年的時(shí)候用電子計(jì)算器計(jì)算得到了一個(gè)有關(guān)于 318個(gè)城市的貨郎擔(dān)問(wèn)題。 這個(gè)問(wèn)題 一旦 化成線性規(guī)劃問(wèn)題 ，那么 就要處理有 50403個(gè)變數(shù)的方程式及不等式 ，人腦對(duì)于這 樣的問(wèn)題雖然不能說(shuō)完全不能解決，但是所需要的時(shí)間將是難以想象的。而當(dāng)時(shí)的 Lin Shen等人借助了一臺(tái) IBM的 370— 168式的電子計(jì)算機(jī) 后，僅用了 個(gè)最優(yōu)解，納悶對(duì)于電子技術(shù)日新月異的今天，我們可能需要的時(shí)間已經(jīng)不足一分鐘。兩者互相對(duì)比，讓我們不得不承認(rèn)，以后的發(fā)展方向?qū)⒏嗟慕柚?jì)算機(jī)技術(shù)。 13 4 結(jié)論 哈密爾頓圖相可以應(yīng)用的范圍已經(jīng)越來(lái)越廣闊，從工業(yè)鋪路到農(nóng)業(yè)灌溉，航空路線到海底勘探，從國(guó)家的發(fā)展到公司的運(yùn)輸，都可以用到哈密爾頓圖的知識(shí)。哈密爾頓圖的研究已經(jīng)顯得越來(lái)越重要， 在效率第一的當(dāng)今社會(huì)，恰當(dāng)?shù)膽?yīng)用哈密爾頓圖的研究結(jié)果可以可以大大提高工作的效率和 節(jié)約發(fā)展成本，為可持續(xù)發(fā)展提供不可或缺的支持。本文借鑒總結(jié)了大量前人的結(jié)論 ，著重介紹了哈密爾頓圖判定上的五種方法和結(jié)論，并初步對(duì)這五種方法的應(yīng)用范圍進(jìn)行了分類。在哈密爾頓圖的應(yīng)用方面，著重介紹了貨郎擔(dān)問(wèn)題的研究。在解決方法上又介紹了樹的搜索法，同時(shí)也說(shuō)明了解決方法的未來(lái)發(fā)展方向。 14 參考文獻(xiàn) [1] Dir ac G A. Some theor ems on abstr act gr aphs[ J] .Pr oc Londo n Math Soc. 1952, 2: 69 81。 [2] Faudr ee R J, Go uld R J, Jacobson M S, et hoo d unio ns and highly Hamilton g r aphs[ J] . Ar s Combinato ria, 1991, 31: 139 148。 [3] 趙俊 , 宋序平 . 最小度與 Hamilton 連通圖 [ J] . 揚(yáng)州大學(xué)學(xué)報(bào) , 1995, 3: 39 45。 [4] 尹家洪 , 鄰集并與 hamiltonian 性 [ J] , 東南大學(xué)學(xué)報(bào) , 1991, 21 。 [5] 陳顯強(qiáng) , 吳集林 , 論哈密爾頓圖的判定問(wèn)題 ,科學(xué)技術(shù)與工程報(bào)， 2020 年第1 期 。 [6] 羅示豐 , 判別哈密爾頓圖的新方法 [J], 廣西科學(xué)院學(xué)報(bào) ,2020 年 2 月第十七卷第 1期。 [7] 趙克文 , 新的充分條件和哈密爾頓圖 [J], 中國(guó)工程科學(xué) , 2020 年 11 月第5 卷第 11 期 。 [8] Fan G H. New sufficient condit ions for cycles ing raphs [ J] . J Combin Theory Ser B 1984, 37: 221~227。 [9]于言坤 ，哈密爾頓圖的矩陣判定法，吉林教育學(xué)院學(xué)報(bào)（下旬 ）， [10]陳德欽、趙克文 , 哈密 爾 頓圖的鄰域交和鄰域并條件 , 科學(xué)技術(shù)與工程 , 2020 年 4 月第 6 卷第 8 期 。 [11]趙克文 , 曾克揚(yáng) , 一個(gè)充分條件和 Hamilton 連通圖 , 應(yīng)用科學(xué)學(xué)報(bào) ,2020 年 12 月第 21 卷 第 4 期 。 [12]趙克文 . 對(duì) 2 連通 n 階圖某些結(jié)果的改進(jìn) [ J] . 吉林大學(xué)自然科學(xué)學(xué)報(bào) , 2020, 1: 3946。 [13] Liqun Pua, HungLin Fub, Hao Shenc Maximal sets of Hamilton cycles in Dn[ J] scienceDirect 2020。 [14] B. Jackson, Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981) 145– 157。 [15]耿素云 , 屈婉玲 . 離散數(shù)學(xué)基礎(chǔ) , 北京大學(xué)出版社 , 1994 年 7 月第 1 版 。 [16]羅示豐 . 兩圖同構(gòu)的判別準(zhǔn)則及其復(fù)雜性 . 計(jì)算機(jī)科學(xué) , 1997, ( 10) 專輯 : 148～ 153。 [17]錢頌迪等 ,《 運(yùn)籌學(xué) 》 ,清華大學(xué)出版 社， 1990， 247～ 249。 [18]魏權(quán)齡等 , 《 運(yùn)籌學(xué)通論 》 ,中國(guó)人民大學(xué)出版社， 2020， 338— 343。 [19]徐俊明 , 《 圖論及其應(yīng)用 》 ,中國(guó)科技大學(xué)出版社， 1998， 52— 53。 [20]王樹禾 , 《 圖論及其算法 》 ,中國(guó)科技大學(xué)出版社， 1990， 64— 65。 [21]李修睦 , 《 圖論導(dǎo)引 》 ,華中工學(xué)院出版社， 1982， 107— 108。 [22] 盧開澄等 《 ,圖論及其應(yīng)用 》 ,清華大學(xué)出版社， 1995， 70— 77。 15 作者簡(jiǎn)歷 徐杰一村，男，出生與 1990 年 4月，浙江省寧波市余姚市人， 2020 年 9 月至 2020 年 6 月就讀于中國(guó)計(jì)量學(xué)院。在校期間，獲得社會(huì)工作獎(jiǎng)學(xué)金三次，校軍訓(xùn)積極分子，校亮點(diǎn)網(wǎng)優(yōu)秀部長(zhǎng)。 16 關(guān)鍵詞 * 密級(jí) * 中圖分類號(hào) * UDC 哈密爾頓圖 ； 判定方法 ； 貨郎擔(dān)問(wèn)題 公開 O157 62 論文贊助 學(xué)位授予單位 * 學(xué)位授予單位代碼 * 學(xué)位類別 * 學(xué)位級(jí)別 * 中國(guó)計(jì)量學(xué)院 10356 理學(xué) 學(xué)士 論文題名 * 哈密爾頓圖的判定及應(yīng)用 論文語(yǔ)種 * 并列題名 * 無(wú) 簡(jiǎn)體中文 作者姓名 * 徐杰一村 學(xué)號(hào) * 0900801110 培養(yǎng)單位名稱 * 培養(yǎng)單位代碼 * 培養(yǎng)單位 地址 郵編 中國(guó)計(jì)量學(xué)院 10356 浙江省杭州下沙高教園區(qū)學(xué)源街 310018 學(xué)科專業(yè) * 研究方向 * 學(xué)制 * 學(xué)位授予年 * 信息與計(jì)算科學(xué) 4 年 2020 論文提交日期 * 導(dǎo)師姓名 * 陳琴 職稱 * 講師 評(píng)閱人 答辯委員會(huì)主席 * 答辯委員會(huì)成員 電子版論文提交格式 文本（√ ）圖像（ ）視頻（ ）音頻（ ）多媒體（ ）其他（ ） 推薦格式： application/msword； application/pdf 電子版論文出版（發(fā)布者） 電子版論文出版（發(fā)布）地 權(quán)限聲明 論文總頁(yè)數(shù) * 23 注：共 33 項(xiàng)，其中帶“ *”為必填數(shù)據(jù)。