特殊圖信息學(xué)院計算機(jī)應(yīng)用技術(shù)系授課教師：胡靜辦公地點(diǎn)：信息樓805電子郵箱：ise_huj@

第23講11/24/20221特殊圖信息學(xué)院計算機(jī)應(yīng)用技術(shù)系第23講11/22/20221離散數(shù)學(xué)第23講回顧上節(jié)課內(nèi)容：圖論中的基本概念握手定理及推論完全圖及其特征通路及回路？想一想，我們上節(jié)課學(xué)習(xí)了什么？11/24/20222離散數(shù)學(xué)第23講回顧上節(jié)課內(nèi)容：？想一想，我們上節(jié)課學(xué)習(xí)了離散數(shù)學(xué)第23講本講基本知識點(diǎn)：1、歐拉圖

歐拉圖的定義歐拉圖的判斷2、哈密爾頓圖

哈密爾頓圖的定義哈密爾頓圖判斷的充分條件3、樹

樹的定義最小生成樹？今天學(xué)習(xí)什么呢？11/24/20223離散數(shù)學(xué)第23講本講基本知識點(diǎn)：？今天學(xué)習(xí)什么呢？11/218世紀(jì)，在俄國哥尼斯堡城（Konnigsberg）（今俄羅斯加里寧格勒）的普萊格爾（Pregel）河上有7座橋．河中間有兩座島，島與河岸之間架有六座橋，另一座橋則連接著兩個島．星期天散步已成為當(dāng)?shù)鼐用竦囊环N習(xí)慣，但試圖走過這樣的七座橋，而且每橋只走過一次卻從來沒有成功過．直至引起瑞士數(shù)學(xué)家歐拉(LeonhardEuler，1707—1783)注意之前，沒有人能夠解決這個問題．第十五章歐拉圖與哈密爾頓圖11/24/2022418世紀(jì)，在俄國哥尼斯堡城（Konnigsberg）第十五章歐拉圖與哈密爾頓圖陸地島嶼島嶼陸地哥尼斯堡七橋問題

