從哈密爾頓圖到旅行貨郎問題

1、從哈密爾頓圖到旅行貨郎問題197年911月7日紐約時(shí)報(bào)出現(xiàn)一篇引人注目的文章，它的標(biāo)題是：蘇聯(lián)的發(fā)現(xiàn)震動(dòng)數(shù)學(xué)界（），這文章介紹一個(gè)本是默默無聞的年青數(shù)學(xué)家卡倩（h，他在線性規(guī)劃理論上的一個(gè)發(fā)現(xiàn)使到美國數(shù)學(xué)界為之轟動(dòng)。由于記者在詢問一些著名數(shù)學(xué)家時(shí)對(duì)數(shù)學(xué)問題了解不深，文章報(bào)導(dǎo)是有一些失實(shí)，但由這文章引起的轟動(dòng)及誤導(dǎo)是相當(dāng)嚴(yán)重。我以后會(huì)討論這問題。該文中說：“俄國人的發(fā)現(xiàn)建議用電子計(jì)算機(jī)處理一類和旅行貨郎問題C）有關(guān)的數(shù)學(xué)上一個(gè)著名及難處理的問題。旅行貨朗問題目的是決定一個(gè)貨郎（或推銷員或銷貨員）所要跑的最短路程他要走遍市鎮(zhèn)，但是不能再回到走過的地方。表面上，這問題看來簡單，事實(shí)上為了要解決這問題

2、的實(shí)際應(yīng)用，人們需要電子計(jì)算機(jī)來解決?！痹谶@點(diǎn)上這記者是說對(duì)了?！奥眯胸浝蓡栴}”目前是許多國家（如西德、日本、蘇聯(lián)、英國、美國、法國）的運(yùn)籌學(xué)工作者研究的熱烈課題。為了要了解這問題，我們可要知道目前在圖論（）上許多人正在研究一種圖哈密爾頓圖（P。一、哈密爾頓圖的由來在1718世紀(jì)時(shí)，歐洲宮庭及一些貴族很喜歡玩西洋象棋，西洋象棋中的騎士Cg是對(duì)應(yīng)我們中國象棋的“馬”，而它通常是刻成一個(gè)馬頭，跑法也是和中國象棋的“馬”一樣，走“日”線即從日的一角沿著對(duì)角線躍到另一角。在年，就有一位名叫范德蒙C）的法國數(shù)學(xué)家，寫了一篇文章研究所謂“棋盤的騎士問題”。這問題是這樣：在X的棋盤格的隨意一個(gè)位置，我放一個(gè)

3、騎士，然后我想法子使他跑遍棋盤的所有的格子，走過的不許再走，我能不能使騎士最后回到原來的位置？這個(gè)問題并不簡單，許多象棋愛好者及數(shù)學(xué)家曾坐下來研究這個(gè)問題。我這里列出一個(gè)情形的解（見圖一），我將棋盤的左下角的格選為起始位置，把它定為，讀者可以驗(yàn)證根據(jù)圖一的跑法，騎士最后是能跑回1的。圖一“棋盤騎士問題”的一個(gè)解法世紀(jì)的大數(shù)學(xué)家歐拉（），在年就系統(tǒng)地研究過這個(gè)問題，也得到了一些結(jié)果。以后德國數(shù)學(xué)家高斯也曾對(duì)這問題發(fā)生興趣，花過一些時(shí)間研究它及另外一個(gè)棋盤的“皇后問題”。我們現(xiàn)在把棋盤上的格子對(duì)應(yīng)在一個(gè)平面上的一個(gè)小圓點(diǎn)，這樣我們?cè)谄矫嫔暇陀?4個(gè)小圓點(diǎn)。從一個(gè)格子用騎士的走法我們可以抵達(dá)不同數(shù)目

4、的格子：如果是處在棋盤的四個(gè)角，只能有兩種跑法；在其他邊緣的格子就有三種跑法；一般當(dāng)中的格子，就有四種可能的跑法。我們把平面上的點(diǎn)用弧線連接，兩個(gè)點(diǎn)有一條弧線連起當(dāng)且僅當(dāng)（TOC o 1-5 h zy我們可以從它們所對(duì)應(yīng)的格子將騎士移動(dòng)。我們得到了一個(gè)圖（）。在圖中取一個(gè)頂點(diǎn)，如果我們有一個(gè)弧線把它和另外一個(gè)點(diǎn)聯(lián)起來，我們就用01（，）來表示這個(gè)弧線。假定我有一系列點(diǎn)，其中沒有兩個(gè)相同以01012n及一序列的弧線存在（0），（，），（，），（，），使到我從出發(fā)可以經(jīng)過，最后由回到，我就說這些弧線組成一個(gè)回路（）u12nn0為了方便，我們用下面的記號(hào)表示這回路：（，1，）。如果我有一個(gè)圖有個(gè)頂點(diǎn)

