第十五章歐拉圖與哈密頓圖

1、14.5 圖的運算 定義定義14.28 設(shè)G1=，G2=為兩個圖。若V1V2=，則稱G1與G2是不交不交的。若E1E2=，則稱G1與G2是邊不交邊不交的或邊不重邊不重的。 不交的圖，必然是邊不交的，但反之不真。 定義定義14.29 設(shè)G1=，G2=為不含孤立點的兩個圖（它們同為無向圖或同為有向圖）。 1）稱以E1E2為邊集，以E1E2中邊關(guān)聯(lián)的頂點組成的集合為頂點集的圖為G1與G2的并圖并圖，記作G1G2 （2）稱以E1-E2為邊集，以E1-E2中邊關(guān)聯(lián)的頂點組成的集合為頂點集的圖為G1與G2的差圖差圖，記作G1-G2. （3）稱以E1E2為邊集，以E1E2中邊關(guān)聯(lián)的頂點組成的集合為頂點集的圖

2、為G1與G2的交圖交圖，記作G1G2. （4）稱以E1 E2為邊集（ 為集合之間的對稱差運算），以E1 E2中邊關(guān)聯(lián)的頂點組成的集合為頂點集的圖為G1與G2的環(huán)和環(huán)和，記作G1 G2. 注意: 1若G1=G2，則G1G2= G1G2=G1(G2)，而G1-G2=G2-G1= G1G2=，這就是在圖的定義中給出空圖概念的原因。 2當(dāng)G1與G2邊不重時，G1G2=，G1-G2=G1，而G2-G1=G2 ，G1G2=G1G2 3圖之間環(huán)和的定義也可以用并、交、差給出，即G1G2=（G1G2）-（G1G2） 在不同的圖論書中，關(guān)于圖運算的定義還不一致，本書中的定義與其他書可能有所不同，請讀者注意區(qū)分。

3、 設(shè)G是n階無向簡單圖，n3且為奇數(shù)，證明G與 中奇度頂點的個數(shù)相等。 故 與G中奇度頂點個數(shù)相等。為偶數(shù)(n為奇數(shù)) 于是，若 為奇數(shù),必有d G(v)也為奇數(shù)。已知在完全二部圖Kr,s中，rs.(1)Kr,s中含有多少種非同構(gòu)的圈？(2)Kr,s中至多有多少個頂點彼此不相鄰？(3)Kr,s中至多有多少條邊彼此不相鄰？(4)Kr,s的點連通度為幾？邊連通度為幾？ (1)當(dāng)r=1時，沒有長度大于等于1的圈。 當(dāng)2rs時，有長度為4,6,2r的圈，它們都是偶圈，因而非同構(gòu)的圈共有r-1種。 (2)至多有maxr,s個頂點彼此不相鄰。 (3)至多有minr,s條邊彼此不相鄰。 (4)=minr,s

4、 第十五章第十五章 歐拉圖與哈密頓圖歐拉圖與哈密頓圖 15.1 歐拉圖 15.2 哈密頓圖15.3 帶權(quán)圖與貨郎擔(dān)問題 格尼斯堡七橋問題：難題：一個人怎樣不重復(fù)地走完七橋，最后回到出發(fā)地點？難題：一個人怎樣不重復(fù)地走完七橋，最后回到出發(fā)地點？歐洲普魯士境內(nèi)格尼斯堡城中有一條貫穿全市的普雷格爾河，河中有兩個小島，由七座橋相連接。15.1 15.1 歐拉圖歐拉圖定義定義 通過圖（無向圖或有向圖）中所有邊邊一次且僅一 次行遍圖中所有頂點的通路稱為歐拉通路歐拉通路， 通過圖中所有邊一次并且僅一次行遍所有頂點的 回路稱為歐拉回路歐拉回路。具有歐拉回路的圖稱為歐拉圖歐拉圖。具有歐拉通路而無歐拉回路的圖稱為

