圖論課件哈密爾頓圖1第一頁，共三十二頁，2022年，8月28日本次課主要內(nèi)容(一)、哈密爾頓圖的概念(二)、性質(zhì)與判定哈密爾頓圖2第二頁，共三十二頁，2022年，8月28日

1、背景(一)、哈密爾頓圖的概念

1857年，哈密爾頓發(fā)明了一個游戲(IcosianGame).它是由一個木制的正十二面體構(gòu)成，在它的每個棱角處標(biāo)有當(dāng)時很有名的城市。游戲目的是“環(huán)球旅行”。為了容易記住被旅游過的城市，在每個棱角上放上一個釘子，再用一根線繞在那些旅游過的城市上(釘子),由此可以獲得旅程的直觀表示。十二面體3第三頁，共三十二頁，2022年，8月28日哈密爾頓(1805---1865),愛爾蘭數(shù)學(xué)家。個人生活很不幸，但興趣廣泛：詩歌、光學(xué)、天文學(xué)和數(shù)學(xué)無所不能。他的主要貢獻(xiàn)是在代數(shù)領(lǐng)域，發(fā)現(xiàn)了四元數(shù)(第一個非交換代數(shù))，他認(rèn)為數(shù)學(xué)是最美麗的花朵。哈密爾頓把該游戲以25英鎊的價格買給了J.JacquesandSons公司(該公司如今以制造國際象棋設(shè)備而著名)，1859年獲得專利權(quán)。但商業(yè)運作失敗了。該游戲促使人們思考點線連接的圖的結(jié)構(gòu)特征。這就是圖論歷史上著名的哈密爾頓問題。

2、哈密爾頓圖與哈密爾頓路定義1如果經(jīng)過圖G的每個頂點恰好一次后能夠回到出發(fā)點，稱這樣的圖為哈密爾頓圖，簡稱H圖。所經(jīng)過的閉途徑是G的一個生成圈，稱為G的哈密爾頓圈。4第四頁，共三十二頁，2022年，8月28日例1、正十二面體是H圖。

十二面體5第五頁，共三十二頁，2022年，8月28日例2下圖G是非H圖。證明：因為在G中，邊uv是割邊，所以它不在G的任意圈上，于是u與v不能在G的同一個圈上。故G不存在包括所有頂點的圈，即G是非H圖。圖Guv定義2如果存在經(jīng)過G的每個頂點恰好一次的路，稱該路為G的哈密爾頓路，簡稱H路。uv圖G6第六頁，共三十二頁，2022年，8月28日(二)、性質(zhì)與判定

1、性質(zhì)定理1(必要條件)若G為H圖，則對V(G)的任一非空頂點子集S，有：證明：G是H圖，設(shè)C是G的H圈。則對V(G)的任意非空子集S,容易知道:所以，有：7第七頁，共三十二頁，2022年，8月28日注：不等式為G是H圖的必要條件，即不等式不滿足時，可斷定對應(yīng)圖是非H圖。例3求證下圖是非H圖。證明：取S=｛2,7,6｝,則有：543218769所以由定理1知，G為非H圖。G8第八頁，共三十二頁，2022年，8月28日注意：滿足定理1不等式的圖不一定是H圖。例如：著名的彼德森圖是非H圖，但它滿足定理1的不等式。Peterson圖彼得森(1839----1910)，丹麥哥本哈根大學(xué)數(shù)學(xué)教授。家境貧寒，因此而輟過學(xué)。但19歲就出版了關(guān)于對數(shù)的專著。他作過中學(xué)教師，32歲獲哥本哈根大學(xué)數(shù)學(xué)博士學(xué)位，然后一直在該大學(xué)作數(shù)學(xué)教授。9第九頁，共三十二頁，2022年，8月28日彼得森是一位出色的名教師。他講課遇到推理困難時，總是說：“這是顯而易見的”，并讓學(xué)生自己查閱他的著作。同時，他是一位有經(jīng)驗的作家，論述問題很形象，講究形式的優(yōu)雅。

1891年，彼得森發(fā)表了一篇奠定他圖論歷史地位的長達(dá)28頁的論文。這篇文章被公認(rèn)是第一篇包含圖論基本結(jié)論的文章。同時也是第一次在文章中使用“圖”術(shù)語。