如何不重復(fù)地走完七橋后回到起點(diǎn)？。。。。ABCD11/24/20225第十五章歐拉圖與哈密爾頓圖第十五章歐拉圖與哈密爾頓圖15.1歐拉圖定義15.1通過圖(無向圖或有向圖)中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路。通過圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。規(guī)定：平凡圖是歐拉圖。11/24/20226第十五章歐拉圖與哈密爾頓圖15.1歐拉圖定義15.1規(guī)定第十五章歐拉圖與哈密爾頓圖定理15.1無向圖G是歐拉圖G是連通圖，且G中沒有奇度頂點(diǎn)。定理15.2無向圖G是半歐拉圖G是連通圖，且G中恰有兩個奇度頂點(diǎn)。并且這兩個奇度結(jié)點(diǎn)分別為歐拉通路的起點(diǎn)和終點(diǎn)。任意兩點(diǎn)之間都有通路11/24/20227第十五章歐拉圖與哈密爾頓圖定理15.1定理15.2任意兩點(diǎn)解：在圖中，僅有兩個度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c的歐拉通路，螞蟻乙走到c只要走一條歐拉通路，邊數(shù)為9條。而螞蟻甲要想走完所有的邊到達(dá)c，至少要先走一條邊到達(dá)b，再走一條歐拉通路，因而它至少要走10條邊才能到達(dá)c，所以乙必勝。例15.1(螞蟻比賽問題)甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)a，b處，并設(shè)圖中的邊長度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過圖中的所有邊最后到達(dá)結(jié)點(diǎn)c處。如果它們的速度相同，問誰先到達(dá)目的地？cb(乙)a(甲)第十五章歐拉圖與哈密爾頓圖11/24/20228解：在圖中，僅有兩個度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c一筆畫問題的判斷對于上圖，有圖(a)能一筆畫并且能回到出發(fā)點(diǎn)的，圖(b)能一筆畫但不能回到出發(fā)點(diǎn)的。11110(a)129283475612345(b)第十五章歐拉圖與哈密爾頓圖11/24/20229一筆畫問題的判斷對于上圖，有圖(a)能一筆畫并且能回到出發(fā)點(diǎn)求歐拉回路的Fleury算法任取v0∈V，令P0＝v0；設(shè)P0＝v0e1v1e2…eivi，按下面的方法從E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無別的邊可選取，否則ei+1不應(yīng)該為G'＝G-{e1,e2,…,ei}中的橋；當(dāng)2）不能再進(jìn)行時，算法結(jié)束。第十五章歐拉圖與哈密爾頓圖11/24/202210求歐拉回路的Fleury算法任取v0∈V，令P0＝v0；第十例15.2：Fleury算法應(yīng)用在右圖所示的歐拉圖中，求從v1出發(fā)的歐拉回路。如果P4＝v1e1v2e2v3e3v4e7v7，再往下走（注意別走橋），就可以走出歐拉回路：P4＝v1e1v2e2v3e3v4e7v7e6v6e5v5e4v4e8v2e9v7e10v1第十五章歐拉圖與哈密爾頓圖11/24/202211例15.2：Fleury算法應(yīng)用在右圖所示的歐拉圖如果P11110(a)1292834756第十五章歐拉圖與哈密爾頓圖橋的實例橋的實例11/24/20221211110(a)1292834756第十五章歐拉圖與哈密爾11110(a)1292834756goback第十五章歐拉圖與哈密爾頓圖11/24/20221311110(a)1292834756goback第十五章歐11110(a)1292834756goback第十五章歐拉圖與哈密爾頓圖11/24/20221411110(a)1292834756goback第十五章歐定理15.3有向圖D是歐拉圖D是強(qiáng)連通圖且每個頂點(diǎn)的入度都等于出度。定理15.4有向圖D是半歐拉圖D是單向連通的，且D中恰有兩個奇度頂點(diǎn)，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點(diǎn)的入度都等于出度。第十五章歐拉圖與哈密爾頓圖11/24/202215定理15.3定理15.4第十五章歐拉圖與哈密爾頓圖11/2第十五章歐拉圖與哈密爾頓圖答案：圖a和圖d是歐拉圖；圖b和圖e不是歐拉圖，但存在歐拉通路；圖c和圖f不存在歐拉通路。練習(xí)：判斷下列各圖是不是歐拉圖或半歐拉圖。11/24/202216第十五章歐拉圖與哈密爾頓圖答案：圖a和圖d是歐拉圖；圖b和哈密爾頓圖的起源：------周游世界問題1859年，數(shù)學(xué)家哈密爾頓創(chuàng)造了一種游戲：他把一個正十二面體的二十個頂點(diǎn)分別標(biāo)上了世界上二十大城市的名字，把正十二面體的三十條棱解釋成連接這些城市之間的交通線。玩法是從某個城市（頂點(diǎn)）出發(fā)，沿著這些交通線（邊）行走，要求經(jīng)過每個城市恰好一次，然后回到出發(fā)點(diǎn)。他把這個游戲稱為“周游世界”。1234567891011121314151617181920第十五章歐拉圖與哈密爾頓圖11/24/202217哈密爾頓圖的起源：1859年，數(shù)學(xué)家哈密爾頓創(chuàng)造了一種游戲：第十五章歐拉圖與哈密爾頓圖15.2哈密爾頓圖定義15.2經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)一次且僅一次的通路稱為哈密爾頓通路。經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密爾頓回路。具有哈密頓回路的圖稱為哈密爾頓圖.具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密爾頓圖.規(guī)定:平凡圖是哈密爾頓圖。11/24/202218第十五章歐拉圖與哈密爾頓圖15.2哈密爾頓圖11/22/第十五章歐拉圖與哈密爾頓圖定理15.7：設(shè)G是n階無向簡單圖，若對G中任意不相鄰的頂點(diǎn)ui,uj，均有d(ui)+d(uj)≥n-1則G中存在哈密爾頓通路.推論