5、半歐拉圖半歐拉圖。歐拉通路是圖中經(jīng)過所有邊的簡單的生成通路， 經(jīng)過所有頂點的通路稱為生成通路歐拉回路是經(jīng)過所有邊的簡單的生成回路。 規(guī)定： 平凡圖是歐拉圖。 (1)是歐拉圖 e1e2e3e4e5為歐拉回路 （2）為半歐拉圖 （3）不是歐拉圖，也不是半歐拉圖 （4）為歐拉圖 e1e2e3e4為歐拉回路 （5），（6）不是歐拉圖，也不是半歐拉圖 定理定理15.1 無向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通圖，且G 中沒有奇度頂點。 證：證： 若G是平凡圖，結(jié)論顯然成立， 下面設(shè)G為非平凡圖，設(shè)G是m條邊的n階無向圖。并設(shè)G的頂點集V=v1,v2,vn. 必要性。 因而vi,vj連通，所以G為連通圖。 因為G

6、為歐拉圖，所以G中存在歐拉回路，設(shè)C為G中任意一條歐拉回路， vi,vjV，vi,vj都在C上，又 viV，vi在C上每出現(xiàn)一次獲得2度，若出現(xiàn)k次就獲得2k度，即d(vi)=2k，所以G中無奇度頂點。 充分性： 由于G為非平凡的連通圖可知，G中邊數(shù)m1.對m作歸納法。 (1) m=1時，由G的連通性及無奇度頂點可知，G只能 是一個環(huán)，因而G為歐拉圖。 (2) 設(shè)mk (k1)時結(jié)論成立，要證明m=K+1時，結(jié)論也成立。 由G的連通性及無奇度頂點可知，(G)2. 用擴大路徑法可以證明G中存在長度大于或等于3的圈， 設(shè)C為G中一個圈，刪除C上的全部邊， 得G的生成子圖G， 設(shè)G有s個連通分支G1

7、,G2,Gs， 每個連通分支至多有k條邊，且無奇度頂點， 并且設(shè)Gi與C的公共頂點為 ，i=1,2,s， 由歸納假設(shè)可知，G1,G2,Gs都是歐拉圖，因而都存在歐拉回路Ci，i=1,2,s. 最后將C還原（即將刪除的邊重新加上）， 并從C上的某頂點vr開始行遍，每遇到 ，就行遍Gi中的歐拉回路Ci，i=1,2,s，最后回到vr， 得回路vr vr， 此回路經(jīng)過G中每條邊一次且僅一次并行遍G中所有頂點，因而它是G中的歐拉回路 故G為歐拉圖。 七橋問題定理定理15.2 無向圖G是半歐拉圖當(dāng)且僅當(dāng)G是連通的，且G中恰有兩個奇度頂點。證證: 必要性。 設(shè)G是m條邊的n階無向圖，因為G為半歐拉圖，因而G

8、中存在歐拉通路（但不存在歐拉回路）， 設(shè)=vi0ej1vi1vim-1ejmvim為G中一條歐拉通路，vi0 vim . vV(G)，若v不在的端點出現(xiàn)，顯然d(v)為偶數(shù)， 若v在端點出現(xiàn)過，則d(v)為奇數(shù)，因為只有兩個端點且不同，因而G中只有兩個奇數(shù)頂點。 另外，G的連通性是顯然的。 下證充分性。 設(shè)G的兩個奇度頂點分別為u0和v0，對G加新邊（u0,v0），得G=G(u0,v0)， 則G是連通且無奇度頂點的圖， 由定理15.1可知，G為歐拉圖，因而存在歐拉回路C，而C=C- (u0,v0)為G中一條歐拉通路，所以G為半歐拉圖。 定理定理15.3 有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強連通的且每

9、個頂點的入度都等于出度。 定理定理15.4 有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點的入度都等于出度。 圖15.3 (1) 圖為歐拉圖 可以看成圈v1v2v8v1，v2v3v4v2，v4v5v6v4，v6v7v8v6之并 也可看成圈v1v2v3v4v5v6v7v8v1與圈v2v4v6v8v2之并 定理定理15.5 G是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且 為若干個邊不重的圈的并。 例例15.1 設(shè)G是非平凡的且非環(huán)的歐拉圖，證明：（1）(G)2.（2）對于G中任意兩個不同頂點u,v，都存在簡單 回路C含u和v.