5、（），,而我能找到一012n個(gè)回路（，），那么我就說這個(gè)圖是哈密爾頓圖（n012n0這個(gè)回路稱為哈密爾頓回路（）。因此，“棋盤的騎士問題”實(shí)際上就是要判斷它所對(duì)應(yīng)的圖是否是哈密爾頓圖的問題。為什么叫哈密爾頓圖？哈密爾頓是誰呢？哈密爾頓是愛爾蘭的一位數(shù)學(xué)家和天文學(xué)家。他的一生是多姿多彩的，我在數(shù)學(xué)和數(shù)學(xué)家的故事第一集里有詳細(xì)介紹他的工作和生平，讀者可以找來一讀。自從哈密爾頓發(fā)現(xiàn)“四元數(shù)”之后，他又發(fā)現(xiàn)了另外一種他命名為“”的代數(shù)系統(tǒng)，這系統(tǒng)有加和乘的運(yùn)算子（），可是乘法不滿足交換律（即這個(gè)規(guī)律）。他發(fā)現(xiàn)這代數(shù)系統(tǒng)是和正則面體（）有關(guān)系。他想到一個(gè)游戲，怎樣跑遍正則多面體上的所有頂點(diǎn)，而最后又能回

6、到起點(diǎn)的問題。在185年他把這個(gè)游戲的想法以25英鎊的價(jià)錢賣給一位玩具和游戲制造商。這25英鎊在12年前是很好用，在今天拿去倫敦的“唐人區(qū)”買“牛腩面”吃可能連十碗都吃不到。這玩具商把這游戲制造出來了（見圖二），在圓盤上有20個(gè)代表城市的圓孔，你必須把個(gè)上面標(biāo)有，的木條順序插進(jìn)去，代表你經(jīng)過不同的城市，最后回到原出發(fā)點(diǎn)。這個(gè)游戲叫“環(huán)游世界”，很可惜玩具商人沒有從這游戲上賺到錢。以后人們因這游戲就稱這類圖為哈密爾頓圖。二、怎么樣的圖是哈密爾頓圖給你一個(gè)圖，你怎么知道它是否是哈密爾頓圖呢？當(dāng)然如果圖的頂點(diǎn)不多，你可以試試找哈密爾頓回路就可以解決和判斷。你用的是最古老的“嘗試和錯(cuò)誤”的方法，但是數(shù)

7、學(xué)家并不滿意這樣的碰得焦頭爛額后才找到真理的方法。是否存在一組必要和充分的條件，使到我們能簡單輕易地判斷一個(gè)圖是否哈密爾頓圖？許多聰明人去試過了，很可惜到現(xiàn)在這問題還未解決，因此讀者可以試試自己來找尋一下。英國數(shù)學(xué)家.狄拉克（）在年給出一個(gè)充分條件使得一個(gè)圖會(huì)是哈密爾頓圖。他的定理是只要檢查每一個(gè)頂點(diǎn)，看它的上面有多少個(gè)弧通過，把這個(gè)數(shù)目用l）來表示，只要每一個(gè)點(diǎn)的l）是相當(dāng)大的話，這圖就會(huì)是哈密爾頓圖。狄拉克定理給定一個(gè)圖G如果其頂點(diǎn)集的元素?cái)?shù)是三3而且d（笈）-11,那么G一定是哈密爾頓圖。由于我們可以看到以下的兩個(gè)圖，都是哈密爾頓圖（見圖三）。4在G中，每個(gè)點(diǎn)宣有aCQ=3,明顯33萬。