設(shè)G為n(n≥3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點(diǎn)ui,uj，均有d(ui)+d(uj)≥n則G中存在哈密頓回路，從而G為哈密爾頓圖。無向圖具有哈密爾頓路與回路的充分條件11/24/202219第十五章歐拉圖與哈密爾頓圖定理15.7：推論無向圖具有哈利用哈密爾頓圖解決實際問題

典型例題1：某地有5個風(fēng)景點(diǎn)，若每個風(fēng)景點(diǎn)均有兩條道路與其他點(diǎn)相通。問游人可否經(jīng)過每個風(fēng)景點(diǎn)恰好一次而游完這5處？解將5個風(fēng)景點(diǎn)看成是有5個結(jié)點(diǎn)的無向圖，兩風(fēng)景點(diǎn)間的道路看成是無向圖的邊，因為每處均有兩條道路與其他結(jié)點(diǎn)相通，故每個結(jié)點(diǎn)的度數(shù)均為2，從而任意兩個不相鄰的結(jié)點(diǎn)的度數(shù)之和等于4，正好為總結(jié)點(diǎn)數(shù)減1。故此圖中存在一條哈密爾頓通路，因此本題有解。第十五章歐拉圖與哈密爾頓圖11/24/202220利用哈密爾頓圖解決實際問題

典型例題1：某地有5個風(fēng)景點(diǎn)，若第十五章歐拉圖與哈密頓圖典型例題2：在某次國際會議的預(yù)備會中，共有8人參加，他們來自不同的國家，已知他們中任何兩個無共同語言的人中的每一個，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個人排在圓桌旁，使其任何人都能與兩邊的人交談。解以8個人分別為無向簡單圖G的頂點(diǎn)，若任意兩人vi與vj有共同語言，就vi，vj在之間連無向邊(vi，vj)

，則任意一個人vi,d(vi)為與vi有共同語言的人數(shù)。由已知條件可知，任意與vi不相鄰的vj（i≠j），均有d(vi)+d(vj)≥8.由定理15.7的推論可知，G中存在哈密頓回路，按尋找到的回路的順序安排座次即可。11/24/202221第十五章歐拉圖與哈密頓圖典型例題2：在某次國際會議的預(yù)備典型例題2：今有a,b,c,d,e,f,g7人，已知下列事實：1）a會講英語2）b會講英語和漢語3）c會講英語、意大利語和俄語4）d會講日語和漢語5）e會講德語和意大利語6）f會講法語、日語和俄語7）g會講法語和德語試問這7個人應(yīng)如何安排座位，才能使每個人和他身邊的人交談？第十五章歐拉圖與哈密爾頓圖11/24/202222典型例題2：第十五章歐拉圖與哈密爾頓圖11/22/202解：設(shè)無向圖G=<V,E>,其中V={a,b,c,d,e,f,g},E={(u,v)|u,v∈V，且u和v有共同語言}。如右圖為連通圖，將七人排座圍圓桌而坐，使得每個人都能與兩邊的交談。即在右圖中尋找一條哈密爾頓回路，第十五章歐拉圖與哈密爾頓圖fgecabd經(jīng)觀察該回路是abdfgeca11/24/202223解：設(shè)無向圖G=<V,E>,其中第十五章歐拉圖與哈密爾頓圖第十六章樹16.1無向樹及其性質(zhì)定義16.1連通無回路的無向圖稱為無向樹，簡稱樹,常用T表示樹。平凡圖稱為平凡樹。若無向圖G至少有兩個連通分支，則稱G為森林。在無向樹中，懸掛頂點(diǎn)稱為樹葉，度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)。。。。。。。。。。。。。。。11/24/202224第十六章樹16.1無向樹及其性質(zhì)。。。第十六章樹定理16.1設(shè)G=<V,E>是n階m條邊的無向圖,則下面各命題是等價的：（1）G是樹。（2）G中任意兩個頂點(diǎn)之間存在唯一的路徑。（3）G中無回路且m=n-1。（4）G是連通的且m=n-1。(5)G是連通的且G中任何邊均為橋。(6)G中沒有回路，但在任何兩個不同的頂點(diǎn)之間加一條新邊，在所得的圖中得到唯一的一個含新邊的圈。11/24/202225第十六章樹定理16.1設(shè)G=<V,E>是n階m條邊的無向第十六章樹（4）G是連通的且m=n-1。(5)G是連通的且G中任何邊均為橋。證明：（4）（5）只需證明G中每條邊均為橋.e∈E，均有E(G-e)=n-1-1=n-2，由于n階圖G是連通的至少需要n-1條邊，所以G-e已不是連通圖，故e為橋。(5)G是連通的且G中任何邊均為橋。(6)G中沒有回路，但在任何兩個不同的頂點(diǎn)之間加一條新邊，在所得的圖中得到唯一的一個含新邊的圈。證明：（5）（6）由于G中每條邊均為橋，因而G中無圈，又由于G連通，所以G為樹。對于u,v∈V且u≠v,則u,v之間存在唯一的路徑T，則T∪（u,v）((u,v)為加的新邊)為G中的圈，顯然圈是唯一的。11/24/202226第十六章樹（4）G是連通的且m=n-1。證明：（4）（5第十六章樹(6)G中沒有回路，但在任何兩個不同的頂點(diǎn)之間加一條新邊，在所得的圖中得到唯一的一個含新邊的圈。(1)G是樹。證明：（6）（1）只要證明G是連通的。u,v∈V且u≠v，則新邊(u,v)∪G產(chǎn)生唯一的圈C，顯然有C-(u,v)為G中u到v的通路，故u~v,由u,v的任意性可知，G是連通的。11/24/202227第十六章樹(6)G中沒有回路，但在任何兩個不同的頂點(diǎn)之間第十六章樹定理16.2