10、 證證: （1）由定理15.5可知，eE(G)，存在圈C，e在C中，因而p(G-e)=p(G)，故e不是橋。 由e的任意性(G)2，即G是2邊-連通圖。 （2）u,vV(G)，uv，由G的連通性可知，u,v之間必存在路徑1， 設(shè)G=G-E(1)，則在G中u與v還必連通， 否則，u與v必處于G的不同的連通分支中， 這說明在1上存在G中的橋，這與（1）矛盾。 于是在G中存在u到v的路徑2，顯然1與2邊不重，這說明u,v處于12形成的簡單回路上。 設(shè)G為歐拉圖，一般來說G中存在若干條歐拉回路，下面介紹兩種求歐拉回路的算法。 1Fleury算法，能不走橋就不走橋： （1）任取v0V(G)，令P0=v0

11、.（2）設(shè)Pi=v0e1v1e2eivi已經(jīng)行遍，按下面方法來從 E(G)-e1,e2,ei中選取ei+1：（a）ei+1與vi相關(guān)聯(lián)； （b）除非無別的邊可供行遍，否則ei+1不應(yīng)該為Gi=G-e1,e2,ei中的橋。（3）當(dāng)（2）不能再進行時，算法停止。 當(dāng)算法停止時所得簡單回路Pm=v0e1v1e2emvm(vm=v0)為G中一條歐拉回路。 例例15.2 圖15.4(1)是給定的歐拉圖G。某人用Fleury算法求G中的歐拉回路時，走了簡單回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(觀看他的錯誤走法)，無法行遍了，試分析在哪步他犯了錯誤? v2e2v3e3v4

12、v2e2v3e3v4e14v9v2e2v3e3v4e14v9e10v2v2e2v3e3v4e14v9e10v2e1v1v2e2v3e3v4e14v9e10v2e1v1e8v8v2e2v3解 :此人行至v8時犯了能不走橋就不走橋的錯誤，因而他沒行出歐拉回路。 此時e9為該圖中的橋，而e7,e11均不是橋，他不應(yīng)該走e9，而應(yīng)該走e7或e11，他沒有走，所以犯了錯誤。 v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2正正確確行行法：法：V2e2v3e3v4e14v9e10v2e1v1e8v8e7v7V2e2v3e3v4e14v9e10v2e1v1e8v8e7v7e6v6V2e2v3

13、e3v4e14v9e10v2e1v1e8v8e7v7e6v6e5v5V2e2v3e3v4e14v9e10v2e1v1e8v8e7v7e6v6e5v5e4v4V2e2v3e3v4e14v9e10v2e1v1e8v8e7v7e6v6e5v5e4v4e13v6e12v9e11v8e9v2與七橋問題類似的就是一筆畫的判斷問題：從圖中某一結(jié)點出發(fā)，線可以相交但不能重合將圖畫完的問題。1859年，數(shù)學(xué)家哈密頓（Hamilton）提出一個問題：能否在正十二面體上求一條初級回路，使它含圖中所有頂點？他形象地將每個頂點比作一個城市，連接兩個頂點之間的邊看作城市之間的交通線。于是原始問題就變成了所謂的周游世界問題

14、：能否從某個城市出發(fā)沿交通線經(jīng)過每個城市一次并且僅一次，最后回到出發(fā)點？哈密頓自己做了肯定的回答。后人為了紀(jì)念這位數(shù)學(xué)家，將經(jīng)過圖中每個頂點一次且僅一次的回路稱為哈密頓回路，將有這種回路的圖稱為哈密頓圖。 15.2 15.2 哈密頓圖哈密頓圖 一、哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖 的定義 定義定義15.2 經(jīng)過圖（有向圖或無向圖）中所有頂點一次 且僅一次的通路稱為哈密頓通路哈密頓通路。經(jīng)過圖中所有頂點一次且僅一次的回路稱為哈密頓回路哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖半哈密頓圖。平凡圖是哈密頓圖。判斷一個圖是否為哈密