8、在三中，每個(gè)點(diǎn)有a3）到了年，美國著名的圖論專家奧斯坦奧勒（i推廣狄拉克的工作，得到以下的結(jié)果。奧勒定理給定一個(gè)圖，如果其頂點(diǎn)集是有三點(diǎn)，而對(duì)于任意兩點(diǎn)，我們有I）（）三，那么一定是哈密爾頓圖。在196年2，匈牙利有一個(gè)少年發(fā)表了一篇只有一頁長的論文，他的結(jié)果卻是推廣了以上奧勒的定理，他的工作是這么重要引起許多人談?wù)?，并且在圖論的教科書上登他的證明。以后幾年來許多人想要改進(jìn)這工作，最后才由一個(gè)捷克青年數(shù)學(xué)家得到比他更好的結(jié)果。這個(gè)少年名叫博薩（），我在數(shù)學(xué)和數(shù)學(xué)家的故事第一集的一篇文章就有介紹他的事跡，讀者想要知道他的故事可以看看該文。為了能更容易看清博薩的結(jié)果，我這里引進(jìn)幾個(gè)記號(hào)：對(duì)于每一個(gè)

9、圖G我們用（）來表示序列如（），（），（）,這里，是的所有頂點(diǎn)，而序列的數(shù)是從小排到大去排列。比方說在圖三里我們有d（G）=（3，3，3，3）假定我們有兩個(gè)序列具有相同個(gè)數(shù)的數(shù)字：我們用W表示當(dāng)且僅當(dāng)對(duì)于每個(gè)我們都有比方說，我們就有W,而W是不對(duì)的。現(xiàn)在對(duì)于每個(gè)三的整數(shù)，我們定義這樣的整數(shù)序列（）（）如果是偶數(shù)，我們有個(gè)數(shù)照底下由小到大的排法：P1口）=（2,3,4，5,）2,（）如果是奇數(shù)，我們有個(gè)數(shù)照底下的由小到大的排法:PGO=（2,3,4,5,，亍瞪，展，11-1n+1n+1n+12，2，2，2）根據(jù)定義我們有P（3）=（1，2，2），（4）=（2，2，2，2），（5）=（2，2，3，

10、3，3），（6）=（2，3，3，3，3，3）以及（7）=（2，3，3，4，4，4，4）讀者請(qǐng)注意我們是怎樣定義這序列現(xiàn)在我們可以敘述博薩的重要發(fā)現(xiàn)：博薩定理如果一個(gè)有三個(gè)頂點(diǎn)的圖，它的（）滿足不等式那么是哈密爾頓圖。讓我們看以下的圖四（）及（），讀者很容易地看出（G）=（2，2，3，3，4），（G）=（3，3，3，3，3，3，3，3）。它們都是哈密爾頓圖。不滿足奧勒的條件，因?yàn)椋ǎ?y)并=不4大過可是我們卻看到（）（2233）三（2233）（）因此由博薩定理知道它是哈密爾頓圖。由這個(gè)例子說明了博薩的結(jié)果是比奧勒的強(qiáng)。然而我們卻由看到它并不滿足博薩的不等式。因此人們嘗試想找比博薩更好的不等式以

11、判別更多的哈密爾頓圖。到目前來說，比較好的工作是捷克青年數(shù)學(xué)家薩瓦達(dá)（d）在年的發(fā)現(xiàn)，他的結(jié)果如下：薩瓦達(dá)定理如果圖的頂點(diǎn)數(shù)是大過，而其（）（，n滿足底下的條件：對(duì)于每個(gè)小于2的正整數(shù)1,兩個(gè)不等式2三，三最少有一個(gè)成立，那in-i么一定是哈密爾頓圖。對(duì)數(shù)學(xué)有興趣的讀者可以試證明博薩的結(jié)果是包含在薩瓦達(dá)定理。我們的圖顯示它不滿足薩瓦達(dá)的條件，因此我們相信會(huì)存在比薩瓦達(dá)還要好的條件，這個(gè)問題就留給讀者自己去尋找。三、旅行貨郎問題如果我現(xiàn)在有一個(gè)圖G而這圖的每一條弧上都算上一個(gè)數(shù)字，我要怎樣才能找到這圖的哈密頓回路具有所有的弧上數(shù)字的和是最小值的性質(zhì)，這個(gè)問題就是數(shù)學(xué)上大名鼎鼎的難題：“旅行貨郎問