1898年，彼得森又發(fā)表了一篇只有3頁的論文，在這篇文章中，為舉反例構(gòu)造了著名的彼得森圖。10第十頁，共三十二頁，2022年，8月28日

2、判定圖的H性判定是NP-困難問題。到目前為止，有關(guān)的定理有300多個，但沒有一個是理想的。拓展H圖的實用特征仍然被圖論領(lǐng)域認(rèn)為是重大而沒有解決的問題。圖的哈密爾頓問題和四色問題被謂為挑戰(zhàn)圖論領(lǐng)域150年智力極限的總和。三位數(shù)學(xué)“諾獎”獲得者Erd?s、Whitney、Lovász以及Dirac、Ore等在哈密爾頓問題上有過杰出貢獻(xiàn)。下面，介紹幾個著名的定理。11第十一頁，共三十二頁，2022年，8月28日定理2(充分條件)對于n≧3的單圖G，如果G中有：那么G是H圖。證明:若不然，設(shè)G是一個滿足定理條件的極大非H簡單圖。顯然G不能是完全圖，否則，G是H圖。于是，可以在G中任意取兩個不相鄰頂點u與v。考慮圖G+uv，由G的極大性，G+uv是H圖。且G+uv的每一個H圈必然包含邊uv。12第十二頁，共三十二頁，2022年，8月28日所以，在G中存在起點為u而終點為v的H路P。不失一般性，設(shè)起點為u而終點為v的H路P為：vnvn-1vi+1viv3v2v1P令：13第十三頁，共三十二頁，2022年，8月28日對于S與T,顯然，另一方面：可以證明：所以：否則，設(shè)那么，由由vnvn-1vi+1viv3v2v1P這樣在G中有H圈，與假設(shè)矛盾！14第十四頁，共三十二頁，2022年，8月28日于是：這與已知矛盾！注：該定理是數(shù)學(xué)家Dirac在1952年得到的。該定理被認(rèn)為是H問題的劃時代奠基性成果。Dirac曾經(jīng)是丹麥奧爾胡斯大學(xué)知名教授，杰出的數(shù)學(xué)研究者。其父親(繼父)是在量子力學(xué)中做出卓越貢獻(xiàn)的物理學(xué)家狄拉克，1933年獲諾貝爾物理學(xué)獎。Dirac發(fā)表關(guān)于H問題論文39篇。他1952年的定理將永載史冊！15第十五頁，共三十二頁，2022年，8月28日

1960年，美國耶魯大學(xué)數(shù)學(xué)家奧勒（Ore）院士考察不相鄰兩點度和情況，弱化了Dirac條件，得到一個光耀千秋的結(jié)果。

Ore發(fā)表關(guān)于H問題論文59篇。定理3(充分條件)對于n≧3的單圖G，如果G中的任意兩個不相鄰頂點u與v，有：那么，G是H圖。注:(1)該定理證明和定理2可以完全一致！

(2)該定理的條件是緊的。例如：設(shè)G是由Kk+1的一個頂點和另一個Kk+1的一個頂點重合得到的圖，那么對于G16第十六頁，共三十二頁，2022年，8月28日的任意兩個不相鄰頂點u與v，有：

但G是非H圖。G=K1+2(K3)

1976年，牛津大學(xué)的圖論大師Bondy(幫迪)等在Ore定理基礎(chǔ)上，得到圖G和它的閉包間的同哈密爾頓性。注：幫迪的書《圖論及其應(yīng)用》是一本經(jīng)典必讀教材。有中譯本和習(xí)題解答。吳望祖譯。17第十七頁，共三十二頁，2022年，8月28日

引理1對于單圖G，如果G中有兩個不相鄰頂點u與v，滿足：

那么G是H圖當(dāng)且僅當(dāng)G+uv是H圖。

