離散數(shù)學(xué)-E圖和H圖省公開課一等獎(jiǎng)全國示范課微課金獎(jiǎng)

第八章

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

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

∪C起、終點(diǎn)，于是C

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

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

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

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

因?yàn)樗且粋€(gè)含有奇數(shù)個(gè)頂點(diǎn)二分圖。所以不可能有H回路。？因?yàn)槎謭D中回路一定是偶數(shù)條邊。(定理5.5.2)5/5/202412離散數(shù)學(xué)第12頁H圖一個(gè)必要條件定理8.2.1假如G是一個(gè)H圖，則對(duì)V(G)任何非空真子集S，均成立：(G–S)|S|(8.1)

證實(shí)：設(shè)C是GH回路(G全部頂點(diǎn)都在C上)，則顯然有(C–S)|S|成立，其中SV(G)。因?yàn)镃–S是G–S生成子圖，C

–S連通分支數(shù)不比G–S少，所以：

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

則G是H圖。證實(shí)：若滿足(8.2)簡單圖不是H圖，令G(p,q)是其中邊數(shù)最多一個(gè)圖。顯然，G≠Kp。？因?yàn)镵p一定是H圖。

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

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

vp，其中u=v1,v=vp。令S={vi|v1vi∈E(G)}，T={vi|vi-1vp∈E(G)}。(S是鄰接u點(diǎn)集合，T是位于鄰接v頂點(diǎn)后面頂點(diǎn)集合)由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離散數(shù)學(xué)第18頁H圖一個(gè)充分條件證實(shí)：……|S∪T|＜p。而S∩T=。若不然，設(shè)vi∈S∩T,則存在v1v2

vi–1vpvp–1

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

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

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

p(8.3)頂點(diǎn)u,v,若uv

E(A),則將邊uv加入到A中，得到A+uv.如此重復(fù)加邊，直到全部滿足(8.3)點(diǎn)都鄰接，最終所得圖稱為A閉包，記為?。因?yàn)橐粋€(gè)圖閉包是唯一，所以求閉包時(shí)加邊次序能夠任意。5/5/202423離散數(shù)學(xué)第23頁求一個(gè)圖閉包例：求右圖閉包。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離散數(shù)學(xué)第24頁H圖充要條件引理8.2.1設(shè)G是p階簡單圖，u與v是G中兩個(gè)不鄰接頂點(diǎn)且滿足：d(u)+d(v)

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

vp

v1,其中v1=u,v2=v。5/5/202425離散數(shù)學(xué)第25頁H圖充要條件證實(shí)：…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)假設(shè)在頂點(diǎn)v3,v4,

vp–1中有r個(gè)頂點(diǎn)：vi1,vi2,

vir與u鄰接，則

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

vi1+1,vi2+1,

vir+1(8.5)中某個(gè)頂點(diǎn)vij+1鄰接。若p≧4，且在G中u,v分別只與vp和v3鄰接，則dG(u)+dG(v)=2﹤p，與條件矛盾。故要么u與{v3,…,vp-1}中r個(gè)頂點(diǎn)鄰接，要么v與{v4,…vp}中r個(gè)頂點(diǎn)鄰接，且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離散數(shù)學(xué)第26頁H圖充要條件證實(shí)：…頂點(diǎn)v必與

(8.5)中某頂點(diǎn)vij+1相鄰接。假如v不與(8.5)中任何頂點(diǎn)鄰接，則有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離散數(shù)學(xué)第27頁A是H圖當(dāng)且僅當(dāng)?是H圖定理8.2.3：p階簡單圖A是H圖當(dāng)且僅當(dāng)?是H圖。證實(shí)：設(shè)圖A是H圖，則顯然?也是H圖。反之，設(shè)?是H圖，若A=?，則A是H圖；若A≠?，則存在ei

E(A),i=1,

,t,t

1，使得A+e1+e2+

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