設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉。證：設(shè)T有x片樹葉，由握手定理及定理16.1可知2(n-1)=∑d(vi)≥x+2(n-x)解得x≥2.以上兩個定理給出了無向樹的主要性質(zhì)，利用這些性質(zhì)和握手定理，可以畫出階數(shù)n比較小的所有非同構(gòu)的無向樹。11/24/202228第十六章樹定理16.2以上兩個定理給出了無向樹的主要性第十六章樹例16.2參見課本P375.

練習(xí)1：無向樹G有5片樹葉，3個2度分支點(diǎn)，其余分支點(diǎn)均為3度，問G有多少個頂點(diǎn)？解：設(shè)G有n個頂點(diǎn),則有下列關(guān)系式5Χ1+3Χ2+(n-5-3)Χ3=2Χ(n-1)

解得：n=11

11/24/202229第十六章樹例16.2參見課本P375.解：11/2第十六章樹16.2生成樹定義16.2設(shè)T是無向圖G的子圖并且為樹，則稱T為G的樹。若T是G的樹且為生成子圖，則稱T是G的生成樹。設(shè)T是G的生成樹，e∈E(G),若e∈E(T)，則稱e為T的樹枝，否則稱e為T的弦。稱導(dǎo)出子圖G[E(G)-E(T)]為T的余樹，記作T。圖中，紅色邊表示生成樹，黑色邊組成其余樹。可見，余樹可能不連通，也可能含回路。11/24/202230第十六章樹16.2生成樹圖中，紅色邊表示生成樹，黑色邊第十六章樹定義16.5設(shè)無向連通帶權(quán)圖G=<V,E,W>,T是G的一棵生成樹，T的各邊權(quán)之和稱為T的權(quán)，記作W(T).G的所有生成樹中權(quán)最小的生成樹稱為G的最小生成樹。Kruskal算法——一種求最小生成樹的算法設(shè)n階無向連通帶權(quán)圖G=<V,E,W>有m條邊,不妨設(shè)G中無環(huán)(否則可先刪去)，算法為：(1)將m條邊按權(quán)從小到大順序排列，設(shè)為e1,e2,…,em。(2)取e1在T中，然后依次檢查e2,…,em，若ej(j=2,3,…,m)與T中的邊不能構(gòu)成回路，則取ej在T中，否則放棄ej，考慮下一條邊，直至j>m。(3)算法停止時得到的T為G的最小生成樹。11/24/202231第十六章樹定義16.5設(shè)無向連通帶權(quán)圖G=<V,E,W>第十六章樹例：用Kruskal算法求下圖的最小生成樹。2121343151131。。。。。OK!。。。。。。。214515545332練習(xí)：求下圖的最小生成樹。11/24/202232第十六章樹例：用Kruskal算法求下圖的最小生成樹。21本講小結(jié)1、掌握歐拉圖的定義2、掌握判斷歐拉圖的方法3、哈密爾頓圖的定義4、掌握判斷哈密爾頓圖的方法（充分條件）5、掌握樹的定義6、最小生成樹及其算法作業(yè)：P304第9題離散數(shù)學(xué)第23講11/24/202233本講小結(jié)離散數(shù)學(xué)第23講11/22/202233特殊圖信息學(xué)院計算機(jī)應(yīng)用技術(shù)系授課教師：胡靜辦公地點(diǎn)：信息樓805電子郵箱：ise_huj@

第23講11/24/202234特殊圖信息學(xué)院計算機(jī)應(yīng)用技術(shù)系第23講11/22/20221離散數(shù)學(xué)第23講回顧上節(jié)課內(nèi)容：圖論中的基本概念握手定理及推論完全圖及其特征通路及回路？想一想，我們上節(jié)課學(xué)習(xí)了什么？11/24/202235離散數(shù)學(xué)第23講回顧上節(jié)課內(nèi)容：？想一想，我們上節(jié)課學(xué)習(xí)了離散數(shù)學(xué)第23講本講基本知識點(diǎn)：1、歐拉圖

