圖論及其應(yīng)用(13)

1、1本次課主要內(nèi)容本次課主要內(nèi)容(一一)、哈密爾頓圖的概念、哈密爾頓圖的概念(二二)、性質(zhì)與判定、性質(zhì)與判定哈密爾頓圖哈密爾頓圖2 1、背景、背景(一一)、哈密爾頓圖的概念、哈密爾頓圖的概念 1857年，年， 哈密爾頓發(fā)明了一個游戲哈密爾頓發(fā)明了一個游戲(Icosian Game).它是由一個木制的正十二面體構(gòu)成，在它的每個棱角它是由一個木制的正十二面體構(gòu)成，在它的每個棱角處標(biāo)有當(dāng)時很有名的城市。游戲目的是處標(biāo)有當(dāng)時很有名的城市。游戲目的是“環(huán)球旅行環(huán)球旅行”。為了容易記住被旅游過的城市為了容易記住被旅游過的城市 ，在每個棱角上放上一，在每個棱角上放上一個釘子，再用一根線繞在那些旅游過的城市上個

2、釘子，再用一根線繞在那些旅游過的城市上(釘子釘子),由此可以獲得旅程的直觀表示。由此可以獲得旅程的直觀表示。十二面體十二面體3 哈密爾頓哈密爾頓(1805-1865),愛爾蘭數(shù)學(xué)家。個人生活很愛爾蘭數(shù)學(xué)家。個人生活很不幸，但興趣廣泛：詩歌、光學(xué)、天文學(xué)和數(shù)學(xué)無所不幸，但興趣廣泛：詩歌、光學(xué)、天文學(xué)和數(shù)學(xué)無所不能。他的主要貢獻(xiàn)是在代數(shù)領(lǐng)域，發(fā)現(xiàn)了四元數(shù)不能。他的主要貢獻(xiàn)是在代數(shù)領(lǐng)域，發(fā)現(xiàn)了四元數(shù)(第第一個非交換代數(shù)一個非交換代數(shù))，他認(rèn)為數(shù)學(xué)是最美麗的花朵。，他認(rèn)為數(shù)學(xué)是最美麗的花朵。 哈密爾頓把該游戲以哈密爾頓把該游戲以25英鎊的價格買給了英鎊的價格買給了J.Jacques and Sons公

3、司公司 (該公司如今以制造國際象棋設(shè)備而著該公司如今以制造國際象棋設(shè)備而著名名) ，1859年獲得專利權(quán)。但商業(yè)運作失敗了。年獲得專利權(quán)。但商業(yè)運作失敗了。 該游戲促使人們思考點線連接的圖的結(jié)構(gòu)特征。這該游戲促使人們思考點線連接的圖的結(jié)構(gòu)特征。這就是圖論歷史上著名的哈密爾頓問題。就是圖論歷史上著名的哈密爾頓問題。 2、哈密爾頓圖與哈密爾頓路、哈密爾頓圖與哈密爾頓路 定義定義1 如果經(jīng)過圖如果經(jīng)過圖G的每個頂點恰好一次后能夠回到的每個頂點恰好一次后能夠回到出發(fā)點，稱這樣的圖為哈密爾頓圖，簡稱出發(fā)點，稱這樣的圖為哈密爾頓圖，簡稱H圖。所經(jīng)過圖。所經(jīng)過的閉途徑是的閉途徑是G的一個生成圈，稱為的一個生

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

5、性質(zhì)、性質(zhì) 定理定理1 (必要條件必要條件) 若若G為為H圖，則對圖，則對V(G)的任一非空的任一非空頂點子集頂點子集S，有：，有：()GSS 證明：證明：G是是H圖，設(shè)圖，設(shè)C是是G的的H圈。則對圈。則對V(G)的任意的任意非空子集非空子集S, 容易知道容易知道:()CSS 所以，有：所以，有：()()GSCSS7 注：不等式為注：不等式為G是是H圖的必要條件，即不等式不滿足圖的必要條件，即不等式不滿足時，可斷定對應(yīng)圖是非時，可斷定對應(yīng)圖是非H圖。圖。 例例3 求證下圖是非求證下圖是非H圖。圖。 證明：取證明：取S=2, 7, 6,則有：則有：543218769()43GSS 所以由定理所以

