哈密爾頓圖的判定及應(yīng)用畢業(yè)論文-資料下載頁(yè)
2025-07-27 06:07本頁(yè)面
【正文】 比較試用，一旦地點(diǎn)數(shù)量達(dá)到十個(gè)，那么我們的計(jì)算量將變的嚇人，甚至可以說(shuō)是超過(guò)了人腦的計(jì)算能力，我們會(huì)感到十分的繁瑣。如果十個(gè)地點(diǎn)還可以勉強(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ī)后，納悶對(duì)于電子技術(shù)日新月異的今天，我們可能需要的時(shí)間已經(jīng)不足一分鐘。兩者互相對(duì)比，讓我們不得不承認(rèn)，以后的發(fā)展方向?qū)⒏嗟慕柚?jì)算機(jī)技術(shù)。 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)行了分類(lèi)。在哈密爾頓圖的應(yīng)用方面，著重介紹了貨郎擔(dān)問(wèn)題的研究。在解決方法上又介紹了樹(shù)的搜索法，同時(shí)也說(shuō)明了解決方法的未來(lái)發(fā)展方向。 參考文獻(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)，2005 年第1 期。[6] 羅示豐, 判別哈密爾頓圖的新方法[J], 廣西科學(xué)院學(xué)報(bào),2001年2月第十七卷第1期。[7] 趙克文, 新的充分條件和哈密爾頓圖[J], 中國(guó)工程科學(xué), 2003 年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ù)與工程, 2006 年4 月第6 卷第8 期。[11]趙克文, 曾克揚(yáng), 一個(gè)充分條件和Hamilton 連通圖, 應(yīng)用科學(xué)學(xué)報(bào),2003 年12 月第21 卷 第4 期。[12]趙克文. 對(duì)2 連通n 階圖某些結(jié)果的改進(jìn)[ J] . 吉林大學(xué)自然科學(xué)學(xué)報(bào), 2001, 1: 3946。[13] Liqun Pua, HungLin Fub, Hao Shenc Maximal sets of Hamilton cycles in Dn[ J] scienceDirect 2008。[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) 專(zhuān)輯: 148～153。[17]錢(qián)頌迪等,《運(yùn)籌學(xué)》,清華大學(xué)出版社，1990，247～249。[18]魏權(quán)齡等, 《運(yùn)籌學(xué)通論》,中國(guó)人民大學(xué)出版社，2000，338—343。[19]徐俊明, 《圖論及其應(yīng)用》,中國(guó)科技大學(xué)出版社，1998，52—53。[20]王樹(shù)禾, 《圖論及其算法》,中國(guó)科技大學(xué)出版社，1990，64—65。[21]李修睦, 《圖論導(dǎo)引》,華中工學(xué)院出版社，1982，107—108。[22] 盧開(kāi)澄等《,圖論及其應(yīng)用》,清華大學(xué)出版社，1995，70—77。作者簡(jiǎn)歷徐杰一村，男，出生與1990年4月，浙江省寧波市余姚市人，2009年9月至2013年6月就讀于中國(guó)計(jì)量學(xué)院。在校期間，獲得社會(huì)工作獎(jiǎng)學(xué)金三次，校軍訓(xùn)積極分子，校亮點(diǎn)網(wǎng)優(yōu)秀部長(zhǎng)。 關(guān)鍵詞*密級(jí)*中圖分類(lèi)號(hào)*UDC哈密爾頓圖；判定方法；貨郎擔(dān)問(wèn)題公開(kāi)O15762論文贊助學(xué)位授予單位*學(xué)位授予單位代碼*學(xué)位類(lèi)別*學(xué)位級(jí)別*中國(guó)計(jì)量學(xué)院10356理學(xué)學(xué)士論文題名*哈密爾頓圖的判定及應(yīng)用論文語(yǔ)種*并列題名*無(wú)簡(jiǎn)體中文作者姓名*徐杰一村學(xué)號(hào)*0900801110培養(yǎng)單位名稱(chēng)*培養(yǎng)單位代碼*培養(yǎng)單位地址郵編中國(guó)計(jì)量學(xué)院10356浙江省杭州下沙高教園區(qū)學(xué)源街310018學(xué)科專(zhuān)業(yè)*研究方向*學(xué)制*學(xué)位授予年*信息與計(jì)算科學(xué)4年2013論文提交日期*導(dǎo)師姓名*陳琴職稱(chēng)*講師評(píng)閱人答辯委員會(huì)主席*答辯委員會(huì)成員電子版論文提交格式 文本（√ ）圖像（ ）視頻（ ）音頻（ ）多媒體（ ）其他（ ）推薦格式：application/msword；application/pdf電子版論文出版（發(fā)布者）電子版論文出版（發(fā)布）地權(quán)限聲明論文總頁(yè)數(shù)*23注：共33項(xiàng)，其中帶“*”為必填數(shù)據(jù)。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1