1、1,圖論及其應用,應用數(shù)學學院,2,本次課主要內容,(一)、哈密爾頓圖的概念,(二)、性質與判定,哈密爾頓圖,3,1、背景,(一)、哈密爾頓圖的概念,1857年， 哈密爾頓發(fā)明了一個游戲(Icosian Game).它是由一個木制的正十二面體構成，在它的每個棱角處標有當時很有名的城市。游戲目的是“環(huán)球旅行”。為了容易記住被旅游過的城市 ，在每個棱角上放上一個釘子，再用一根線繞在那些旅游過的城市上(釘子),由此可以獲得旅程的直觀表示。,4,哈密爾頓(1805-1865),愛爾蘭數(shù)學家。個人生活很不幸，但興趣廣泛：詩歌、光學、天文學和數(shù)學無所不能。他的主要貢獻是在代數(shù)領域，發(fā)現(xiàn)了四元數(shù)(第一個非交

2、換代數(shù))，他認為數(shù)學是最美麗的花朵。,哈密爾頓把該游戲以25英鎊的價格買給了J.Jacques and Sons公司 (該公司如今以制造國際象棋設備而著名) ，1859年獲得專利權。但商業(yè)運作失敗了。,該游戲促使人們思考點線連接的圖的結構特征。這就是圖論歷史上著名的哈密爾頓問題。,2、哈密爾頓圖與哈密爾頓路,定義1 如果經(jīng)過圖G的每個頂點恰好一次后能夠回到出發(fā)點，稱這樣的圖為哈密爾頓圖，簡稱H圖。所經(jīng)過的閉途徑是G的一個生成圈，稱為G的哈密爾頓圈。,5,例1、正十二面體是H圖。,6,例2 下圖G是非H圖。,證明：因為在G中，邊uv是割邊，所以它不在G的任意圈上，于是u與v不能在G的同一個圈上。

3、故G不存在包括所有頂點的圈，即G是非H圖。,定義2 如果存在經(jīng)過G的每個頂點恰好一次的路，稱該路為G的哈密爾頓路，簡稱H路。,7,(二)、性質與判定,1、性質,定理1 (必要條件) 若G為H圖，則對V(G)的任一非空頂點子集S，有：,證明：G是H圖，設C是G的H圈。則對V(G)的任意非空子集S, 容易知道:,所以，有：,8,注：不等式為G是H圖的必要條件，即不等式不滿足時，可斷定對應圖是非H圖。,例3 求證下圖是非H圖。,證明：取S=2, 7, 6,則有：,所以由定理1知，G為非H圖。,9,注意：滿足定理1不等式的圖不一定是H圖。,例如：著名的彼德森圖是非H圖，但它滿足定理1的不等式。,彼得森

4、(1839-1910)，丹麥哥本哈根大學數(shù)學教授。家境貧寒，因此而輟過學。但19歲就出版了關于對數(shù)的專著。他作過中學教師，32歲獲哥本哈根大學數(shù)學博士學位，然后一直在該大學作數(shù)學教授。,10,彼得森是一位出色的名教師。他講課遇到推理困難時，總是說：“這是顯而易見的”，并讓學生自己查閱他的著作。同時，他是一位有經(jīng)驗的作家，論述問題很形象，講究形式的優(yōu)雅。,1891年，彼得森發(fā)表了一篇奠定他圖論歷史地位的長達28頁的論文。這篇文章被公認是第一篇包含圖論基本結論的文章。同時也是第一次在文章中使用“圖”術語。,1898年，彼得森又發(fā)表了一篇只有3頁的論文，在這篇文章中，為舉反例構造了著名的彼得森圖。,

5、11,2、判定,圖的H性判定是NP-困難問題。到目前為止，有關的定理有300多個，但沒有一個是理想的。拓展H圖的實用特征仍然被圖論領域認為是重大而沒有解決的問題。,圖的哈密爾頓問題和四色問題被謂為挑戰(zhàn)圖論領域150年智力極限的總和。三位數(shù)學“諾獎”獲得者Erds、Whitney 、 Lovsz 以及Dirac、Ore等在哈密爾頓問題上有過杰出貢獻。,下面，介紹幾個著名的定理。,12,定理2 (充分條件) 對于n3的單圖G，如果G中有：,那么G是H圖。,證明: 若不然，設G是一個滿足定理條件的極大非H簡單圖。顯然G不能是完全圖，否則，G是H圖。,于是，可以在G中任意取兩個不相鄰頂點u與v?？紤]圖

6、G + u v，由G的極大性，G+ u v是H圖。且G+ u v的每一個H圈必然包含邊u v。,13,所以，在G中存在起點為u而終點為v的H路P。,不失一般性，設起點為u而終點為v的H路P為：,令：,14,對于S與T, 顯然，,另一方面：可以證明：,所以：,否則，設,那么，由,由,這樣在G中有H圈，與假設矛盾！,15,于是：,這與已知 矛盾！,注：該定理是數(shù)學家 Dirac在1952年得到的。該定理被認為是H問題的劃時代奠基性成果。,Dirac曾經(jīng)是丹麥奧爾胡斯大學知名教授，杰出的數(shù)學研究者。其父親(繼父)是在量子力學中做出卓越貢獻的物理學家狄拉克，1933年獲諾貝爾物理學獎。Dirac發(fā)表關