15、頓圖，就是判斷能否將圖中所有頂點都放置在一個初級回路（圈）上，這不是一件易事。與判斷一個圖是否為歐拉圖不一樣，到目前為止，人們還沒有找到哈密頓圖簡單的充分必要條件。定理定理15.6 設(shè)無向圖G=是哈密頓圖，對于任意V1 V，且V1 ，均有 p(G-V1)|V1| 證證 設(shè)C為G中任意一條哈密頓回路， 易知，當(dāng)V1中頂點在C上均不相鄰時，p(C-V1)達到最大值|V1|， 而當(dāng)V1中頂點在C上有彼此相鄰的情況時，均有p(C-V1)|V1|， 所以有p(C-V1)|V1|. 而C是G的生成子圖， 所以，有p(G-V1)p(C-V1)|V1|. 本定理的條件是哈密頓圖的必要條件，但不是充分條件?？梢?/p>

16、驗證彼得松圖滿足定理中的條件，但它不是哈密頓圖。當(dāng)然，若一個圖不滿足定理中的條件，它一定不是哈密頓圖 推論推論 設(shè)無向圖G=是半哈密頓圖，對于任意V1 V，且V1 ，均有 p(G-V1)|V1|+1 證證 設(shè)P是G中起于u終于v的哈密頓通路，令G=G(u,v)（在G的頂點u,v之間加新邊），易知G為哈密頓圖，由定理可知，p(G-V1)|V1|.而有p(G-V1)=p(G-V1-(u,v)p(G-V1)+1|V1|+1. 例例15.3 在圖15.6中給出的三個圖都是二部圖。它們中的那些是哈密頓圖？哪些是半哈密頓圖？為什么？ G1不是哈密頓圖，也不是半哈密頓圖。 G2是半哈密頓圖 G3是哈密頓圖

17、baegjckhfid為G2中一條哈密頓通路 如：abcdgihjefa 一般情況下，設(shè)二部圖G=，|V1|V2|，且|V1|2，|V2|2， 1）若G是哈密頓圖，則|V1|=|V2|。2）若G是半哈密頓圖，則|V2|=|V1|+1 3）若|V2|V1|+2，則G不是哈密頓圖，也不是半哈密頓圖。 例例15.4 設(shè)G是n階無向連通圖。證明：若G中有割點或橋，則G不是哈密頓圖。定理定理15.7 設(shè)G是n階無向簡單圖，若對于G中任意不相鄰的頂點vi,vj，均有 d(vi)+d(vj)n-1 則G中存在哈密頓通路。證證 首先證明G是連通圖。 否則G至少有兩個連通分支，設(shè)G1,G2是階數(shù)為n1,n2的兩

18、個連通分支， 設(shè)v1V(G1)，v2V(G2)，因為G是簡單圖，所以 dG(v1)+dG(v2)=dG1(v1)+dG2(v2)n1-1+n2-1n-2 這與條件矛盾，所以G必為連通圖。 下面證G中存在哈密頓通路。 設(shè)=v1v2vl為G中用“擴大路徑法”得到的“極大路徑”， 即的始點v1與終點vl不與外的頂點相鄰。 顯然有l(wèi)n 1)若l=n，則為G中哈密頓通路。 2)若ln，這說明不是哈密頓通路，即G中還存在著外的頂點。但可以證明G中存在過上所有頂點的圈。 (a)若v1與vl相鄰，即(v1,vl)E(G)，則(v1,vl)為滿足要求的圈。 (b)若v1與vl不相鄰， 設(shè)v1與上的 相鄰（k2，

19、否則d(v1)+d(vl)1+l-2=l-1n-1，這與（15.1）矛盾）， 此時，vl至少與 相鄰的頂點 之一相鄰（否則，d(v1)+d(vl)k+l-2-(k-1)=l-1n-1）， 設(shè)vl與 相鄰（2rk），見圖(1)所示。于是，回路C= 過上的所有頂點。 (c)下面證明存在比更長的路徑。 因為ln，所以C外還有頂點，由G的連通性可知，存在vl+1V(G)-V(C)與C上某頂點vt相鄰，見圖(2)所示。 刪除邊（vt-1,vt）得路徑= 比長度大1， 對上的頂點重新排序，使其成為=v1v2vlvl+1， 對重復(fù)a）c），在有限步內(nèi)一定得到G的哈密頓通路。 推論推論 設(shè)G為n(n3)階無向