6、由定理1知，知，G為非為非H圖。圖。G8 注意：滿足定理注意：滿足定理1不等式的圖不一定是不等式的圖不一定是H圖。圖。 例如：著名的彼德森圖是非例如：著名的彼德森圖是非H圖，但它滿足定理圖，但它滿足定理1的的不等式。不等式。Peterson圖圖 彼得森彼得森(1839-1910)，丹麥哥本哈根大學(xué)數(shù)學(xué)教授。，丹麥哥本哈根大學(xué)數(shù)學(xué)教授。家境貧寒，因此而輟過學(xué)。但家境貧寒，因此而輟過學(xué)。但19歲就出版了關(guān)于對數(shù)的歲就出版了關(guān)于對數(shù)的專著。他作過中學(xué)教師，專著。他作過中學(xué)教師，32歲獲哥本哈根大學(xué)數(shù)學(xué)博士歲獲哥本哈根大學(xué)數(shù)學(xué)博士學(xué)位，然后一直在該大學(xué)作數(shù)學(xué)教授。學(xué)位，然后一直在該大學(xué)作數(shù)學(xué)教授。9

7、彼得森是一位出色的名教師。他講課遇到推理困難時，彼得森是一位出色的名教師。他講課遇到推理困難時，總是說：總是說：“這是顯而易見的這是顯而易見的”，并讓學(xué)生自己查閱他的著，并讓學(xué)生自己查閱他的著作。同時，他是一位有經(jīng)驗的作家，論述問題很形象，講作。同時，他是一位有經(jīng)驗的作家，論述問題很形象，講究形式的優(yōu)雅。究形式的優(yōu)雅。 1891年，彼得森發(fā)表了一篇奠定他圖論歷史地位的長達(dá)年，彼得森發(fā)表了一篇奠定他圖論歷史地位的長達(dá)28頁的論文。這篇文章被公認(rèn)是第一篇包含圖論基本結(jié)論頁的論文。這篇文章被公認(rèn)是第一篇包含圖論基本結(jié)論的文章。同時也是第一次在文章中使用的文章。同時也是第一次在文章中使用“圖圖”術(shù)語。

8、術(shù)語。 1898年，彼得森又發(fā)表了一篇只有年，彼得森又發(fā)表了一篇只有3頁的論文，在這篇文頁的論文，在這篇文章中，為舉反例構(gòu)造了著名的彼得森圖。章中，為舉反例構(gòu)造了著名的彼得森圖。10 2、判定、判定 圖的圖的H性判定是性判定是NP-困難問題。到目前為止，有關(guān)的困難問題。到目前為止，有關(guān)的定理有定理有300多個，但沒有一個是理想的。拓展多個，但沒有一個是理想的。拓展H圖的實圖的實用特征仍然被圖論領(lǐng)域認(rèn)為是重大而沒有解決的問題。用特征仍然被圖論領(lǐng)域認(rèn)為是重大而沒有解決的問題。 圖的哈密爾頓問題和四色問題被謂為挑戰(zhàn)圖論領(lǐng)域圖的哈密爾頓問題和四色問題被謂為挑戰(zhàn)圖論領(lǐng)域150年智力極限的總和。三位數(shù)學(xué)年

9、智力極限的總和。三位數(shù)學(xué)“諾獎諾獎”獲得者獲得者Erds、Whitney 、 Lovsz 以及以及Dirac、Ore等在哈密等在哈密爾頓問題上有過杰出貢獻(xiàn)。爾頓問題上有過杰出貢獻(xiàn)。 下面，介紹幾個著名的定理。下面，介紹幾個著名的定理。11 定理定理2 (充分條件充分條件) 對于對于n33的單圖的單圖G G，如果，如果G G中有：中有：()2nG 那么那么G是是H圖。圖。 證明證明: 若不然，設(shè)若不然，設(shè)G是一個滿足定理條件的極大非是一個滿足定理條件的極大非H簡單圖。顯然簡單圖。顯然G不能是完全圖，否則，不能是完全圖，否則，G是是H圖。圖。 于是，可以在于是，可以在G中任意取兩個不相鄰頂點中任意