12、題”。這問題在年由德國著名數(shù)學(xué)家.提出，這年來是許多人廢寢忘食研究的對(duì)象。我們?cè)谌粘Ｉ钪芯蜁?huì)遇到這問題，比方說：（1）你是學(xué)校校車的司機(jī)，你從學(xué)校開車出來，到不同的街道去接孩子，你要怎樣安排使走的路程最短，可以接到所有的孩子回到學(xué)校去？（2）春假到了，你想駕車在北美幾個(gè)城市旅行，可是現(xiàn)在汽油是這么昂貴，你想要盡量省用油，汽油的消耗是和路程成正比，因此你想法子找一個(gè)回路具有最短的路程。（3）你為了商業(yè)業(yè)務(wù)，需要乘飛機(jī)飛幾個(gè)城市，不同的飛機(jī)公司提供不同的票價(jià)，你要怎樣安排行程，使到你能走遍你要去的城市，最后又回來原出發(fā)地，而又能省錢？“旅行貨郎問題”是這么容易明白，可是要找出一個(gè)行之有效及能迅速

13、提供解答的方法，目前并不存在。在年前，美國的管理科學(xué)（）一篇討論“旅行貨郎問題”的文章就說道：“人類由于他的運(yùn)算能力的限制在解決旅行貨郎問題上并不好?！比藗儸F(xiàn)在對(duì)于這問題的實(shí)際情形都是借助高速的電子計(jì)算機(jī)來運(yùn)我在以下會(huì)介紹一種直觀而又容易明白的樹的搜索法來尋找最優(yōu)解，目前解“旅行貨郎問題”有很多種方法，由于大部分要牽涉到較深的數(shù)學(xué)知識(shí)，因此我不在這里介紹。我最后會(huì)通過例子說明為什么這個(gè)看來小學(xué)生都能明白的問題卻是數(shù)學(xué)難題。德國人很喜歡精確的數(shù)學(xué)，在197年8，波恩大學(xué)有一位數(shù)學(xué)家想要知道在西德的12個(gè)0有鐵路穿過的城市要安排一個(gè)最短路程的回路，應(yīng)該怎么樣跑。他從鐵路局找到了準(zhǔn)確的城市間鐵路的長

14、度，整個(gè)問題變成一個(gè)有714個(gè)0變數(shù)，12個(gè)0方程及96個(gè)不等式的線性規(guī)劃問題，用電子計(jì)算機(jī)去算得到最短的回路是694公2里。（見圖五）。我這里舉一個(gè)例子說明這個(gè)方法，假定我現(xiàn)在有四個(gè)城市ABCD它們之間的路程是由下面的表給出（見圖六）：我要找從出發(fā)回到的最短回路。我從出發(fā)，我寫：（）0是表示最初沒有出發(fā)路線長是0然后我列下所有可能的下一個(gè)站：BCD然后我得到三個(gè)節(jié)點(diǎn)I）：（）,（）,（）這時(shí)我就把I）劃掉，然后找節(jié)點(diǎn)具有最小的數(shù)值，這里是（）。從我可以走的站是和）我就劃掉（）1用（旁的數(shù)字是呢？因?yàn)樗牵ǎ┘埃ǎ﹣砣〈槭裁矗ǎ┘由希ǎ┑拈L。（見圖七）。）我們把沒劃掉的節(jié)點(diǎn)中有最小長度的找

15、出，這是（）的下一個(gè)可能的站是和，因此我們劃掉（）補(bǔ)上兩個(gè)節(jié)點(diǎn)（）及（）+我們繼續(xù)找具有最小長度的節(jié)點(diǎn)，這時(shí)看到是（）從出發(fā)可以到達(dá)或D于是我們劃掉I）3補(bǔ)上I）+（）+（見圖七（）我們?cè)偎阉饔凶钚￠L度的節(jié)點(diǎn)，看到是（）5于是劃掉它，補(bǔ)上（）,得圖七（）。我們?cè)偎阉鳑]有被劃的節(jié)點(diǎn)，看到有最小長度的是（）及（）7我就先劃掉（）補(bǔ)上（）,得圖七（）。然后我再劃掉（）補(bǔ)上（）得圖七（）。這時(shí)候我看剩下沒劃線的最小長度的節(jié)點(diǎn)是：（）及（）8我劃掉了比方說（）8補(bǔ)上（）+我再尋找最小長度的節(jié)點(diǎn)得（）8劃掉之后補(bǔ)上Y（）,得圖七（）?，F(xiàn)在變成（）是最小長度的節(jié)點(diǎn)，我們劃掉補(bǔ)上（）,得圖七（），我們劃去（）

