第八章

E圖和H圖5/5/20241離散數學第1頁§8.1七橋問題與E圖七橋問題：有四塊陸地與連結它們七座橋，問能否從這四塊陸地中任意一塊出發，經過每一座橋恰好一次，最終回到原地？5/5/20242離散數學第2頁一筆畫該問題等價于“能否一筆畫出下列圖？”Euler證實了，七橋問題是無解。圖中：頂點表示陸地，邊表示陸地之間橋。5/5/20243離散數學第3頁E圖定義8.1.1：設G是一個圖，經過G每一條邊鏈稱為E鏈；閉E鏈稱為E閉鏈。假如G中存在E鏈，稱G為半E圖；假如G中存在E閉鏈，稱G為E圖。下面討論中設G是非平凡連通圖。5/5/20244離散數學第4頁無奇點連通圖是E圖引理8.1.1：連通圖G中無奇點，則G是E圖。證實：設G是無奇點連通圖且G不是E圖。在全部連通無奇點非E圖中，選一個邊最少圖G。因G每個頂點度最少是2，從而G必含閉鏈。為何？

若G不含回路，則G是樹。我們知道樹中最少有兩個懸掛點（奇點）。矛盾，所以G中一定含有回路。而回路就是閉鏈。假如回路之間有重復出現邊，我們能夠去掉重復者，使每條邊僅出現一次，這么就得到了一條閉鏈。所以G中必含閉鏈。設C是G中最長閉鏈，由假設C不是E閉鏈，于是G–E(C)中必含非平凡連通分支G且G中無奇點，顯然q(G)<q(G)。為何？故G必是E圖(由G和C選法)。于是G有一條E閉鏈C。因G連通，C和C必有公共點v,以v作為C

∪C起、終點，于是C

∪C是G一條閉鏈且長度大于C長度，這與C假設矛盾。故G是E圖。因G不是E圖。G無奇點且C無奇點。5/5/20245離散數學第5頁C’CGvGG中含閉鏈圖示C∪C’是一條閉鏈圖示5/5/20246離散數學第6頁E圖是無奇點連通圖引理8.1.1’：E圖是無奇點連通圖。證實：設G是E圖，C是G一條E閉鏈。因為G連通且C是含G每邊恰一次閉鏈，所以，C中每個點都既是起點也是終點。于是，從C上任一點u出發，每經過一個頂點v，就有兩條與v關聯邊出現(一進一出)。這么，C上每個頂點，也即G每個頂點度均為偶數，故G中無奇點。由引理8.1.1和8.1.1’，我們有：定理8.1.1：連通圖G是E圖當且僅當G中無奇點。5/5/20247離散數學第7頁半E圖中最多有兩個奇點推論8.1.1：G是半E圖當且僅當G中最多有兩個奇點。證實：(必要性)設G是半E圖，C是G一條E鏈。除起點與終點外，C中每個頂點度均為偶數。又因G連通，故G最多有兩個奇點。

(充分性)設G最多只有兩個奇點。若G無奇點，則由定理8.1.1知，G為E圖，亦為半E圖；若G有兩個奇點，設為u和v,則在G中加入e=uv邊，使G中無奇點。由定理8.1.1知，G+e為E圖，即G+e含E閉鏈C，于是C–e組成G一條E鏈，所以G是半E圖。5/5/20248離散數學第8頁哥尼斯城堡橋不是E圖半E圖5/5/20249離散數學第9頁§8.2周游世界問題與H圖周游世界問題:

用一個正十二面體二十個頂點來代表二十個城市，要求從其中任一頂點出發，沿著這個正十二面體棱走遍這二十個頂點，且每個城市只經過一次，最終回到起點。該問題等價于“能否從下列圖找一條含全部頂點回路？”5/5/202410離散數學第10頁H圖定義8.2.1：

