哈密爾頓圖的判定及應(yīng)用畢業(yè)論文-資料下載頁
2025-07-27 06:07本頁面
【正文】 比較試用，一旦地點數(shù)量達到十個，那么我們的計算量將變的嚇人，甚至可以說是超過了人腦的計算能力，我們會感到十分的繁瑣。如果十個地點還可以勉強算出來，那么地點數(shù)量達到300個或者500個呢？那時候的計算量是我們無法想象的，而這種情況對于像中國這樣的大國來說，是非常現(xiàn)實的問題。這個時候我們就不得不借助計算機的力量。計算機到底可以提升多少的計算速度呢？一個例子能夠很好的說明問題：在美國工作的華籍數(shù)學(xué)家Lin Shen及Hong Saman等人在1977年的時候用電子計算器計算得到了一個有關(guān)于318個城市的貨郎擔問題。這個問題一旦化成線性規(guī)劃問題，那么就要處理有50403個變數(shù)的方程式及不等式，人腦對于這樣的問題雖然不能說完全不能解決，但是所需要的時間將是難以想象的。而當時的Lin Shen等人借助了一臺IBM的370—168式的電子計算機后，納悶對于電子技術(shù)日新月異的今天，我們可能需要的時間已經(jīng)不足一分鐘。兩者互相對比，讓我們不得不承認，以后的發(fā)展方向?qū)⒏嗟慕柚嬎銠C技術(shù)。 4 結(jié)論 哈密爾頓圖相可以應(yīng)用的范圍已經(jīng)越來越廣闊，從工業(yè)鋪路到農(nóng)業(yè)灌溉，航空路線到海底勘探，從國家的發(fā)展到公司的運輸，都可以用到哈密爾頓圖的知識。哈密爾頓圖的研究已經(jīng)顯得越來越重要，在效率第一的當今社會，恰當?shù)膽?yīng)用哈密爾頓圖的研究結(jié)果可以可以大大提高工作的效率和節(jié)約發(fā)展成本，為可持續(xù)發(fā)展提供不可或缺的支持。本文借鑒總結(jié)了大量前人的結(jié)論，著重介紹了哈密爾頓圖判定上的五種方法和結(jié)論，并初步對這五種方法的應(yīng)用范圍進行了分類。在哈密爾頓圖的應(yīng)用方面，著重介紹了貨郎擔問題的研究。在解決方法上又介紹了樹的搜索法，同時也說明了解決方法的未來發(fā)展方向。 參考文獻[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] . 揚州大學(xué)學(xué)報, 1995, 3: 39 45。[4] 尹家洪, 鄰集并與hamiltonian 性[ J] , 東南大學(xué)學(xué)報, 1991, 21 。[5] 陳顯強, 吳集林, 論哈密爾頓圖的判定問題,科學(xué)技術(shù)與工程報，2005 年第1 期。[6] 羅示豐, 判別哈密爾頓圖的新方法[J], 廣西科學(xué)院學(xué)報,2001年2月第十七卷第1期。[7] 趙克文, 新的充分條件和哈密爾頓圖[J], 中國工程科學(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é)報（下旬），[10]陳德欽、趙克文, 哈密爾頓圖的鄰域交和鄰域并條件, 科學(xué)技術(shù)與工程, 2006 年4 月第6 卷第8 期。[11]趙克文, 曾克揚, 一個充分條件和Hamilton 連通圖, 應(yīng)用科學(xué)學(xué)報,2003 年12 月第21 卷 第4 期。[12]趙克文. 對2 連通n 階圖某些結(jié)果的改進[ J] . 吉林大學(xué)自然科學(xué)學(xué)報, 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)的判別準則及其復(fù)雜性. 計算機科學(xué), 1997, ( 10) 專輯: 148～153。[17]錢頌迪等,《運籌學(xué)》,清華大學(xué)出版社，1990，247～249。[18]魏權(quán)齡等, 《運籌學(xué)通論》,中國人民大學(xué)出版社，2000，338—343。[19]徐俊明, 《圖論及其應(yīng)用》,中國科技大學(xué)出版社，1998，52—53。[20]王樹禾, 《圖論及其算法》,中國科技大學(xué)出版社，1990，64—65。[21]李修睦, 《圖論導(dǎo)引》,華中工學(xué)院出版社，1982，107—108。[22] 盧開澄等《,圖論及其應(yīng)用》,清華大學(xué)出版社，1995，70—77。作者簡歷徐杰一村，男，出生與1990年4月，浙江省寧波市余姚市人，2009年9月至2013年6月就讀于中國計量學(xué)院。在校期間，獲得社會工作獎學(xué)金三次，校軍訓(xùn)積極分子，校亮點網(wǎng)優(yōu)秀部長。 關(guān)鍵詞*密級*中圖分類號*UDC哈密爾頓圖；判定方法；貨郎擔問題公開O15762論文贊助學(xué)位授予單位*學(xué)位授予單位代碼*學(xué)位類別*學(xué)位級別*中國計量學(xué)院10356理學(xué)學(xué)士論文題名*哈密爾頓圖的判定及應(yīng)用論文語種*并列題名*無簡體中文作者姓名*徐杰一村學(xué)號*0900801110培養(yǎng)單位名稱*培養(yǎng)單位代碼*培養(yǎng)單位地址郵編中國計量學(xué)院10356浙江省杭州下沙高教園區(qū)學(xué)源街310018學(xué)科專業(yè)*研究方向*學(xué)制*學(xué)位授予年*信息與計算科學(xué)4年2013論文提交日期*導(dǎo)師姓名*陳琴職稱*講師評閱人答辯委員會主席*答辯委員會成員電子版論文提交格式 文本（√ ）圖像（ ）視頻（ ）音頻（ ）多媒體（ ）其他（ ）推薦格式：application/msword；application/pdf電子版論文出版（發(fā)布者）電子版論文出版（發(fā)布）地權(quán)限聲明論文總頁數(shù)*23注：共33項，其中帶“*”為必填數(shù)據(jù)。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1