7、于H問題論文39篇。他1952年的定理將永載史冊！,16,1960年，美國耶魯大學數(shù)學家奧勒（Ore）院士考察不相鄰兩點度和情況，弱化了Dirac條件 ，得到一個光耀千秋的結果。,Ore發(fā)表關于H問題論文59篇。,定理3 (充分條件) 對于n3的單圖G，如果G中的任意兩個不相鄰頂點u與v，有：,那么，G是H圖。,注: (1) 該定理證明和定理2可以完全一致！,(2) 該定理的條件是緊的。例如：設G是由Kk+1的一個頂點和另一個Kk+1的一個頂點重合得到的圖，那么對于G,17,的任意兩個不相鄰頂點u與v，有：,但G是非H圖。,1976年，牛津大學的圖論大師Bondy(幫迪)等在Ore定理基礎上，

8、得到圖G和它的閉包間的同哈密爾頓性。,注：幫迪的書圖論及其應用是一本經(jīng)典必讀教材。有中譯本和習題解答。吳望祖譯 。,18,引理1 對于單圖G，如果G中有兩個不相鄰頂點u與v，滿足：,那么G是H圖當且僅當G + u v是H圖。,證明：“必要性” 顯然。,“充分性”,若不然，設G是非H圖，那么G+uv的每個H圈必然經(jīng)過邊uv, 于是G含有一條哈密爾頓(u ,v)路。,19,令：,對于S與T, 顯然，,另一方面：可以證明：,所以：,否則，設,那么，由,由,20,這樣在G中有H圈，與假設矛盾！,于是：,這與已知矛盾！,定義3 在n階單圖中，若對d (u) + d (v) n 的任意一對頂點u與v，均有

9、u a dj v , 則稱G是閉圖。,引理2 若G1和G2是同一個點集V的兩個閉圖，則G=G1G2是閉圖。,21,證明：任取w V，有：,所以，對,可得：,因G1與G2都是閉圖，所以u與v在G1與G2中都鄰接，所以，在G中也鄰接。故G是閉圖。,注：G1與G2都是閉圖，它們的并不一定是閉圖。,22,例如：,定義4 稱 是圖G的閉包，如果它是包含G的極小閉圖。,注：如果G本身是閉圖，則其閉包是它本身；如果G不是閉圖，則由定義可以通過在度和大于等于n的不相鄰頂點對間加邊來構造G的閉圖。例如：,23,引理3 圖G的閉包是唯一的。,證明：設 和 是圖G的兩個閉包，則：,所以，有：,又由引理2知， 是閉圖

10、，且,有：,同理：,所以，,24,定理4(幫迪閉包定理) 圖G是H圖當且僅當它的閉包是H圖。,證明：“必要性”顯然。,“充分性” ：假設G的閉包是H圖，我們證明G是H圖。,假設G的閉包和G相同，結論顯然。,若不然，設ei (1ik)是為構造G的閉包而添加的所有邊，由引理1，G是H圖當且僅當G+e1是H圖， G+e1是H圖當且僅當G+e1+e2是H圖, 反復應用引理1，可以得到定理結論。,由于完全圖一定是H圖，所以由閉包定理有：,推論1：設G是n3的單圖，若G的閉包是完全圖，則G是H圖。,25,由閉包定理也可以推出Dirac和Ore定理：,推論1：設G是n3的單圖。,(1) 若(G)n/2,則G

11、是H圖(Dirac定理);,(2) 若對于G中任意不相鄰頂點u與v，都有d(u)+d(v)n,則G是H圖.(Ore定理),在閉包定理的基礎上，Chvtal和幫迪進一步得到圖的H性的度序列判定法。,定理5(Chvtal度序列判定法) 設簡單圖G的度序列是(d1,d2,dn), 這里，d1d2dn,并且n3.若對任意的mm,或者dn-m n-m,則G是H圖。,證明方法：證G的閉包是完全圖。,26,證明：如果G的閉包是Kn，則G是H圖。,否則，設u與v是G的閉包中不相鄰接的且度和最大的兩點，又假設：,由于 是閉圖，u與v 是其中不鄰接頂點，所以：,于是，若取 ，則,對于這個m, 由于：,所以在G的閉

12、包中至少有m個點與v不鄰接。,27,由u與v的取法知：與v不鄰接的m個點中，u的度數(shù)最大。這就意味著：G中至少有m個點的度數(shù)不大于m,即：,另一方面，由m的選取，G的閉包中有n-1-m個點與u不相鄰接。而這些點中，v的度最大。這意味著：在G的閉包中有n-1-m個與u不鄰接的點的度數(shù)小于等于v的度數(shù)。,但是，由：,以及u的度數(shù)不超過v的度數(shù)假設，G的閉包中至少有n-m個點的度不超過n-m,從而在G中至少有n-m個點的度數(shù)嚴格小于n-m,即：,28,例4 求證下圖是H圖。,證明：在G中有：,因n=9,所以，m=1,2,3,4,29,所以，由度序列判定法，G是H圖。,注 ：哈密爾頓圖研究簡介,哈密爾頓問題的研究一直是圖論熱點。研究歷史大致情況如下：,(1) 1952年Dirac定理是研究的奠基性結果；,(2) 1962年Ore定理是Dirac定理的重要推進；,(3) 1976年幫迪的閉包定理是Ore定理的重要推進；,(4) 1985年時任劍橋大學兼?zhèn)惗卮髮W教授的Nicos在弱化Ore定理條件基礎上推進了Ore定理；,(5) 1996年GSU計算機系五個特聘教授之一的Chen和SCI 雜志圖論雜志編委Egawa及SCI雜志圖論與組合主編 Saito等再進一步推進Ore定理。,30,(6) 2007年, 賴虹建教授統(tǒng)一上面全部結果(見美