第十五章 歐拉圖

第十五章歐拉圖第一頁，共三十九頁，2022年，8月28日定理15.1

無向圖G為歐拉圖的充要條件G是連通圖且沒有奇度頂點。

定理15.2

無向圖G是半歐拉圖的充要條件G是連通的且恰有兩個奇度的頂點。

或半歐拉圖有且僅有兩個奇點，一個為歐拉路的起點一個為歐拉路的終點。第二頁，共三十九頁，2022年，8月28日

例2

下圖中的各圖是否可以一筆畫出？NYYNY一筆畫問題？P296定理15.1第三頁，共三十九頁，2022年，8月28日定理15.3

有向圖D為歐拉圖的充要條件D是強連通圖且每個頂點的入度等于出度。

定理15.4

有向圖D是半歐拉圖的充要條件D是單向連通的且恰有兩個奇度的頂點，其中一個頂點的入度比出度大1，另一個頂點出度比入度大1，而其余頂點的入度等于出度。定理15.5

G是非平凡的歐拉圖的充要條件G是連通的且是若干個邊不重的圈的并。

第四頁，共三十九頁，2022年，8月28日Y第五頁，共三十九頁，2022年，8月28日相關應用哥尼斯堡七橋問題

18世紀哥尼斯堡（后來的加里寧格勒）位于立陶宛的普雷格爾上有7座橋，將河中的兩個島和河岸連結，如圖1所示。城中的居民經常沿河過橋散步，于是提出了一個問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點。這就是七橋問題，一個著名的圖論問題。

瑞士數學家歐拉（Euler）解決

抽象出的圖應該是？第六頁，共三十九頁，2022年，8月28日抽象出的圖應該是？我們當然不能試走！結論不言而喻！第七頁，共三十九頁，2022年，8月28日

應用1、右圖是某展覽館的平面圖，一個參觀者能否不重復地穿過每一扇門？如果不能，請說明理由。如果能，應從哪開始走？第八頁，共三十九頁，2022年，8月28日右圖中只有A，D兩個奇點，是一筆畫，所以答案是肯定的，應該從A或D展室開始走。第九頁，共三十九頁，2022年，8月28日例一個郵遞員投遞信件要走的街道如下左圖所示，圖中的數字表示各條街道的千米數，他從郵局出發(fā)，要走遍各街道，最后回到郵局。怎樣走才能使所走的行程最短？全程多少千米？郵局212111

怎么樣使非歐拉圖變?yōu)闅W拉圖？除去奇點！添加邊或刪除邊。怎么樣除去奇點？該題應該采用的辦法？重復某些邊（添加邊）。第十頁，共三十九頁，2022年，8月28日解：圖中共有8個奇點，不可能不重復地走遍所有的路。必須在8個奇點間添加4條線，才能消除所有奇點，從而成為能從郵局出發(fā)最后返回郵局的一筆畫。當然要在距離最近的兩個奇點間添加一條連線，如左上圖中虛線所示，共添加4條連線，這4條連線表示要重復走的路，顯然，這樣重復走的路程最短，全程34千米。走法參考右上圖(走法不唯一)。212111第十一頁，共三十九頁，2022年，8月28日2、右圖中每個小正方形的邊長都是100米。小明沿線段從A點到B點，不許走重復路，他最多能走多少米？該題應該采用的辦法？刪除某些邊，除去奇點對，將A、B變?yōu)榛c！第十二頁，共三十九頁，2022年，8月28日解：這道題大多數同學都采用試畫的方法，實際上還是用歐拉圖的判定定理來求解更合理、快捷。首先，圖中有8個奇點，在8個奇點之間至少要去掉4條線段，才能使這8個奇點變成偶點；其次，從A點出發(fā)到B點，A，B兩點必須是奇點，現在A，B都是偶點，必須在與A，B連接的線段中各去掉1條線段，使A，B成為奇點。所以至少要去掉6條線段，也就是最多能走1800米，走法如下圖。第十三頁，共三十九頁，2022年，8月28日作業(yè)1：一只木箱的長、寬、高分別為5，4，3厘米(見右圖)，有一只甲蟲從A點出發(fā)，沿棱爬行，每條棱不允許重復，則甲蟲回到A點時，最多能爬行多少厘米？第十四頁，共三十九頁，2022年，8月28日作業(yè)2郵遞員要從郵局出發(fā)，走遍左下圖(單位：千米)中所有街道，最后回到郵局，怎樣走路程最短？全程多少千米？第十五頁，共三十九頁，2022年，8月28日問題也是由一則游戲引入的：1859年，愛爾蘭數學家Hamilton提出的，如圖的正十二面體，以12個正五邊形為面。又稱為正則柏拉圖體。這些正五邊形的三邊相交與20個頂點的一個多面體。Hamilton用正十二面體代表地球。游戲題的內容是：沿著正十二面體的棱尋找一條旅行路線，通過每個城市恰好一次又回到出發(fā)城市。這便是Hamilton回路問題。哈密爾頓圖