20、簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有 d(vi)+d(vj)n 則G中存在哈密頓回路，從而G為哈密頓圖。 證證 由定理15.7可知，G中存在哈密頓通路，設(shè)=v1v2vn為G中一條哈密頓通路，若v1與vn相鄰，設(shè)邊e=(v1,vn)，則e為G中哈密頓回路。若v1與vn不相鄰，應(yīng)用（15.2），同定理15.7證明中的（2）類似，可證明存在過上各頂點的圈，此圈即為G中的哈密頓回路。 定理定理15.8 設(shè)u,v為n階無向簡單圖G中兩個不相鄰的頂點，且d(u)+d(v)n，則G為哈密頓圖當(dāng)且僅當(dāng)G(u,v)為哈密頓圖（u,v）是加的新邊）。 例例15.5 在某此國際會議的預(yù)備會議中，共

21、有8人參加，他們來自不同的國家。已知他們中任何兩個無共同語言的人中的每一個，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個人排在圓桌旁，使其任何人都能與兩邊的人交談。 解解 設(shè)8個人分別為v1,v2,v8，作無向簡單圖G=，其中V=v1,v2,v8, vi,vjV，且ij，若vi與vj有共同語言，就在vi,vj之間連無向邊（vi,vj），由此組成邊集合E，則G為8階無向簡單圖， viV，d(vi)為與vi有共同語言的人數(shù)。由已知條件可知， vi,vjV且ij，均有d(vi)+d(vj)8.由定理15.7的推論可知，G中存在哈密頓回路，設(shè)C= 為G中一條哈密頓回路，按這條回路的順序安排座

22、次即可。 從此例更可以看出，哈密頓圖是能將圖中所有頂點都能安排在某個初級回路上的圖。 定理定理15.9 若D為n（n2）階競賽圖，則D中具有哈密頓通路。 證證 對n作歸納法。n=2時，D的基圖為K2，結(jié)論成立。 設(shè) n=k時結(jié)論成立?，F(xiàn)在設(shè)n=k+1.設(shè) V(D)=v1,v2,vk,vk+1。 由歸納假設(shè)可知，D1存在哈密頓通路，設(shè)1=v1v2vk為其中一條。 令D1=D-vk+1，易知D1為k階競賽圖，下面證明vk+1可擴到1中去。 若存在vr（1rk），有E (D)，i=1,2,r-1，而E(D)，見圖1所示 則=v1v2vr-1vk+1vrvk為D中哈密頓通路。 否則, i1,2,k，均

23、有E(D)，見圖2 則=為D中哈密頓通路。 例例15.6 如圖所示的三個圖中哪些是哈密頓圖？哪些是半哈密頓圖？ 1）為哈密頓圖 2）取V1=a,b,c,d,e，從圖中刪除V1得7個連通分支，由定理15.6和推論可知，不是哈密頓圖，也不是半哈密頓圖。 3）取V1=b,e,h，從圖中刪除V1得4個連通分支，由定理15.6可知，它不是哈密頓圖。但存在哈密頓通路 15.3 帶權(quán)圖與貨郎擔(dān)問題 定義定義15.3 給定圖G=（G為無向圖或有向圖），設(shè)W：ER（R為實數(shù)集），對G中任意的邊e=(vi,vj)（G為有向圖時，e=），設(shè)W(e)=wij，稱實數(shù)wij為邊e上的權(quán)，并將wij標(biāo)注在邊e上，稱G為帶權(quán)圖帶權(quán)圖，此時常將帶權(quán)圖G記作. 設(shè)GG，稱 W(e)為G的權(quán)，并記作W(G)，即 W(G)= W(e). 設(shè)有n個城市，城市之間均有道路，道路的長度均大于或等于0，可能是（對應(yīng)關(guān)聯(lián)的城市之間無交通線）。一個旅行商從某個城市出發(fā)，要經(jīng)過每個城市一次且僅一次，最后回到出發(fā)的城市，問他如何走才能使他走的路線最短？這就是著名的旅行商問題或貨郎擔(dān)問題。這個問題可化歸為如下的圖論問題。 設(shè)G=，為一個n階