10、取兩個不相鄰頂點u與與v?？紤]。考慮圖圖G + u v，由，由G的極大性，的極大性，G+ u v是是H圖。且圖。且G+ u v的每的每一個一個H圈必然包含邊圈必然包含邊u v。12 所以，在所以，在G中存在起點為中存在起點為u而終點為而終點為v的的H路路P。 不失一般性，設(shè)起點為不失一般性，設(shè)起點為u而終點為而終點為v的的H路路P為：為：121,nnPv vvuv vvvnvn-1vi+1viv3v2v1P 令：令：1()iiSv uvE G()jjTvv vE G13 對于對于S與與T, 顯然，顯然， 另一方面：可以證明：另一方面：可以證明：nvSTST 所以：所以：STn 否則，設(shè)否則，設(shè)

11、 ivST 那么，由那么，由+1()iivSvE G1有v 由由()iivTvE Gn有vvnvn-1vi+1viv3v2v1P 這樣在這樣在G中有中有H圈，與假設(shè)矛盾！圈，與假設(shè)矛盾！14 于是：于是： 這與已知這與已知 矛盾！矛盾！( )( )d ud vSTSTSTn 注：該定理是數(shù)學(xué)家注：該定理是數(shù)學(xué)家 Dirac在在1952年得到的。該定理被年得到的。該定理被認(rèn)為是認(rèn)為是H問題的劃時代奠基性成果。問題的劃時代奠基性成果。()2nG Dirac曾經(jīng)是丹麥奧爾胡斯大學(xué)知名教授，杰出的數(shù)學(xué)曾經(jīng)是丹麥奧爾胡斯大學(xué)知名教授，杰出的數(shù)學(xué)研究者。其父親研究者。其父親(繼父繼父)是在量子力學(xué)中做出卓

12、越貢獻(xiàn)的物是在量子力學(xué)中做出卓越貢獻(xiàn)的物理學(xué)家狄拉克，理學(xué)家狄拉克，1933年獲諾貝爾物理學(xué)獎。年獲諾貝爾物理學(xué)獎。Dirac發(fā)表關(guān)發(fā)表關(guān)于于H問題論文問題論文39篇。他篇。他1952年的定理將永載史冊！年的定理將永載史冊！15 1960年，美國耶魯大學(xué)數(shù)學(xué)家年，美國耶魯大學(xué)數(shù)學(xué)家奧勒（奧勒（Ore）院士考察不院士考察不相鄰兩點度和情況，弱化了相鄰兩點度和情況，弱化了Dirac條件條件 ，得到一個光耀千，得到一個光耀千秋的結(jié)果。秋的結(jié)果。 Ore發(fā)表關(guān)于發(fā)表關(guān)于H問題論文問題論文59篇。篇。 定理定理3 (充分條件充分條件) 對于對于n33的單圖的單圖G G，如果，如果G G中的任意中的任意兩

13、個不相鄰頂點兩個不相鄰頂點u u與與v v，有：，有：( )( )d ud vn 那么，那么，G是是H圖。圖。 注注: (1) 該定理證明和定理該定理證明和定理2可以完全一致！可以完全一致！ (2) 該定理的條件是緊的。例如：設(shè)該定理的條件是緊的。例如：設(shè)G是由是由Kk+1的一個頂?shù)囊粋€頂點和另一個點和另一個Kk+1的一個頂點重合得到的圖，那么對于的一個頂點重合得到的圖，那么對于G16 的任意兩個不相鄰頂點的任意兩個不相鄰頂點u與與v，有：，有：( )( )21d ud vkn 但但G是非是非H圖。圖。G=K1+2(K3) 1976年，牛津大學(xué)的圖論大師年，牛津大學(xué)的圖論大師Bondy(幫迪幫

14、迪)等在等在Ore定理基礎(chǔ)上，得到圖定理基礎(chǔ)上，得到圖G和它的閉包間的同哈密爾頓性。和它的閉包間的同哈密爾頓性。 注：幫迪的書注：幫迪的書圖論及其應(yīng)用圖論及其應(yīng)用是一本經(jīng)典必讀教是一本經(jīng)典必讀教材。有中譯本和習(xí)題解答。吳望祖譯材。有中譯本和習(xí)題解答。吳望祖譯 。17 引理引理1 對于單圖對于單圖G，如果，如果G中有兩個不相鄰頂點中有兩個不相鄰頂點u與與v，滿足：滿足：( )( )d ud vn 那么那么G是是H圖當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng)G + u v是是H圖。圖。 證明：證明：“必要性必要性” 顯然。顯然。 “充分性充分性” 若不然，設(shè)若不然，設(shè)G是非是非H圖，那么圖，那么G+uv的每個的每個H圈必