證明：“必要性”顯然?！俺浞中浴比舨蝗?，設(shè)G是非H圖，那么G+uv的每個H圈必然經(jīng)過邊uv,于是G含有一條哈密爾頓(u,v)路。vnvn-1vi+1viv3v2v1P18第十八頁，共三十二頁，2022年，8月28日令：對于S與T,顯然，另一方面：可以證明：所以：否則，設(shè)那么，由由19第十九頁，共三十二頁，2022年，8月28日vnvn-1vi+1viv3v2v1P這樣在G中有H圈，與假設(shè)矛盾！于是：這與已知矛盾！定義3在n階單圖中，若對d(u)+d(v)≧n的任意一對頂點u與v，均有uadjv,則稱G是閉圖。

引理2若G1和G2是同一個點集V的兩個閉圖，則G=G1∩G2是閉圖。20第二十頁，共三十二頁，2022年，8月28日證明：任取w∈V，有：

所以，對

可得：

因G1與G2都是閉圖，所以u與v在G1與G2中都鄰接，所以，在G中也鄰接。故G是閉圖。

注：G1與G2都是閉圖，它們的并不一定是閉圖。21第二十一頁，共三十二頁，2022年，8月28日

例如：

定義4稱是圖G的閉包，如果它是包含G的極小閉圖。G1G2

注：如果G本身是閉圖，則其閉包是它本身；如果G不是閉圖，則由定義可以通過在度和大于等于n的不相鄰頂點對間加邊來構(gòu)造G的閉圖。例如：G22第二十二頁，共三十二頁，2022年，8月28日

引理3圖G的閉包是唯一的。

證明：設(shè)和

是圖G的兩個閉包，則：

所以，有：

又由引理2知，是閉圖，且

有：

同理：

所以，23第二十三頁，共三十二頁，2022年，8月28日定理4(幫迪——閉包定理)圖G是H圖當(dāng)且僅當(dāng)它的閉包是H圖。證明：“必要性”顯然?！俺浞中浴保杭僭O(shè)G的閉包是H圖，我們證明G是H圖。假設(shè)G的閉包和G相同，結(jié)論顯然。若不然，設(shè)ei(1≦i≦k)是為構(gòu)造G的閉包而添加的所有邊，由引理1，G是H圖當(dāng)且僅當(dāng)G+e1是H圖，G+e1是H圖當(dāng)且僅當(dāng)G+e1+e2是H圖,…,反復(fù)應(yīng)用引理1，可以得到定理結(jié)論。由于完全圖一定是H圖，所以由閉包定理有：推論1：設(shè)G是n≧3的單圖，若G的閉包是完全圖，則G是H圖。24第二十四頁，共三十二頁，2022年，8月28日由閉包定理也可以推出Dirac和Ore定理：推論1：設(shè)G是n≧3的單圖。

(1)若δ(G)≧n/2,則G是H圖(Dirac定理);

(2)若對于G中任意不相鄰頂點u與v，都有d(u)+d(v)≧n,則G是H圖.(Ore定理)在閉包定理的基礎(chǔ)上，Chvátal和幫迪進(jìn)一步得到圖的H性的度序列判定法。定理5(Chvátal——度序列判定法)設(shè)簡單圖G的度序列是(d1,d2,…,dn),這里，d1≦d2≦…≦dn,并且n≧3.若對任意的m<n/2,或者dm>m,或者dn-m≧n-m,則G是H圖。證明方法：證G的閉包是完全圖。25第二十五頁，共三十二頁，2022年，8月28日證明：如果G的閉包是Kn，則G是H圖。否則，設(shè)u與v是G的閉包中不相鄰接的且度和最大的兩點，又假設(shè)：由于是閉圖，u與v是其中不鄰接頂點，所以：于是，若取，則對于這個m,由于：所以在G的閉包中至少有m個點與v不鄰接。26第二十六頁，共三十二頁，2022年，8月28日由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ù)假設(shè)，G的閉包中至少有n-m個點的度不超過n-m,從而在G中至少有n-m個點的度數(shù)嚴(yán)格小于n-m,即：27第二十七頁，共三十二頁，2022年，8月28日例4求證下圖是H圖。證明：在G中有：354218769G因n=9,所以，m=1,2,3,428第二十八頁，共三十二頁，2022年，8月28日所以，由度序列判定法，G是H圖。

注：哈密爾頓圖研究簡介哈密爾頓問題的研究一直是圖論熱點。