歐拉圖的定義歐拉圖的判斷2、哈密爾頓圖

哈密爾頓圖的定義哈密爾頓圖判斷的充分條件3、樹

樹的定義最小生成樹？今天學(xué)習(xí)什么呢？11/24/202236離散數(shù)學(xué)第23講本講基本知識點(diǎn)：？今天學(xué)習(xí)什么呢？11/218世紀(jì)，在俄國哥尼斯堡城（Konnigsberg）（今俄羅斯加里寧格勒）的普萊格爾（Pregel）河上有7座橋．河中間有兩座島，島與河岸之間架有六座橋，另一座橋則連接著兩個島．星期天散步已成為當(dāng)?shù)鼐用竦囊环N習(xí)慣，但試圖走過這樣的七座橋，而且每橋只走過一次卻從來沒有成功過．直至引起瑞士數(shù)學(xué)家歐拉(LeonhardEuler，1707—1783)注意之前，沒有人能夠解決這個問題．第十五章歐拉圖與哈密爾頓圖11/24/20223718世紀(jì)，在俄國哥尼斯堡城（Konnigsberg）第十五章歐拉圖與哈密爾頓圖陸地島嶼島嶼陸地哥尼斯堡七橋問題

如何不重復(fù)地走完七橋后回到起點(diǎn)？。。。。ABCD11/24/202238第十五章歐拉圖與哈密爾頓圖第十五章歐拉圖與哈密爾頓圖15.1歐拉圖定義15.1通過圖(無向圖或有向圖)中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路。通過圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。規(guī)定：平凡圖是歐拉圖。11/24/202239第十五章歐拉圖與哈密爾頓圖15.1歐拉圖定義15.1規(guī)定第十五章歐拉圖與哈密爾頓圖定理15.1無向圖G是歐拉圖G是連通圖，且G中沒有奇度頂點(diǎn)。定理15.2無向圖G是半歐拉圖G是連通圖，且G中恰有兩個奇度頂點(diǎn)。并且這兩個奇度結(jié)點(diǎn)分別為歐拉通路的起點(diǎn)和終點(diǎn)。任意兩點(diǎn)之間都有通路11/24/202240第十五章歐拉圖與哈密爾頓圖定理15.1定理15.2任意兩點(diǎn)解：在圖中，僅有兩個度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c的歐拉通路，螞蟻乙走到c只要走一條歐拉通路，邊數(shù)為9條。而螞蟻甲要想走完所有的邊到達(dá)c，至少要先走一條邊到達(dá)b，再走一條歐拉通路，因而它至少要走10條邊才能到達(dá)c，所以乙必勝。例15.1(螞蟻比賽問題)甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)a，b處，并設(shè)圖中的邊長度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過圖中的所有邊最后到達(dá)結(jié)點(diǎn)c處。如果它們的速度相同，問誰先到達(dá)目的地？cb(乙)a(甲)第十五章歐拉圖與哈密爾頓圖11/24/202241解：在圖中，僅有兩個度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c一筆畫問題的判斷對于上圖，有圖(a)能一筆畫并且能回到出發(fā)點(diǎn)的，圖(b)能一筆畫但不能回到出發(fā)點(diǎn)的。11110(a)129283475612345(b)第十五章歐拉圖與哈密爾頓圖11/24/202242一筆畫問題的判斷對于上圖，有圖(a)能一筆畫并且能回到出發(fā)點(diǎn)求歐拉回路的Fleury算法任取v0∈V，令P0＝v0；設(shè)P0＝v0e1v1e2…eivi，按下面的方法從E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無別的邊可選取，否則ei+1不應(yīng)該為G'＝G-{e1,e2,…,ei}中的橋；當(dāng)2）不能再進(jìn)行時，算法結(jié)束。第十五章歐拉圖與哈密爾頓圖11/24/202243求歐拉回路的Fleury算法任取v0∈V，令P0＝v0；第十例15.2：Fleury算法應(yīng)用在右圖所示的歐拉圖中，求從v1出發(fā)的歐拉回路。如果P4＝v1e1v2e2v3e3v4e7v7，再往下走（注意別走橋），就可以走出歐拉回路：P4＝v1e1v2e2v3e3v4e7v7e6v6e5v5e4v4e8v2e9v7e10v1第十五章歐拉圖與哈密爾頓圖11/24/202244例15.2：Fleury算法應(yīng)用在右圖所示的歐拉圖如果P11110(a)1292834756第十五章歐拉圖與哈密爾頓圖橋的實例橋的實例11/24/20224511110(a)1292834756第十五章歐拉圖與哈密爾11110(a)1292834756goback第十五章歐拉圖與哈密爾頓圖11/24/20224611110(a)1292834756goback第十五章歐11110(a)1292834756goback第十五章歐拉圖與哈密爾頓圖11/24/20224711110(a)1292834756goback第十五章歐定理15.3有向圖D是歐拉圖D是強(qiáng)連通圖且每個頂點(diǎn)的入度都等于出度。定理15.4有向圖D是半歐拉圖D是單向連通的，且D中恰有兩個奇度頂點(diǎn)，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點(diǎn)的入度都等于出度。第十五章歐拉圖與哈密爾頓圖11/24/202248定理15.3定理15.4第十五章歐拉圖與哈密爾頓圖11/2第十五章歐拉圖與哈密爾頓圖答案：圖a和圖d是歐拉圖；圖b和圖e不是歐拉圖，但存在歐拉通路；圖c和圖f不存在歐拉通路。練習(xí)：判斷下列各圖是不是歐拉圖或半歐拉圖。11/24/202249第十五章歐拉圖與哈密爾頓圖答案：圖a和圖d是歐拉圖；圖b和哈密爾頓圖的起源：------周游世界問題1859年，數(shù)學(xué)家哈密爾頓創(chuàng)造了一種游戲：他把一個正十二面體的二十個頂點(diǎn)分別標(biāo)上了世界上二十大城市的名字，把正十二面體的三十條棱解釋成連接這些城市之間的交通線。玩法是從某個城市（頂點(diǎn)）出發(fā)，沿著這些交通線（邊）行走，要求經(jīng)過每個城市恰好一次，然后回到出發(fā)點(diǎn)。他把這個游戲稱為“周游世界”。1234567891011121314151617181920第十五章歐拉圖與哈密爾頓圖11/24/202250哈密爾頓圖的起源：1859年，數(shù)學(xué)家哈密爾頓創(chuàng)造了一種游戲：第十五章歐拉圖與哈密爾頓圖15.2哈密爾頓圖定義15.2經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)一次且僅一次的通路稱為哈密爾頓通路。經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密爾頓回路。具有哈密頓回路的圖稱為哈密爾頓圖.具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密爾頓圖.規(guī)定:平凡圖是哈密爾頓圖。11/24/202251第十五章歐拉圖與哈密爾頓圖15.2哈密爾頓圖11/22/第十五章歐拉圖與哈密爾頓圖定理15.7：設(shè)G是n階無向簡單圖，若對G中任意不相鄰的頂點(diǎn)ui,uj，均有d(ui)+d(uj)≥n-1則G中存在哈密爾頓通路.推論