15、然經(jīng)過圈必然經(jīng)過邊邊uv, 于是于是G含有一條哈密爾頓含有一條哈密爾頓(u ,v)路。路。vnvn-1vi+1viv3v2v1P18 令：令：1()iiSv uvE G()jjTvv vE G 對于對于S與與T, 顯然，顯然， 另一方面：可以證明：另一方面：可以證明：nvSTST 所以：所以：STn 否則，設(shè)否則，設(shè) ivST 那么，由那么，由+1()iivSvE G1有v 由由()iivTvE Gn有v19vnvn-1vi+1viv3v2v1P 這樣在這樣在G中有中有H圈，與假設(shè)矛盾！圈，與假設(shè)矛盾！ 于是：于是： 這與已知矛盾！這與已知矛盾！( )( )d ud vSTSTSTn 定義定義

16、3 在在n階單圖中，若對階單圖中，若對d (u) + d (v) n n 的的任意一對任意一對頂點頂點u與與v，均有，均有u a dj v , 則稱則稱G是閉圖。是閉圖。 引理引理2 若若G1和和G2是同一個點集是同一個點集V的兩個閉圖，則的兩個閉圖，則G=G1G2是閉圖。是閉圖。20 證明：任取證明：任取w V，有：，有： 所以，對所以，對12()(),()()GGGGdwdwdwdw( )( )GGdudvn 可得：可得：1122( )( ),( )( )GGGGdudvn dudvn 因因G1與與G2都是閉圖，所以都是閉圖，所以u與與v在在G1與與G2中都鄰接，所中都鄰接，所以，在以，在

17、G中也鄰接。故中也鄰接。故G是閉圖。是閉圖。 注：注：G1與與G2都是閉圖，它們的并不一定是閉圖。都是閉圖，它們的并不一定是閉圖。21 例如：例如： 定義定義4 稱稱 是圖是圖G的閉包，如果它是包含的閉包，如果它是包含G的極小閉圖。的極小閉圖。G1G212GGG 注：如果注：如果G本身是閉圖，則其閉包是它本身；如果本身是閉圖，則其閉包是它本身；如果G不不是閉圖，則由定義可以通過在度和大于等于是閉圖，則由定義可以通過在度和大于等于n的不相鄰頂?shù)牟幌噜忢旤c對間加邊來構(gòu)造點對間加邊來構(gòu)造G的閉圖。例如：的閉圖。例如：GG22 引理引理3 圖圖G的閉包是唯一的。的閉包是唯一的。 證明：設(shè)證明：設(shè) 和和

18、 是圖是圖G的兩個閉包，則：的兩個閉包，則：1G2G1GG2GG 所以，有：所以，有：12GGG 又由引理又由引理2知，知， 是閉圖，且是閉圖，且12GG121GGG 有：有：121GGG 同理：同理：122GGG 所以，所以，12GG23 定理定理4(幫迪幫迪閉包定理閉包定理) 圖圖G是是H圖當(dāng)且僅當(dāng)它的閉圖當(dāng)且僅當(dāng)它的閉包是包是H圖。圖。 證明：證明：“必要性必要性”顯然。顯然。 “充分性充分性” ：假設(shè)：假設(shè)G的閉包是的閉包是H圖，我們證明圖，我們證明G是是H圖。圖。 假設(shè)假設(shè)G的閉包和的閉包和G相同，結(jié)論顯然。相同，結(jié)論顯然。 若不然，設(shè)若不然，設(shè)ei (1ik)ik)是為構(gòu)造是為構(gòu)造