第十六頁，共三十九頁，2022年，8月28日定義：通過圖G的每個結點一次且僅一次的環(huán)稱為哈密爾頓環(huán)。具有哈密爾頓環(huán)的圖稱為哈密爾頓圖。通過圖G的每個結點一次且僅一次的開路稱為哈密爾頓路。具有哈密爾頓路的圖稱為半哈密爾頓圖。

例3半哈密爾頓圖

哈密爾頓圖

哈密爾頓圖N第十七頁，共三十九頁，2022年，8月28日至今沒有一個像歐拉圖的充要條件那樣的“非平凡的”(不是定義的同義反復)關于哈密頓圖、半哈密頓圖的充分必要條件，但關于它們的充分性和必要性分別有一些研究成果，我們分別給出。但能體會到是邊多還是邊少是哈密頓圖的可能大？第十八頁，共三十九頁，2022年，8月28日一、哈密爾頓圖的必要條件定理15.6

若圖G=（V，E）是哈密爾頓圖，則對于V的任意一個非空子集V1，有p（G–V1）≤|V1|這里p（G–V1）表示從G中刪除V1（刪除S中的各結點及相關聯的邊）后所剩圖的分圖（連通分支）數。|V1|表示V1中的結點數。推論

若圖G=（V，E）是半哈密爾頓圖，則對于V的任意一個非空子集V1，有p（G–V1）≤|V1|＋1.第十九頁，共三十九頁，2022年，8月28日例4

在圖（a）中去掉結點u以后p（G–{u}）=2，（b）中去掉結點u1和u2以后，p（G–{u1，u2}）=3，由此可以判定，這兩個圖都不是哈密爾頓圖。P299例15.4有割點和橋的圖，不是哈密爾頓圖。第二十頁，共三十九頁，2022年，8月28日但必須要說明的是滿足定理條件的不一定是哈密頓圖。如下圖著名的彼得森(Petersen)圖是滿足定理條件的，但不是哈密頓圖。利用哈密頓圖的必要條件可以用來判定某些圖不是哈密頓圖,但不便于應用。因為要檢查G的頂點集V的所有子集。第二十一頁，共三十九頁，2022年，8月28日二、哈密爾頓圖的充分但不必要的條件定理15.7設G是n階的無向簡單圖，如果G中任意不相鄰的頂點u,v，均有d(u)+d(v)≥n-1,則G中存在哈密爾頓通路。推論設G是具有n個（n≥3）個結點的圖，如果G中任意不相鄰的頂點u,v均有d(u)+d(v)≥n,

則G是哈密頓圖。

不必要如一個六邊形！第二十二頁，共三十九頁，2022年，8月28日

證先證G為一連通圖。反證法：若不然，G由若干連通分支所組成。令v1，v2分屬于連通分支G1，G2；G1，G2各有n1，n2個頂點。顯然n1≤n，n2≤n，于是deg(v1)≤n1–1，deg(v2)≤n2–1，而deg(v1)

+deg(v2)≤n1+n2

–2＜n–1，與題設矛盾。第二十三頁，共三十九頁，2022年，8月28日為證G有哈密頓通路，只要在G中構作出一條長為n－1的通路。為此令P為G中任意一條長為p－1(p＜n)的通路，設其頂點序列為v1，v2，…，vp。我們來擴充這一通路。（1）如果有v

v1，v2，…，vp，它與v1或vp間有邊相關聯，那么可立即擴充P為長度為p的通路。（2）如果v1，vp均只與原通路P上的頂點相鄰，如下可證：G中有一條包含v1，v2，…，vp，長度為p的回路。如果v1與vp相鄰，那么我們已經如愿。如果v1與vi1,vi2,…,vir相鄰，1＜i1，i2,…,ir＜p,考慮vp：第二十四頁，共三十九頁，2022年，8月28日（2.1）若vp與vi1-1,vi2-1,…,vir-1之一，例如vi1-1相鄰，那么我們便可得到包含v1，v2，…，vp的回路：（v1，v2，…，vi1-1,vp,vp-1,…，vi1,v1）如圖8.25（a）所示。（2.2）若vp不與vi1-1,vi2-1,…,vir-1中任何一個相鄰，那么deg(vp)≤p-r-l，因而deg(v1)+deg(vp)≤r+p–r–l=p–1＜n–1與題設矛盾，因此（2.2）不可能發(fā)生。