設(shè)G為n(n≥3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點(diǎn)ui,uj，均有d(ui)+d(uj)≥n則G中存在哈密頓回路，從而G為哈密爾頓圖。無向圖具有哈密爾頓路與回路的充分條件11/24/202252第十五章歐拉圖與哈密爾頓圖定理15.7：推論無向圖具有哈利用哈密爾頓圖解決實際問題

典型例題1：某地有5個風(fēng)景點(diǎn)，若每個風(fēng)景點(diǎn)均有兩條道路與其他點(diǎn)相通。問游人可否經(jīng)過每個風(fēng)景點(diǎn)恰好一次而游完這5處？解將5個風(fēng)景點(diǎn)看成是有5個結(jié)點(diǎn)的無向圖，兩風(fēng)景點(diǎn)間的道路看成是無向圖的邊，因為每處均有兩條道路與其他結(jié)點(diǎn)相通，故每個結(jié)點(diǎn)的度數(shù)均為2，從而任意兩個不相鄰的結(jié)點(diǎn)的度數(shù)之和等于4，正好為總結(jié)點(diǎn)數(shù)減1。故此圖中存在一條哈密爾頓通路，因此本題有解。第十五章歐拉圖與哈密爾頓圖11/24/202253利用哈密爾頓圖解決實際問題

典型例題1：某地有5個風(fēng)景點(diǎn)，若第十五章歐拉圖與哈密頓圖典型例題2：在某次國際會議的預(yù)備會中，共有8人參加，他們來自不同的國家，已知他們中任何兩個無共同語言的人中的每一個，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個人排在圓桌旁，使其任何人都能與兩邊的人交談。解以8個人分別為無向簡單圖G的頂點(diǎn)，若任意兩人vi與vj有共同語言，就vi，vj在之間連無向邊(vi，vj)

，則任意一個人vi,d(vi)為與vi有共同語言的人數(shù)。由已知條件可知，任意與vi不相鄰的vj（i≠j），均有d(vi)+d(vj)≥8.由定理15.7的推論可知，G中存在哈密頓回路，按尋找到的回路的順序安排座次即可。11/24/202254第十五章歐拉圖與哈密頓圖典型例題2：在某次國際會議的預(yù)備典型例題2：今有a,b,c,d,e,f,g7人，已知下列事實：1）a會講英語2）b會講英語和漢語3）c會講英語、意大利語和俄語4）d會講日語和漢語5）e會講德語和意大利語6）f會講法語、日語和俄語7）g會講法語和德語試問這7個人應(yīng)如何安排座位，才能使每個人和他身邊的人交談？第十五章歐拉圖與哈密爾頓圖11/24/202255典型例題2：第十五章歐拉圖與哈密爾頓圖11/22/202解：設(shè)無向圖G=<V,E>,其中V={a,b,c,d,e,f,g},E={(u,v)|u,v∈V，且u和v有共同語言}。如右圖為連通圖，將七人排座圍圓桌而坐，使得每個人都能與兩邊的交談。即在右圖中尋找一條哈密爾頓回路，第十五章歐拉圖與哈密爾頓圖fgecabd經(jīng)觀察該回路是abdfgeca11/24/202256解：設(shè)無向圖G=<V,E>,其中第十五章歐拉圖與哈密爾頓圖第十六章樹16.1無向樹及其性質(zhì)定義16.1連通無回路的無向圖稱為無向樹，簡稱樹,常用T表示樹。平凡圖稱為平凡樹。若無向圖G至少有兩個連通分支，則稱G為森林。在無向樹中，懸掛頂點(diǎn)稱為樹葉，度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)。。。。。。。。。。。。。。。11/24/202257第十六章樹16.1無向樹及其性質(zhì)。。。第十六章樹定理16.1設(shè)G=<V,E>是n階m條邊的無向圖,則下面各命題是等價的：（1）G是樹。（2）G中任意兩個頂點(diǎn)之間存在唯一的路徑。（3）G中無回路且m=n-1。（4）G是連通的且m=n-1。(5)G是連通的且G中任何邊均為橋。(6)G中沒有回路，但在任何兩個不同的頂點(diǎn)之間加一條新邊，在所得的圖中得到唯一的一個含新邊的圈。11/24/202258第十六章樹定理16.1設(shè)G=<V,E>是n階m條邊的無向第十六章樹（4）G是連通的且m=n-1。(5)G是連通的且G中任何邊均為橋。證明：（4）（5）只需證明G中每條邊均為橋.e∈E，均有E(G-e)=n-1-1=n-2，由于n階圖G是連通的至少需要n-1條邊，所以G-e已不是連通圖，故e為橋。(5)G是連通的且G中任何邊均為橋。(6)G中沒有回路，但在任何兩個不同的頂點(diǎn)之間加一條新邊，在所得的圖中得到唯一的一個含新邊的圈。證明：（5）（6）由于G中每條邊均為橋，因而G中無圈，又由于G連通，所以G為樹。對于u,v∈V且u≠v,則u,v之間存在唯一的路徑T，則T∪（u,v）((u,v)為加的新邊)為G中的圈，顯然圈是唯一的。11/24/202259第十六章樹（4）G是連通的且m=n-1。證明：（4）（5第十六章樹(6)G中沒有回路，但在任何兩個不同的頂點(diǎn)之間加一條新邊，在所得的圖中得到唯一的一個含新邊的圈。(1)G是樹。證明：（6）（1）只要證明G是連通的。u,v∈V且u≠v，則新邊(u,v)∪G產(chǎn)生唯一的圈C，顯然有C-(u,v)為G中u到v的通路，故u~v,由u,v的任意性可知，G是連通的。11/24/202