16、的最小長度節(jié)點(diǎn)（），補(bǔ)上（）。我們已得到一個(gè)回路了，這時(shí)我們把（1）圖中所有長度大過12，節(jié)點(diǎn)全劃掉，因?yàn)檫@些節(jié)點(diǎn)所產(chǎn)生的回路肯定要大過，我們可以不考慮，我們只剩下（）1劃掉它之后補(bǔ)上（），我們得（）。謝天謝地，到此時(shí)我們?cè)贈(zèng)]有什么節(jié)點(diǎn)可以劃了，我們得到兩個(gè)回路（）及（）B它們的長都是2這種方法在數(shù)學(xué)上有一個(gè)名稱叫。為了說明整個(gè)搜索的程序，我畫了許多像樹枝分叉的圖，實(shí)際上讀者只需在一個(gè)圖上劃線及向下發(fā)展不必畫這么多樹。通常哈密爾頓回路找到之后，我們選取最少的長度，那就是我們所要的答案。五、為什么數(shù)學(xué)家和電腦專家對(duì)貨郎問題發(fā)生興趣我們前面介紹的方法在城市數(shù)目字比方說不超過十個(gè)還不顯得可怕。如果現(xiàn)

17、在有21個(gè)城市用以上的方法去搜索最短的回路，我們最少要找超過九十萬個(gè)以上的路線，這是多么巨大的數(shù)字呀！現(xiàn)在請(qǐng)想一想，如果我們要處理的是五百個(gè)城市，或者一千個(gè)城市，或者就拿像中國這么大的國家，這么多的縣城，要處理這問題，用目前最快速的電子計(jì)算機(jī)來協(xié)助，也會(huì)使電子計(jì)算機(jī)掛投降的白旗，宣稱：“我的記憶不夠處理這些問題產(chǎn)生出來的數(shù)值，對(duì)不起哥哥，我不能替你效勞?！蔽仪懊娼榻B的樹的搜索法是一個(gè)比較簡單但并不是太好的方法，這20年來，許多人想出一些方法想要改進(jìn)，希望能找到一個(gè)較理想的方法，可以快速的找到結(jié)果。目前來說這樣理想的方法還沒有找到。什么樣的方法算是理想呢？我們這里給一個(gè)粗略的解釋：比方說我們要用

18、電子計(jì)算機(jī)來幫我們工作，例如處理個(gè)城市的旅行貨郎問題，當(dāng)我把個(gè)城市的距離表喂給電子計(jì)算機(jī)之后，它就會(huì)一步一步的去找。如果它要得到答案，所要花費(fèi)的步驟數(shù)目是可以用的函數(shù)（）來表示。我們說這方法是“理想”，當(dāng)（）是一個(gè)的多項(xiàng)式。目前我們的方法都不是理想的。如果你真能找到一個(gè)理想的方法，你的成果會(huì)轟動(dòng)全世界。你的方法可以轉(zhuǎn)化用來解決許多數(shù)學(xué)的難題及電子計(jì)算機(jī)理論的一些著名難題。旅行貨郎問題是許多國家的運(yùn)籌學(xué)研究中心的工作者深入研究的問題。在美國的華籍?dāng)?shù)學(xué)工作者在這方面有很好的結(jié)果的有及等人。在年先生和合作用電子計(jì)算機(jī)處理有個(gè)城市的“旅行貨郎問題”，這個(gè)問題化成線性規(guī)劃問題就要處理有個(gè)變數(shù)（）的方程式，及不等式，如果不借助電子計(jì)算機(jī)的快速計(jì)算，我想就是請(qǐng)一位能筆算及心算很快的數(shù)學(xué)家，讓他窮十年的時(shí)間也是不能解決。以上的問題他們用式的電子計(jì)算機(jī)，只花分鐘就得到一個(gè)最優(yōu)解?！巴嫖飭手尽保@是以前老一輩的人罵兒童或少年不讀書只喜歡游戲所愛用的一句話。其實(shí)游戲和玩具可以引導(dǎo)大發(fā)現(xiàn)。如果有青少年肯對(duì)哈密爾頓圖及旅行貨郎問題下點(diǎn)苦功研究，我會(huì)說他們是“玩物立志”，很可能以后會(huì)出一些在這些問題上作出大貢獻(xiàn)的中國人。六、動(dòng)腦筋想想看：尋找下面幾個(gè)圖的哈密爾頓回路：2在下面的X方格里，如果我在最左上角放一只馬，然后讓馬依