設G是一個圖，含G每個頂點通路稱為H通路；起點與終點重合H通路稱為H回路；假如G中存在H回路，稱G為H圖；若G中存在H通路，稱G為半H圖；說明：H圖必是半H圖，反之不然。?5/5/202411離散數學第11頁Herschel圖該圖是半H圖。

因為它是一個含有奇數個頂點二分圖。所以不可能有H回路。？因為二分圖中回路一定是偶數條邊。(定理5.5.2)5/5/202412離散數學第12頁H圖一個必要條件定理8.2.1假如G是一個H圖，則對V(G)任何非空真子集S，均成立：(G–S)|S|(8.1)

證實：設C是GH回路(G全部頂點都在C上)，則顯然有(C–S)|S|成立，其中SV(G)。因為C–S是G–S生成子圖，C

–S連通分支數不比G–S少，所以：

(G–S)(C–S)|S|故(8.1)式成立。5/5/202413離散數學第13頁G(H圖)C(H回路）定理8.2.1證實圖示5/5/202414離散數學第14頁一個非H圖判定取S為紅色點集。|S|=5。(G–S)=6＞|S|依據定理8.2.1，此圖不是H圖。5/5/202415離散數學第15頁注意：這只是必要條件注意定理8.2.1只是判斷H圖必要條件，有圖即使滿足條件，卻不是H圖。如右邊Peterson圖不是H圖。可是它卻滿足定理8.2.1條件。Peterson圖Peterson圖是半H圖而不是H圖。5/5/202416離散數學第16頁H圖一個充分條件定理8.2.2：設G是p(3)階簡單圖。假如G中任何兩個不鄰接頂點u和v均滿足：d(u)+d(v)p(8.2)

則G是H圖。證實：若滿足(8.2)簡單圖不是H圖，令G(p,q)是其中邊數最多一個圖。顯然，G≠Kp。？因為Kp一定是H圖。

設u，v是G中不鄰接兩個頂點。由G假設可知，G+uv是H圖，且其中H回路必含uv。于是，G中存在從u到vH通路P:v1v2

vp，其中u=v1,v=vp。5/5/202417離散數學第17頁H圖一個充分條件證實：…H通路P:v1v2

vp，其中u=v1,v=vp。令S={vi|v1vi∈E(G)}，T={vi|vi-1vp∈E(G)}。(S是鄰接u點集合，T是位于鄰接v頂點后面頂點集合)由G是簡單圖知，|S|=d(u),|T|=d(v)。又由v1與vp不鄰接有S{v2,

,vp–1}以及T{v3,

,vp}，從而S∪T{v2,v3,

,vp}，|S∪T|＜p。5/5/202418離散數學第18頁H圖一個充分條件證實：……|S∪T|＜p。而S∩T=。若不然，設vi∈S∩T,則存在v1v2

vi–1vpvp–1

viv1將是GH回路。此與G不是H圖假設相矛盾。u=v1v2vi-1vivi+1vp-1vp=vG+uv中H回路G中H回路5/5/202419離散數學第19頁H圖一個充分條件定理8.2.2：設G是p(3)階簡單圖。假如G中任何兩個不鄰接頂點u和v均滿足：d(u)+d(v)p(8.2)

則G是H圖。證實：……|S|=d(u),|T|=d(v)，|S∪T|＜p，S∩T=，于是p≤d(v1)+d(vp)=|S|+|T|=|S∪T|＜p，此為矛盾。故結論成立。5/5/202420離散數學第20頁定理8.2.2條件不是必要例以下列圖是H圖但任意兩頂點度之和為4,而P=55/5/202421離散數學第21頁H圖又一個充分條件推論8.2.1設G是p(

3)階簡單圖，假如(G)P/2,則G是H圖。證實：任取u,v∈V(G),由題設都有d(u)+d(v)p/2+p/2=p所以，由定理8.2.2知，G是H圖。5/5/202422離散數學第22頁圖閉包定義8.2.2：設A是p階圖，對A中滿足：d(u)+d(v)

p(8.3)頂點u,v,若uv

E(A),則將邊uv加入到A中，得到A+uv.如此重復加邊，直到全部滿足(8.3)點都鄰接，最終所得圖稱為A閉包，記為?。因為一個圖閉包是唯一，所以求閉包時加邊次序能夠任意。5/5/202423離散數學第23頁求一個圖閉包例：求右圖閉包。v1v2v3v4v5v6d(v1)+d(v4)≥6,連接v1和v4。d(v3)+d(v5)≥6,連接v3和v5。d(v3)+d(v6)≥6,連接v3和v6。d(v4)+d(v6)≥6,連接v4和v6。d(v4)+d(v2)≥6,連接v4和v2。d(v5)+d(v2)≥6,連接v5和v2。d(v6)+d(v2)≥6,連接v6和v2。存在A=?情形：⑴A=Kp,⑵A中無滿足條件邊可加,如圖G。G5/5/202424離散數學第24頁H圖充要條件引理8.2.1設G是p階簡單圖，u與v是G中兩個不鄰接頂點且滿足：d(u)+d(v)

p于是，G是H圖當且僅當G+uv是H圖。證實：設G是H圖，則G+uv顯然也是H圖。反之，假設G+uv是H圖，假如其中一條H回路不含uv，則G必是H圖；假如G+uv中全部H回路均含邊uv，設其中有一條回路為C：v1v2v3v4

vp

v1,其中v1=u,v2=v。5/5/202425離散數學第25頁H圖充要條件證實：…C：v1v2

vp

v1，其中v1=u，v2=v。記；d

(u)=dG+uv(u)=dG(u)+1，d

(v)=dG+uv(v)=dG(v)+1，則有d

(u)+d

(v)=dG(u)+dG(v)+2p+2(8.4)假設在頂點v3,v4,

vp–1中有r個頂點：vi1,vi2,

vir與u鄰接，則

dG+uv(u)=r+2(u與v2,vp鄰接)。于是，頂點v必與r個頂點

vi1+1,vi2+1,

vir+1(8.5)中某個頂點vij+1鄰接。若p≧4，且在G中u,v分別只與vp和v3鄰接，則dG(u)+dG(v)=2﹤p，與條件矛盾。故要么u與{v3,…,vp-1}中r個頂點鄰接，要么v與{v4,…vp}中r個頂點鄰接，且r≧

(p-2)/2.∵dG(u)=r+1,dG(v)=r+1∴dG(u)+dG(v)=2r+2≧p,故r≧

(p-2)/2

5/5/202426離散數學第26頁H圖充要條件證實：…頂點v必與

(8.5)中某頂點vij+1相鄰接。假如v不與(8.5)中任何頂點鄰接，則有dG+uv(v)

(p–1)–r=(p–1)–(dG+uv(u)–2)所以，dG+uv(v)+dG+uv(u)p+1，此與(8.4)矛盾。所以，C

=v1vijvij–1

v3v2vij+1

vpv1就是G一條H回路(C

恰不包含邊uv)。即G為H圖。v2(v)vpv1vij–1vij+1vijv1(u)G+uvH回路

GH回路

P-1是G最大度5/5/202427離散數學第27頁A是H圖當且僅當?是H圖定理8.2.3：p階簡單圖A是H圖當且僅當?是H圖。證實：設圖A是H圖，則顯然?也是H圖。反之，設?是H圖，若A=?，則A是H圖；若A≠?，則存在ei

E(A),i=1,

,t,t

1，使得A+e1+e2+

+et=?。設ei=uv，由閉包定義知，d(u)+d(v)

p，且u與v在A中不鄰接，因為?是H圖，由引理8.2.1知?–et仍是H圖，重復應用該引理，可知A是H圖。5/5/202428離散數學第28頁用頂點度序列判斷H圖定理8.2.4：設p(

3)階簡單圖G各頂點度數序列為d1

d2

dp，于是，若對任何m<p/2，或者dm>m，或者dp–m≧p–m，則G是H圖。證實:我們將證實?=Kp，從而由定理8.2.3有G是H圖。(由推論8.2.1知Kp是H圖)假設?≠Kp，用d

(v)記?中v度數。設u和v是?中不鄰接且度數和為最大兩個點，不妨假設d

(u)

d

(v)。因為uv

E(?)，所以由閉包定義有d

(u)+d

(v)<p，于是d

(u)<p/2。取m=d

(u)<p/2。5/5/202429離散數學第29頁用頂點度序列判斷H圖證實：……m=d

(u)<p/2。設為?中不與v鄰接頂點數，則d

(v)=(p–1)–，即=(p–1)–d

(v)。而p–1

d

(u)+d

(v)，所以，

d

(u)=m。即?中不與v鄰接頂點數最少為m，記為：vi1,vi2,

,vi

(m，u=vi

)。其中由u最大性不妨設d(vi1)d(vi2)

d(vi

)=m。因為V(G)=V(?)，所以G中也最少有m個頂點度數小于m，又因為G度數序列以遞增次序排列，所以：dmm。5/5/202430離散數學第30頁用頂點度序列判斷H圖證實：……dmm。

一樣，設在?中不與u鄰接頂點數為，于是，=(p–1)–d’(u)=(p–1)–m。設這些頂點分別為vj1,vj2,

,vj

，(v=vj

)，其中由v假定可設d(vj1)d(vj2)

d(vj

)=d(v)<p–m。又m<p/2，所以，m+(m–p)<0，即d(u)＜p–m。從而G中共有(p–m–1)+1=p–m個頂點度數均小于p–m，即dp–m<p–m。這說明存在m＜p/2使得dmm和dp–m＜p–m都成立，此與已知條件矛盾，于是?=Kp。定理得證.∵d(v)+d(u)＜p，且d(u)=m個頂點加上頂點u5/5/202431離散數學第31頁§8.3應用[旅行推銷員問題]設有n個城市C1,

,Cn,某推銷員從C1出發推銷產品，每個城市都要走到一次，最終回到C1。已知每兩個城市之間距離，問怎樣安排行程才能使總旅程最短？[等價圖論語言描述]在賦權完全圖中求權最小H回路，簡稱為最優回路。5/5/202432離散數學第32頁求最優回路最優回路是可解。最簡單方法就是窮舉法，即找出KP全部H回路，然后從中選出最小者即可。可是對n(4)個頂點完全圖，全部權可能不等H回路共有(n–1)!種，其時間復雜度為O(n!)。所以當N較大時，用窮舉法求解是不可想象。怎樣用較快算法來求最優回路，是人們正在研究且還未最終處理問題。人們開始轉而求其次，即尋找一個算法能較快地求出一個較優但不一定是最優解。5/5/202433離散數學第33頁逐次改進法逐次改進法這是一個近似解法。先找賦權完全圖G一條H回路，記為C=v1v2

vnv1,假如w(vi–1vj–1)+w(vivj)<w(vi–1vi)+w(vj–1vj)(8.6)

則用H回路Cij=v1v2

vi–1vj–1vj–2

vi+1vivjvj+1

vnv1代替C。重復應用，直到找不出滿足(8.6)式Cij為止。逐次改進法不一定得到最優回路。5/5/202434離散數學第34頁圖示：逐次改進法任意一條H回路C如圖所表示。v1vj–1vj–2vivi+1vi–1vjvj+1v2vn現在找到w(vi–1vj–1)+w(vivj)<w(vi–1vi)+w(vj–1vj)于是將C改進為Cij.顯然改進后回路依然是H回路且權值較低。5/5/202435離散數學第35頁求下列圖最優回路首先選C=v1v2v3v4v5v6v1w(C)=14+15+8+13+1+5=56v5v6v1v2v3v41381514517651191381210