19、G G的閉包而添加的所有的閉包而添加的所有邊，由引理邊，由引理1 1，G G是是H H圖當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng)G+eG+e1 1是是H H圖，圖， G+e1是是H圖圖當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G+e1+e2是是H圖圖, 反復(fù)應(yīng)用引理反復(fù)應(yīng)用引理1，可以得到定，可以得到定理結(jié)論。理結(jié)論。 由于完全圖一定是由于完全圖一定是H圖，所以由閉包定理有：圖，所以由閉包定理有： 推論推論1：設(shè)：設(shè)G是是n33的單圖，若的單圖，若G G的閉包是完全圖，則的閉包是完全圖，則G G是是H H圖。圖。24 由閉包定理也可以推出由閉包定理也可以推出Dirac和和Ore定理：定理： 推論推論1：設(shè)：設(shè)G是是n33的單圖。的單圖。 (

20、1) 若若(G)n/2,(G)n/2,則則G G是是H H圖圖(Dirac(Dirac定理定理);); (2) 若若對于對于G G中任意不相鄰頂點中任意不相鄰頂點u u與與v v，都有，都有d(u)+d(v)n,d(u)+d(v)n,則則G G是是H H圖圖.(Ore.(Ore定理定理) ) 在閉包定理的基礎(chǔ)上，在閉包定理的基礎(chǔ)上，Chvtal和幫迪進(jìn)一步得到圖的和幫迪進(jìn)一步得到圖的H性的度序列判定法。性的度序列判定法。 定理定理5(Chvtal度序列判定法度序列判定法) 設(shè)簡單圖設(shè)簡單圖G的度序列的度序列是是(d1,d2,dn), 這里，這里，d1dd2 2ddn n, ,并且并且n3.n3

21、.若對任意若對任意的的mn/2,mm,m,或者或者d dn-m n-m n-m, n-m,則則G G是是H H圖。圖。 證明方法：證證明方法：證G的閉包是完全圖。的閉包是完全圖。25 證明：如果證明：如果G的閉包是的閉包是Kn，則，則G是是H圖。圖。 否則，設(shè)否則，設(shè)u與與v是是G的閉包中不相鄰接的且度和最大的的閉包中不相鄰接的且度和最大的兩點，又假設(shè)：兩點，又假設(shè)：()( )GGdudv 由于由于 是閉圖，是閉圖，u與與v 是其中不鄰接頂點，所以：是其中不鄰接頂點，所以：G()( )GGdudvn 于是，若取于是，若取 ，則，則()Gmdu2nm 對于這個對于這個m, 由于：由于：( )()

22、GGdvndunm 所以在所以在G的閉包中至少有的閉包中至少有m個點與個點與v不鄰接。不鄰接。26 由由u與與v的取法知：與的取法知：與v不鄰接的不鄰接的m個點中，個點中，u的度數(shù)最的度數(shù)最大。這就意味著：大。這就意味著：G中至少有中至少有m個點的度數(shù)不大于個點的度數(shù)不大于m,即：即：mdm 另一方面，由另一方面，由m的選取，的選取，G的閉包中有的閉包中有n-1-m個點與個點與u不不相鄰接。而這些點中，相鄰接。而這些點中，v的度最大。這意味著：在的度最大。這意味著：在G的閉的閉包中有包中有n-1-m個與個與u不鄰接的點的度數(shù)小于等于不鄰接的點的度數(shù)小于等于v的度數(shù)。的度數(shù)。 但是，由：但是，由：( )()GGdvndunm 以及以及u的度數(shù)不超過的度數(shù)不超過v的度數(shù)假設(shè)，的度數(shù)假設(shè)，G的閉包中至少有的閉包中至少有n-m個點的度不超過個點的度不超過n-m,從而在從而在G中至少有中至少有n-m個點的度數(shù)個點的度數(shù)嚴(yán)格小于嚴(yán)格小于n-m,即：即：nmdnm27 例例4 求證下圖是求證下圖是H圖。圖。 證明：在證明：在G中有：中有：354218769G1233ddd455dd66d77d898dd 因因n=9,所以，所以，m=1,2,3,4285678945,936,927