圖的哈密爾頓性_第1頁
已閱讀1頁,還剩16頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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

2、一個非交換代數),他認為數學是最美麗的花朵。,哈密爾頓把該游戲以25英鎊的價格買給了J.Jacques and Sons公司 (該公司如今以制造國際象棋設備而著名) ,1859年獲得專利權。但商業(yè)運作失敗了。,該游戲促使人們思考點線連接的圖的結構特征。這就是圖論歷史上著名的哈密爾頓問題。,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圖。,(二)、性質與判定,1、性質,定理1 (必要條件) 若G為H圖,則對V(G)的任一非空頂點子集S,有:,證明:設C是G的H圈,則對V(G)的任意非空子集S, 容易知道:,所以,有:,7,注:不等式為G是H圖的必要條件,即不等式不滿足時,可斷定對應圖是

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

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

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

7、 若不然,設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。,不失一般性,設起點為u而終點為v的H路P為:,令:,13,對于S與T, 顯然,,另一方面:可以證明:,所以:,否則,設,那么,由,由,這樣在G中有H圈,與假設

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論