p，且u與v在A中不鄰接，因?yàn)?是H圖，由引理8.2.1知?–et仍是H圖，重復(fù)應(yīng)用該引理，可知A是H圖。5/5/202428離散數(shù)學(xué)第28頁用頂點(diǎn)度序列判斷H圖定理8.2.4：設(shè)p(

3)階簡單圖G各頂點(diǎn)度數(shù)序列為d1

d2

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

(v)記?中v度數(shù)。設(shè)u和v是?中不鄰接且度數(shù)和為最大兩個(gè)點(diǎn)，不妨假設(shè)d

(u)

d

(v)。因?yàn)閡v

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

(u)+d

(v)<p，于是d

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

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

(u)<p/2。設(shè)為?中不與v鄰接頂點(diǎn)數(shù)，則d

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

(v)。而p–1

d

(u)+d

(v)，所以，

d

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

,vi

(m，u=vi

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

d(vi

)=m。因?yàn)閂(G)=V(?)，所以G中也最少有m個(gè)頂點(diǎn)度數(shù)小于m，又因?yàn)镚度數(shù)序列以遞增次序排列，所以：dmm。5/5/202430離散數(shù)學(xué)第30頁用頂點(diǎn)度序列判斷H圖證實(shí)：……dmm。

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

,vj

，(v=vj

)，其中由v假定可設(shè)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個(gè)頂點(diǎn)度數(shù)均小于p–m，即dp–m<p–m。這說明存在m＜p/2使得dmm和dp–m＜p–m都成立，此與已知條件矛盾，于是?=Kp。定理得證.∵d(v)+d(u)＜p，且d(u)=m個(gè)頂點(diǎn)加上頂點(diǎn)u5/5/202431離散數(shù)學(xué)第31頁§8.3應(yīng)用[旅行推銷員問題]設(shè)有n個(gè)城市C1,

,Cn,某推銷員從C1出發(fā)推銷產(chǎn)品，每個(gè)城市都要走到一次，最終回到C1。已知每兩個(gè)城市之間距離，問怎樣安排行程才能使總旅程最短？[等價(jià)圖論語言描述]在賦權(quán)完全圖中求權(quán)最小H回路，簡稱為最優(yōu)回路。5/5/202432離散數(shù)學(xué)第32頁求最優(yōu)回路最優(yōu)回路是可解。最簡單方法就是窮舉法，即找出KP全部H回路，然后從中選出最小者即可。可是對(duì)n(4)個(gè)頂點(diǎn)完全圖，全部權(quán)可能不等H回路共有(n–1)!種，其時(shí)間復(fù)雜度為O(n!)。所以當(dāng)N較大時(shí)，用窮舉法求解是不可想象。怎樣用較快算法來求最優(yōu)回路，是人們正在研究且還未最終處理問題。人們開始轉(zhuǎn)而求其次，即尋找一個(gè)算法能較快地求出一個(gè)較優(yōu)但不一定是最優(yōu)解。5/5/202433離散數(shù)學(xué)第33頁逐次改進(jìn)法逐次改進(jìn)法這是一個(gè)近似解法。先找賦權(quán)完全圖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。重復(fù)應(yīng)用，直到找不出滿足(8.6)式Cij為止。逐次改進(jìn)法不一定得到最優(yōu)回路。5/5/202434離散數(shù)學(xué)第34頁圖示：逐次改進(jìn)法任意一條H回路C如圖所表示。v1vj–1vj–2vivi+1vi–1vjvj+1v2vn現(xiàn)在找到w(vi–1vj–1)+w(vivj)<w(vi–1vi)+w(vj–1vj)于是將C改進(jìn)為Cij.顯然改進(jìn)后回路依然是H回路且權(quán)值較低。5/5/202435離散數(shù)學(xué)第35頁求下列圖最優(yōu)回路首先選C=v1v2v3v4v5v6v1w(C)=14+15+8+13+1+5=56v5v6v1v2v3v41381514517651191381210