第二十五頁，共三十九頁，2022年，8月28日現考慮G中這條包含v1，v2，…，vp、長度為p的回路。由于p≤n－l，故必有回路外頂點v與回路上頂點（例如vk）相鄰，如圖8.25（b）所示，那么我們可以得到一條長度為p的、包含v1，v2，…，vp的通路：（v,vk,vk-1,…,v1,vi1,vi1+1,…,vp,vi1-1,…,vk+1），如圖8.25（c）所示。重復過程（l），（2）不斷擴充通路P，直至它的長度為n–1，這時便得到G中的一條哈密頓通路。定理的后半部分仿上可證。第二十六頁，共三十九頁，2022年，8月28日＃＃推論若G是有n(≥3)個頂點的簡單圖，對于每一個頂點v滿足d(v)≥n/2，則G是哈密頓圖。證明：若G中任意兩點都相鄰，則有一條哈密頓回路：v1,v2,v3,…vn,v1。若G中存在不相鄰的點，則對于任意兩個都不相鄰的點u,v，有d(u)+d(v)=n,由定理知G是哈密頓圖。顯然≥3的完全圖是哈密頓圖。第二十七頁，共三十九頁，2022年，8月28日

例5

哈路哈環(huán)第二十八頁，共三十九頁，2022年，8月28日定義給定圖G=<V,E>有n個結點，若將圖G中度數之和至少是n的非鄰接結點連接起來得圖G'，對圖G'

重復上述步驟，直到不再有這樣的結點對存在為止，所得到的圖，稱為是原圖G的閉包，記作C(G)。定理15.8

當且僅當一個簡單圖的閉包是漢密爾頓圖時，這個簡單圖是漢密爾頓圖。第二十九頁，共三十九頁，2022年，8月28日定義：P273

設D為n階有向簡單圖,若D的基圖為n階無向完全圖Kn,則稱D是n階競賽圖。定理15.9若D為n(n2)階競賽圖,則D中具有哈密頓通路。第三十頁，共三十九頁，2022年，8月28日證對n作歸納法。1)當n=2時,D的基圖為K2,結論成立。2)當n=k時,結論成立。3)設V(D)={v1,v2,…,vk,vk+1}。令D1=D-vk+1,顯然,D1為k階競賽圖。由歸納假設可知:D1存在哈密頓通路。不妨假設:1=v’1v’2…v’k是一條哈密頓通路。下面證明:vk+1可擴到1中。3.1)存在v’r(1rk),有:<v’i,vk+1>E(D)

(i=1..r-1),<vk+1,v’r>E(D),如下圖(a)所示,則

=v’1v’2…v’r-1vk+1v’r…v’k為D中哈密頓通路。3.2)i{1,2,…,k},均有:<v’i,vk+1>E(D),見下圖(b)所示,則='∪<v’k,vk+1>為D中哈密頓通路。第三十一頁，共三十九頁，2022年，8月28日四、應用：帶權圖與貨郎擔問題定義15.3給定圖G=<V,E>(G為無向圖或有向圖),

設W:E→R(R為實數集),

對e=(vi,vj)(<vi,vj>)E(G),

設W(e)=wij,稱實數wij為邊e上的權(Weight)在G上,將權wij標注在邊e上,稱G為帶權圖通常將帶權圖G記作<V,E,W>稱eE(G)W(e)為G的權,記作W(G)第三十二頁，共三十九頁，2022年，8月28日貨郎擔問題設有n個城市,城市之間有道路,道路的長度均大于或等于0,可能是∞(城市之間無交通線)。一個旅行商從某個城市出發(fā),要經過每個城市一次且僅一次,最后回到出發(fā)的城市,問如何才能使他所走的路線最短？這就是著名的旅行商問題或貨郎擔問題。這個問題可化歸為圖論問題。設G=<V,E,W>為一個n階完全帶權圖Kn,各邊的權非負,且有些邊的權可能為∞。求G中一條最短的哈密頓回路,這就是貨郎擔問題的數學模型。第三十三頁，共三十九頁，2022年，8月28日例15.7下圖(a)為完全帶權圖K4,求出其不同的哈密頓回路,并指出最短的哈密頓回路。由貨郎擔問題中不同哈密頓回路的含義可知:求哈密頓回路可從任何頂點出發(fā)。下面先求出從a點出發(fā),考慮順時針與逆時針順序的不同的哈密頓回路。C1=abcdaC2=abdcaC3=acbdaC4=acdbaC5=adbcaC6=adcba于是,當不考慮時針順序時,可知:C1=C6,W(C1)=8(見圖(b))C2=C4,W(C2)=10(見圖(c))C3=C5,W(C3)=12經過比較可知,C1是最短的哈密頓回路。第三十四頁，共三十九頁，2022年，8月28日在n階完全帶權圖中,共存在(n-1)!/2種不同的哈密頓回路,經過比較可找出其最短的哈密頓回路。當n=4時,有3種不同的哈密頓回路當n=5時,有12種不同的哈密頓回路當n=6時,有60種不同的哈密頓回路…當n=11時,有5×9!=1,814,400種不同的哈密頓回路…由此可見:貨郎擔問題的計算量是非常大的。對于貨郎擔問題,人們一方面在尋找好的算法,另一方面也在尋找各種近似算法(找次佳的回路或可接受的回路)。第三十五頁，共三十九頁，2022年，8月28日例4

已知關于a，b，c，d，e，f和g的下述事實：a講英語；