圖的哈密爾頓性

1、迷茫的旅行商 —— 圖的哈密爾頓性,,,1,一名旅行商要拜訪多個地點時，如何找到在拜訪每個地點一次后再回到起點的最短路徑？？,很難嗎？,不信你試試 ！即使就只有33個地方，瞎走的話也許真的要走上至少200年！,1、背景,(一)、哈密爾頓圖的概念,2,哈密爾頓(1805---1865), 愛爾蘭數(shù)學(xué)家。個人生活很不幸，但興趣廣泛：詩歌、光學(xué)、天文學(xué)和數(shù)學(xué)無所不能。他的主要貢獻是在代數(shù)領(lǐng)域，發(fā)現(xiàn)了四元數(shù)(第

2、一個非交換代數(shù))，他認為數(shù)學(xué)是最美麗的花朵。,哈密爾頓把該游戲以25英鎊的價格買給了J.Jacques and Sons公司 (該公司如今以制造國際象棋設(shè)備而著名) ，1859年獲得專利權(quán)。但商業(yè)運作失敗了。,該游戲促使人們思考點線連接的圖的結(jié)構(gòu)特征。這就是圖論歷史上著名的哈密爾頓問題。,3,2、哈密爾頓圖與哈密爾頓路,定義1 如果圖G的一個圈C含有G的所有頂點，則稱C為圖G的哈密爾頓圈, 簡稱哈圈或者H-圈。,定義2 如果圖G

3、的一條路P含有G的所有頂點，則稱P為圖G的哈密爾頓路, 簡稱哈路或者H-路。,定義3 如果圖G含有哈密爾頓圈，則稱G為哈密爾頓圖,例1、正十二面體是H圖。,例2 下圖G是非H圖。,(二)、性質(zhì)與判定,1、性質(zhì),定理1 (必要條件) 若G為H圖，則對V(G)的任一非空頂點子集S，有：,證明：設(shè)C是G的H圈，則對V(G)的任意非空子集S, 容易知道:,所以，有：,7,注：不等式為G是H圖的必要條件，即不等式不滿足時，可斷定對應(yīng)圖是

4、非H圖。,證明：取S=｛u, v, w｝,則有：,所以由定理1知，G為非H圖。,8,例3 求證右圖是非H圖。,注意：滿足定理1不等式的圖不一定是H圖。,彼得森(1839----1910)，丹麥哥本哈根大學(xué)數(shù)學(xué)教授。家境貧寒，因此而輟過學(xué)。但19歲就出版了關(guān)于對數(shù)的專著。他當(dāng)過中學(xué)教師，32歲獲哥本哈根大學(xué)數(shù)學(xué)博士學(xué)位，然后一直在該大學(xué)作數(shù)學(xué)教授。,9,例如：著名的彼德森圖是非H圖，但它滿足定理1的不等式。,彼得森是一位出色的名教師。他講

5、課遇到推理困難時，總是說：“這是顯而易見的”，并讓學(xué)生自己查閱他的著作。同時，他是一位有經(jīng)驗的作家，論述問題很形象，講究形式的優(yōu)雅。,1891年，彼得森發(fā)表了一篇奠定他圖論歷史地位的長達28頁的論文。這篇文章被公認是第一篇包含圖論基本結(jié)論的文章。同時也是第一次在文章中使用“圖”術(shù)語。,1898年，彼得森又發(fā)表了一篇只有3頁的論文，在這篇文章中，為舉反例構(gòu)造了著名的彼得森圖。,10,2、判定,圖的H性判定是NP-困難問題。到目前為止，有關(guān)

6、的定理有300多個，但沒有一個是理想的。拓展H圖的實用特征仍然被圖論領(lǐng)域認為是重大而沒有解決的問題。,圖的哈密爾頓問題和四色問題被謂為挑戰(zhàn)圖論領(lǐng)域150年智力極限的總和。三位數(shù)學(xué)“諾獎”獲得者ErdÖs、Whitney 、 Lovász 以及Dirac、Ore等在哈密爾頓問題上有過杰出貢獻。,下面，介紹一個著名的定理。,11,定理2 (充分條件) 對于n≧3的簡單圖G，如果G中有：,那么G是H圖。,證明:

7、 若不然，設(shè)G是一個滿足定理條件的極大非H簡單圖。顯然G不能是完全圖，否則，G是H圖。,于是，可以在G中任意取兩個不相鄰頂點u與v?？紤]圖G + u v，由G的極大性，G+u v是H圖。且G+u v的每一個H圈必然包含邊uv。,12,所以，在G中存在起點為u而終點為v的H路P。,不失一般性，設(shè)起點為u而終點為v的H路P為：,令：,13,對于S與T, 顯然，,另一方面：可以證明：,所以：,否則，設(shè),那么，由,由,這樣在G中有H圈，與假設(shè)

8、矛盾！,14,于是：,這與已知 矛盾！,注：該定理是數(shù)學(xué)家 Dirac在1952年得到的。該定理被認為是H問題的劃時代奠基性成果。,Dirac曾經(jīng)是丹麥奧爾胡斯大學(xué)知名教授，杰出的數(shù)學(xué)研究者。其父親(繼父)是在量子力學(xué)中做出卓越貢獻的物理學(xué)家狄拉克，1933年獲諾貝爾物理學(xué)獎。Dirac發(fā)表關(guān)于H問題論文39篇。他1952年的定理將永載史冊！,15,1960年，美國耶魯大學(xué)數(shù)學(xué)家Ore院士考察不相