哈密爾頓圖的判定及應(yīng)用畢業(yè)論文(參考版)
2025-07-30 06:07本頁(yè)面
【正文】 。在校期間，獲得社會(huì)工作獎(jiǎng)學(xué)金三次，校軍訓(xùn)積極分子，校亮點(diǎn)網(wǎng)優(yōu)秀部長(zhǎng)。[22] 盧開澄等《,圖論及其應(yīng)用》,清華大學(xué)出版社，1995，70—77。[20]王樹禾, 《圖論及其算法》,中國(guó)科技大學(xué)出版社，1990，64—65。[18]魏權(quán)齡等, 《運(yùn)籌學(xué)通論》,中國(guó)人民大學(xué)出版社，2000，338—343。[16]羅示豐. 兩圖同構(gòu)的判別準(zhǔn)則及其復(fù)雜性. 計(jì)算機(jī)科學(xué), 1997, ( 10) 專輯: 148～153。[14] B. Jackson, Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981) 145–157。[12]趙克文. 對(duì)2 連通n 階圖某些結(jié)果的改進(jìn)[ J] . 吉林大學(xué)自然科學(xué)學(xué)報(bào), 2001, 1: 3946。[9]于言坤，哈密爾頓圖的矩陣判定法，吉林教育學(xué)院學(xué)報(bào)（下旬），[10]陳德欽、趙克文, 哈密爾頓圖的鄰域交和鄰域并條件, 科學(xué)技術(shù)與工程, 2006 年4 月第6 卷第8 期。[7] 趙克文, 新的充分條件和哈密爾頓圖[J], 中國(guó)工程科學(xué), 2003 年11 月第5 卷第11 期。[5] 陳顯強(qiáng), 吳集林, 論哈密爾頓圖的判定問題,科學(xué)技術(shù)與工程報(bào)，2005 年第1 期。[3] 趙俊, 宋序平. 最小度與Hamilton 連通圖[ J] . 揚(yáng)州大學(xué)學(xué)報(bào), 1995, 3: 39 45。 參考文獻(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。在哈密爾頓圖的應(yīng)用方面，著重介紹了貨郎擔(dān)問題的研究。哈密爾頓圖的研究已經(jīng)顯得越來(lái)越重要，在效率第一的當(dāng)今社會(huì)，恰當(dāng)?shù)膽?yīng)用哈密爾頓圖的研究結(jié)果可以可以大大提高工作的效率和節(jié)約發(fā)展成本，為可持續(xù)發(fā)展提供不可或缺的支持。兩者互相對(duì)比，讓我們不得不承認(rèn)，以后的發(fā)展方向?qū)⒏嗟慕柚?jì)算機(jī)技術(shù)。這個(gè)問題一旦化成線性規(guī)劃問題，那么就要處理有50403個(gè)變數(shù)的方程式及不等式，人腦對(duì)于這樣的問題雖然不能說(shuō)完全不能解決，但是所需要的時(shí)間將是難以想象的。這個(gè)時(shí)候我們就不得不借助計(jì)算機(jī)的力量。在上面方法展示的過程中我們可以發(fā)現(xiàn)，這樣的搜索方法在地點(diǎn)數(shù)量較少的時(shí)候還比較試用，一旦地點(diǎn)數(shù)量達(dá)到十個(gè)，那么我們的計(jì)算量將變的嚇人，甚至可以說(shuō)是超過了人腦的計(jì)算能力，我們會(huì)感到十分的繁瑣。比如當(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ù)值。由此我們得到了在五個(gè)城市之間銷售的最佳路線。見圖35。圖34：樹的搜索法第二步根據(jù)上述法則繼續(xù)推廣，就可以知道，假設(shè)是ABC的路徑，那么到達(dá)C城以后，就只剩下了兩種可能路徑：ABCDEA和ABCEDA，于是我們劃掉節(jié)點(diǎn)ABC（30），得到兩個(gè)新的節(jié)點(diǎn)ABCDEA（180）和ABCEDA（190）。圖33：樹的搜索法第一步現(xiàn)在我們可以看到由城市B可能到達(dá)的城市有C、D、E，把節(jié)點(diǎn)AB（10）劃掉，我們可以得到三個(gè)新的節(jié)點(diǎn)ABC（10+20）、ABD（10+50）、ABE（10+60）后面的50、60分別表示BC、BD、BE的長(zhǎng)度，以此類推我們還可以得到的新節(jié)點(diǎn)有ACB(40)、ACD(70)、ACE(100)、ADB(100)、ADC(100)、ADE(80)、AEB(130)、AEC(150)、AED(100)九個(gè)節(jié)點(diǎn)。A、B、C、D、E五座城市之間的距離由下表進(jìn)行表出：表31：五個(gè)城市之間的距離表ABCDB10C2020D505050E70608030圖32：五個(gè)城市之間的連通情況我們選擇從點(diǎn)A出發(fā)，先寫A（0），0表示最初沒有出發(fā)路線是的路程長(zhǎng)度是0，然后我們可以列出下一步可能到達(dá)的城市，分別由B、C、D、E，可以得到四個(gè)節(jié)點(diǎn)為AB（10）、AC（20）、AD（50）、AE（70）。圖31：西德120個(gè)城市最短路線圖那么在一般情況下我們可以借用什么方法來(lái)解決貨郎擔(dān)問題呢？在這里介紹一種較為簡(jiǎn)單的方法樹的搜索法。他費(fèi)盡心血從鐵路局找到了準(zhǔn)確的城市間鐵路的長(zhǎng)度，把整個(gè)問題變成了一個(gè)有7140個(gè)變數(shù)，120個(gè)方程及96個(gè)不等式的線性規(guī)劃問題，人類的大腦已經(jīng)對(duì)這樣的問題表示無(wú)能為力了，最后不得不用電子計(jì)算機(jī)去算，才得到了最短的回路是6942公里。雖然這個(gè)方法還未應(yīng)用到貨郎擔(dān)問題的解決上，但是卻也堅(jiān)定了很多人繼續(xù)往這個(gè)方向研究的信心，在不久的將來(lái)這個(gè)問題一定可以獲得更大的突破。1979年11月7日《紐約時(shí)報(bào)》上出現(xiàn)了一篇很有影響力的文章，它的標(biāo)題為《蘇聯(lián)的發(fā)現(xiàn)震動(dòng)數(shù)學(xué)界》，這篇文章雖然有一定的夸大成分存在，但是他所說(shuō)的把貨郎擔(dān)問題的解決和計(jì)算機(jī)聯(lián)系起來(lái)的思想確實(shí)沒有錯(cuò)的。美國(guó)的《管理科學(xué)》中有一篇討論“貨郎擔(dān)問題”的文章，該文中提到：人類由于他的計(jì)算能力的限制，在解決貨郎擔(dān)問題上并不好。所以貨郎擔(dān)問題的研究是與生活直接相關(guān)的，是非常具有現(xiàn)實(shí)意義的。為公司創(chuàng)造更多的利潤(rùn)。（3）再假設(shè)當(dāng)我們出差坐飛機(jī)時(shí)，由于各地的情況不同導(dǎo)致各個(gè)地方之間的價(jià)格會(huì)不一樣。因?yàn)樯钪行枰龅截浝蓳?dān)問題的地方實(shí)在是太多了，例如：（1）當(dāng)我們外出旅游的時(shí)候，提前安排好路程最短的路線，不僅可以節(jié)省交通上的成本，還可以得到更多的時(shí)間來(lái)參觀。將上述的問題進(jìn)行數(shù)學(xué)提煉后所求的問題可以轉(zhuǎn)化為，在一個(gè)加附了權(quán)值的完全圖中，尋找一個(gè)權(quán)值最小的哈密爾頓回路。蒙那哥在1932年提出來(lái)的，80年來(lái)一直是哈密爾頓圖的應(yīng)用中的最典型的例子，無(wú)數(shù)人對(duì)其進(jìn)行廢寢忘食的研究。相信在不久的將來(lái)會(huì)有一種簡(jiǎn)單的方法可以幫助我們得出結(jié)論。然而簡(jiǎn)單觀察后就可以發(fā)現(xiàn)圖G4是一個(gè)哈密爾頓圖，所以博薩定理和薩瓦達(dá)定理是有一定的缺陷的。薩瓦達(dá)定理也對(duì)這個(gè)問題表示無(wú)能為力，在圖G4中n=8，所以小于n/2的正整數(shù)i=3。然而博薩定理和薩瓦達(dá)定理同樣是不完善的，這一點(diǎn)圖G4給我們作出了很好的例子。同樣也可以根據(jù)薩瓦達(dá)定理來(lái)進(jìn)行判定，因?yàn)閚=5，所以小于n/2的i有i=2。這個(gè)時(shí)候我們就可以用博薩定理進(jìn)行判定。同樣使用奧勒定理時(shí)min
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1