1第十一章幾種特殊的圖主要內容歐拉圖哈密頓圖二部圖與匹配平面圖著色.1第十一章幾種特殊的圖主要內容.1211.1

歐拉圖歷史背景：哥尼斯堡七橋問題.211.1歐拉圖歷史背景：哥尼斯堡七橋問題.23歐拉圖定義定義11.1圖(無向圖或有向圖)中所有邊恰好通過一次且經過所有頂點的通路稱為歐拉通路.圖中所有邊恰好通過一次且經過所有頂點的回路稱為歐拉回路．具有歐拉回路的圖稱為歐拉圖.具有歐拉通路而無歐拉回路的圖稱為半歐拉圖．說明：規定平凡圖為歐拉圖.環不影響圖的歐拉性..3歐拉圖定義定義11.1圖(無向圖或有向圖)中所有邊恰好34歐拉圖實例歐拉圖不是半歐拉圖歐拉圖不是半歐拉圖.4歐拉圖實例歐拉圖不是半歐拉圖歐拉圖不是半歐拉圖.45歐拉圖的判別法定理11.1(1)無向圖G是歐拉圖當且僅當G是連通的且沒有奇度頂點．(2)無向圖G是半歐拉圖當且僅當G是連通的且恰有兩個奇度頂點．(3)有向圖D是歐拉圖當且僅當D是強連通的且每個頂點的入度等于出度．(4)有向圖D是半歐拉圖當且僅當D是單向連通的且恰有兩個奇度頂點,其中一個頂點的入度比出度大1,另一個頂點出度比入度大1,其余頂點的入度等于出度．例1

設G是非平凡的歐拉圖，則(G)2.證只需證明G的任意一條邊e都不是橋.設C是一條歐拉回路,e在C上，因而Ge仍是連通的，故e不是橋．.5歐拉圖的判別法定理11.1(1)無向圖G是歐拉圖當且56Fleury算法算法：(1)任取v0V(G),令P0=v0,i=0.(2)設Pi=v0e1v1e2…eivi，

如果E(G)-{e1,e2,…,ei}中沒有與vi關聯的邊,則計算結束;

否則按下面方法從E(G){e1,e2,…,ei}中選取ei+1：

(a)ei+1與vi關聯；

(b)除非無別的邊可供選擇,否則ei+1不應為

G{e1,e2,…,ei}

中的橋.

設ei+1=(vi,vi+1),把ei+1vi+1加入Pi.(3)令i=i+1,返回(2)..6Fleury算法算法：.67實例一筆畫出一條歐拉回路.7實例一筆畫出一條歐拉回路.78實例一筆畫出一條歐拉回路.8實例一筆畫出一條歐拉回路.8911.2

哈密頓圖歷史背景：哈密頓周游世界問題

(1)(2).911.2哈密頓圖歷史背景：哈密頓周游世界問題910哈密頓圖與半哈密頓圖定義11.2經過圖中所有頂點一次且僅一次的通路稱作哈密頓通路.經過圖中所有頂點一次且僅一次的回路稱作哈密頓回路.具有哈密頓回路的圖稱作哈密頓圖.具有哈密頓通路且無哈密頓回路的圖稱作半哈密頓圖.規定:平凡圖是哈密頓圖.哈密頓圖半哈密頓圖哈密頓圖例不是.10哈密頓圖與半哈密頓圖定義11.2經過圖中所有頂點一次且1011無向哈密頓圖的一個必要條件定理11.2

設無向圖G=<V,E>是哈密頓圖，對于任意V1V且V1，均有p(GV1)|V1|證設C為G中一條哈密頓回路(1)p(CV1)|V1|(2)p(GV1)

p(CV1)|V1|（因為CG）推論設無向圖G=<V,E>是半哈密頓圖，對于任意的V1V且V1均有

p(GV1)|V1|+1證設為從u到v的哈密頓通路，令G=G(u,v)，則G為哈密頓圖.于是

p(GV1)=p(GV1(u,v))

p(GV1)+1|V1|+1.11無向哈密頓圖的一個必要條件定理11.2設無向圖G=<1112例題例2判斷下面的圖是不是哈密頓圖,是不是半哈密頓圖.解(a)取V1={a,f},p(GV1)=|{b,c,d,e}|=4>|V1|=2,不是哈密頓圖，也不是半哈密頓圖．(b)取V1={a,g,h,i,c},p(GV1)=|{b,e,f,j,k,d}|=6>|V1|=5,不是哈密頓圖.而baegjckhfid是一條哈密頓通路,是半哈密頓圖．(c)abcdgihjefa是一條哈密頓回路，是哈密頓圖．.12例題例2判斷下面的圖是不是哈密頓圖,是不是半哈密頓1213例題例3設G為n階無向連通簡單圖，若G中有割點或橋，則G不是哈密頓圖.證設v為割點，則p(Gv)2>|{v}|=1.K2有橋，它顯然不是哈密頓圖.除K2外，其他有橋的連通圖均有割點..13例題例3設G為n階無向連通簡單圖，若G中有割點或橋，1314無向哈密頓圖的一個充分條件定理11.3

設G是n階無向簡單圖,若對于任意不相鄰的頂點vi,vj,均有

d(vi)+d(vj)

n1()則G中存在哈密頓通路.推論設G為n(n3)階無向簡單圖,若對于G中任意兩個不相鄰的頂點vi,vj,均有

d(vi)+d(vj)

n

（）則G中存在哈密頓回路..14無向哈密頓圖的一個充分條件定理11.3設G是n階無向1415判斷是否為哈密頓圖判斷是否為(半)哈密頓圖至今還是一個難題.(1)觀察出一條哈密頓回路或哈密頓通路.(2)證明滿足充分條件.(3)證明不滿足必要條件.例4

證明右圖(周游世界問題)是哈密頓圖證a

b

c

d

e

f

g

h

i

j

k

l

m

no

p

q

r

s

t

a是一條哈密頓回路.注意，此圖不滿足定理11.3推論的條件.例5

完全圖Kn(n3)是哈密頓圖.證

任何兩個頂點u,v，d(u)+d(v)=2(n1)

n.15判斷是否為哈密頓圖判斷是否為(半)哈密頓圖至今還是一個1516貨郎問題貨郎問題:有n個城市,給定城市之間道路的長度(長度可以為,對應這兩個城市之間無交通線).貨郎從某個城市出發,要經過每個城市一次且僅一次,最后回到出發的城市,問如何走才能使他走的路線最短?圖論方法描述如下:設G=<V,E,W>為一個n階完全帶權圖Kn,各邊的權非負,且可能為.求G中的一條最短的哈密頓回路.不計出發點和方向,Kn(n3)中有(n1)!/2條不同的哈密頓回路.16貨郎問題貨郎問題:有n個城市,給定城市之間道路的長度1617

解C1=a

b

c

d

a,W(C1)=10

C2=a

b

d

c

a,W(C2)=11

C3=a

c

b

d

a,W(C3)=9最短

例6

求下面帶權圖K4中最短哈密頓回路.

例題.17解C1=abcda,W(C171811.3二部圖與匹配定義11.3

設G=<V,E>為一個無向圖,若能將V分成V1和V2(V1V2=V,V1V2=),使得G中的每條邊的兩個端點都是一個屬于V1,另一個屬于V2,則稱G為二部圖(或稱二分圖,偶圖),稱V1和V2為互補頂點子集,常將二部圖G記為<V1,V2,E>.又若G是簡單二部圖,V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖,記為Kr,s,其中r=|V1|,s=|V2|..1811.3二部圖與匹配定義11.3設G=<V,E>1819實例例K2,3K3,3.19實例例K2,3K3,3.1920二部圖的判別法定理11.4

無向圖G=<V1,V2,E>是二部圖當且僅當G中無奇圈.證

必要性.若G中無圈,結論成立.若G中有圈,設G中的一個圈C=v1v2vlv1,l≥2.不妨設v1V1,v1,v2,,vl

依次交替屬于V1,

V2且vlV2,因而l為偶數.得證C為偶圈．充分性.不妨設G為連通圖,否則可對每個連通分支進行討論,

孤立點可根據需要分屬V1和V2.設v0為G中任意一個頂點,令V1={v|vV(G)d(v0,v)為偶數}V2={v|vV(G)d(v0,v)為奇數}d(v0,v)是v0到v的最短路徑的邊數(每條邊的權為1).V1，V2,V1V2=,V1V2=V(G).要證V1中任意兩點不相鄰．.20二部圖的判別法定理11.4無向圖G=<V1,V2,E2021證明假若存在vi,vjV1相鄰,記e=(vi,vj),設v0到vi,vj的最短路徑分別為i,j,由i,j和e構成一條長度為奇數的回路.這條回路可能是一條復雜回路,可以分解成若干由i,j共有的邊構成的回路(實際上是每條邊重復一次的路徑)和由i,j不共有的邊及e構成的圈.由i,j共有的邊構成的回路的長度為偶數,故在由i,j不共有的邊(可以還包括e)構成的圈中一定有奇圈,這與已知條件矛盾.得證V1中任意兩頂點不相鄰.由對稱性,V2中也不存在相鄰的頂點,得證G為二部圖．.21證明假若存在vi,vjV1相鄰,記e=(vi,vj)2122最大匹配定義11.4設G=<V1,V2,E>為二部圖,ME,如果M中的任意兩條邊都不相鄰,則稱M是G的一個匹配.G中邊數最多的匹配稱作最大匹配.又設|V1||V2|,如果M是G的一個匹配且|M|=|V1|,則稱M是V1到V2的完備匹配.當|V2|=|V1|時,完備匹配又稱作完美匹配．例完備匹配完美匹配最大匹配.22最大匹配定義11.4設G=<V1,V2,E>為二部圖,2223與匹配有關的概念定義11.5設M是二部圖G=<V1,V2,E>的一個匹配.稱M中的邊為匹配邊,不在M中的邊為非匹配邊.與匹配邊相關聯的頂點為飽和點,不與匹配邊相關聯的頂點為非飽和點.G中由匹配邊和非匹配邊交替構成的路徑稱為交錯路徑,起點和終點都是非飽和點的交錯路徑稱為可增廣的交錯路徑．M為G的完備匹配當且僅當V1或V2中的每個頂點都是飽和點．M為G的完美匹配當且僅當G中的每個頂點都是飽和點．.23與匹配有關的概念定義11.5設M是二部圖G=<V1,2324可增廣的交錯路徑例左圖,飽和點:u1,u3,u4,v1,v2,v3;非飽和點:u2,v4;可增廣的交錯路徑:u2v3u4v2u1v4.由得到多一條邊的匹配.設M為G的一個匹配,是關于M的可增廣的交錯路徑,則

M

=ME()=(ME())(ME())是比M多一條邊的匹配.定理11.5

M為G的最大匹配G中不含M的可增廣的交錯路徑.u1u1u2u2u3u3u4u4v1v2v3v4v1v2v3v4.24可增廣的交錯路徑例左圖,飽和點:u1,u3,u4,v2425Hall定理定理11.6(Hall定理)設二部圖G=<V1,V2,E>,其中|V1||V2|,則

G中存在從V1到V2的完備匹配當且僅當V1中任意k(1k|V1|)個頂點至少與V2中的k個頂點相鄰.(相異性條件)證

必要性顯然.證充分性.設M為G的最大匹配,若M不是完備的,則存在非飽和點vxV1.于是,存在eE1=EM與vx關聯,且V2中與vx相鄰的頂點都是飽和點.考慮從vx出發的盡可能長的所有交錯路徑,這些交錯路徑都不是可增廣的,因此每條路徑的另一個端點一定是飽和點,從而全在V1中.令

S={v|vV1且v在從vx出發的交錯路徑上}T={v|vV2且v在從vx出發的交錯路徑上}除vx外,S和T中的頂點都是飽和點,且由匹配邊給出兩者之間的一一對應,因而|S|=|T|+1.這說明V1中有|T|+1個頂點只與V2中|T|個頂點相鄰,與相異性條件矛盾..25Hall定理定理11.6(Hall定理)設二部圖G=2526t條件定理11.7

設二部圖G=<V1,V2,E>,如果存在t使得,V1中每個頂點至少關聯t條邊,而V2中每個頂點至多關聯t條邊,則G中存在V1到V2的完備匹配.(t條件)證V1中任意k(1k|V1|)個頂點至少關聯kt條邊,而V2中每個頂點至多關聯t條邊,這kt條邊至少關聯V2中k個頂點.G滿足相異性條件．第2個圖不滿足t條件,但有完備匹配.例前兩個滿足相異性條件,第3個不滿足.26t條件定理11.7設二部圖G=<V1,V2,E>,2627一個應用實例例7

某課題組要從a,b,c,d,e5人中派3人分別到上海、廣州、香港去開會.已知a只想去上海，b只想去廣州，c,d,e都表示想去廣州或香港.問該課題組在滿足個人要求的條件下，共有幾種派遣方案？解令G=<V1,V2,E>，其中V1={s,g,x}，s,g,x分別表示上海、廣州和香港.V2={a,b,c,d,e},E={(u,v)|uV1,vV2,v想去u}.每個V1到V2的完備匹配給出一個派遣方案,共有9種.如a到上海,b到廣州,c到香港.

.27一個應用實例例7某課題組要從a,b,c,d,2728(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.11.4平面圖定義11.6如果能將無向圖G畫在平面上使得除頂點處外無邊相交,則稱G是可平面圖,簡稱平面圖.畫出的無邊相交的圖稱為G的平面嵌入.無平面嵌入的圖稱為非平面圖．例

(1)(2)(3)(4).28(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.12829平面圖的性質K5,K3,3都是非平面圖（定理11.13）平行邊與環不影響平面性.定理11.8

平面圖的子圖都是平面圖,非平面圖的母圖都是非平面圖．例如,所有度數不超過4的簡單圖都是平面圖.

當|V1|=1和2時二部圖G=<V1,V2,E>是平面圖.

Kn(n5)和Ks,t(s,t3)都是非平面圖..29平面圖的性質K5,K3,3都是非平面圖（定理11.132930平面圖的面與次數定義11.7給定平面圖G的平面嵌入,G的邊將平面劃分成若干個區域,每個區域都稱為G的一個面,其中有一個面的面積無限,稱為無限面或外部面,其余面的面積有限,稱為有限面或內部面.包圍每個面的所有邊組成的回路組稱為該面的邊界，邊界的長度稱為該面的次數．面R的次數記為deg(R)．deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.例.30平面圖的面與次數定義11.7給定平面圖G的平面嵌入,3031次數的性質定理17.4

平面圖各面次數之和等于邊數的兩倍.證

對每一條邊e,若e在兩個面的公共邊界上,則在計算這兩個面的次數時,e各提供1.而當e只在某一個面的邊界上出現時,它必在該面的邊界上出現兩次,從而在計算該面的次數時,e提供2．.31次數的性質定理17.4平面圖各面次數之和等于邊數的兩3132極大平面圖定義11.8

G為簡單平面圖,若在G的任意兩個不相鄰的頂點之間加一條邊所得圖為非平面圖,則稱G為極大平面圖.例如,K5,K33刪去一條邊后是極大平面圖K1,K2,K3,K4都是極大平面圖.定理11.10

設G為n(n3)階簡單連通的平面圖,G為極大平面圖當且僅當G的每個面的次數均為3.

證

現只證必要性.各面次數都大于或等于3.假如deg(Ri)=s4,若v1與v3不相鄰,則在Ri內加邊(v1,v3)不破壞平面性,與G是極大平面圖矛盾,因而v1與v3必相鄰,且邊(v1,v3)必在Ri外部.同樣地,v2與v4也相鄰且邊(v2,v4)在Ri的外部.于是,(v1,v3)與(v2,v4)相交于Ri的外部,與G是平面圖矛盾..32極大平面圖定義11.8G為簡單平面圖,若在G的任意3233例是否是極大平面圖?定理的應用只有(3)為極大平面圖

(1)(2)(3).33例是否是極大平面圖?定理的應用只有(3)為極大平面圖3334極小非平面圖定義11.9

若在非平面圖G中任意刪除一條邊,所得圖為平面圖,則稱G為極小非平面圖.K5,K3,3都是極小非平面圖

極小非平面圖必為簡單圖.34極小非平面圖定義11.9若在非平面圖G中任意刪除一條3435

歐拉公式定理11.11

設G為n階m條邊r個面的連通平面圖,則nm+r=2證對m做歸納證明.m=0時,G為平凡圖,n=1,m=0,r=1,成立.設m=k(k0)時結論成立.當m=k+1時,分兩者情況討論:(1)G中有一個1度頂點v,令G

=Gv,仍是連通的,n

=n1,m

=m1=k,r

=r.由歸納假設,nm

+r

=2.于是nm+r=(n

+1)(m

+1)+r

=n

m

+r=2(2)G中沒有1度頂點,則每一條邊都在某兩個面的公共邊界上.任取一條邊e,令G

=Ge,仍連通且n

=n,m

=m1=k,

r

=r1.由歸納假設,n

m

+r

=2.于是nm+r=n

(m

+1)+(r

+1)=n

m

+r

=2.35歐拉公式定理11.11設G為n階m條邊r個面的連通3536

歐拉公式的推廣推論對于有k個連通分支的平面圖G,有n

m+r=k+1其中n,m,r分別為G的頂點數,邊數和面數.證

設G的連通分支為G1,G2,…,Gk,由歐拉公式ni

mi

+ri=2,i=1,2,…,k.G的面數

.于是，整理得n

m+r=k+1.36歐拉公式的推廣推論對于有k個連通分支的平面圖G,3637解得與歐拉公式有關的定理定理11.12

設G為連通的平面圖,每個面的次數至少為l3，則

證由定理11.9及歐拉公式,定理11.13

K5,K3,3都是非平面圖.證假設K5是平面圖,K5無環和平行邊,每個面的次數均大于等于3.應該有矛盾..37解得與歐拉公式有關的定理定理11.12設G為連通的3738證(續)假設K3,3是平面圖,K3,3中最短圈的長度為4,每個面的次數均大于等于4.應該有矛盾.定理11.14

設G為n(n3)階m條邊的極大平面圖,則m=3n6.證極大平面圖是連通圖,由歐拉公式得r=2+mn.又由定理11.10的必要性,G的每個面的次數均為3,所以2m=3r.得m=3n6．推論設G是n(n3)階m條邊的簡單平面圖,則m3n6與歐拉公式有關的定理.38證(續)假設K3,3是平面圖,K3,3中最短圈的長3839如果簡單連通平面圖G的每個面的次數都等于3,則G為極大平面圖.證由定理11.9,

2m=3r由歐拉公式,r=2+m

n

整理得m=3n6若G不是極大平面圖,則G中存在不相鄰的頂點u,v,使得G

=G(u,v)還是簡單平面圖,而G

的邊數m

=m+1,n

=n,故m

>3n6與定理11.14的推論矛盾．定理11.10充分性證明.39如果簡單連通平面圖G的每個面的次數都等于3,則G為極大3940

同胚定義11.10設e=(u,v)為圖G的一條邊,在G中刪除e,增加新的頂點w,使u,v均與w相鄰,稱為在G中插入2度頂點w.設w為G中一個2度頂點,w與u,v相鄰,刪除w,增加新邊(u,v),稱為在G中消去2度頂點w.

若兩個圖G1與G2同構,或通過反復插入、消去2度頂點后同構,則稱G1與G2同胚．例插入與消去2度頂點收縮邊.40同胚定義11.10設e=(u,v)為圖G的一條邊4041庫拉圖斯基定理定理11.15

G是平面圖

G中不含與K5和K3,3同胚的子圖.定理11.16

G是平面圖

G中無可收縮為K5或K3,3的子圖.例8

證明下邊兩個圖為非平面圖.

與K5同胚

。

。

。

與K3,3同胚

。

。

.41庫拉圖斯基定理定理11.15G是平面圖G中不含4142例題例9

證明彼得森圖為非平面圖.

與K5同胚收縮(a,f),(b,g),(c,h),(d,i),(e,j)

與K3,3同胚收縮(b,g),(c,h),(d,i),(e,j)

.42例題例9證明彼得森圖為非平面圖.與K5同胚與K4243點著色定義11.11

設無向圖G無環,對G的每個頂點涂一種顏色,使相鄰的頂點涂不同的顏色,稱為圖G的一種點著色,簡稱著色.若能用k種顏色給G的頂點著色，則稱G是k-可著色的．圖的著色問題:要用盡可能少的顏色給圖著色.偶圈用2種顏色,奇圈用3種.奇階輪圖用3種,偶階輪圖用4種.例11

G是2-可著色的當且僅當G是二部圖.1212121232123323123243例10.43點著色定義11.11設無向圖G無環,對G的每個頂點4344應用1.有n項工作,每項工作需要一天的時間,有些工作不能同時進行,問至少需要幾天才能完成所有的工作?頂點表示工作,兩點之間有一條邊這兩項工作不能同時進行.工作的時間安排對應于這個圖的點著色:著同一種顏色的頂點對應的工作可安排在同一天,所需的最少天數是所需要的最少顏色數.2.寄存器分配.計算機有k個寄存器,要給每一個變量分配一個寄存器.如果兩個變量要在同一時刻使用,則不能把它們分配給同一個寄存器.每一個變量是一個頂點,如果兩個變量要在同一時刻使用,則用一條邊連接這兩個變量.這個圖的k-著色對應給變量分配寄存器的一種安全方式:給著同一種顏色的變量分配同一個寄存器..44應用1.有n項工作,每項工作需要一天的時間,有些工4445應用3.無線交換設備的波長分配.有n臺設備和k個發射波長,要給每一臺設備分配一個波長.如果兩臺設備靠得太近,則不能給它們分配相同的波長.以設備為頂點,如果兩臺設備靠得太近,則用一條邊連接它們.這個圖的k-著色給出一個波長分配方案:給著同一種顏色的設備分配同一個波長.

.45應用3.無線交換設備的波長分配.有n臺設備和k個發射4546地圖著色與對偶圖地圖:連通無橋平面圖的平面嵌入.每一個面是一個國家(或省,市,區等).若兩個國家有公共的邊界，則稱這兩個國家是相鄰的.對地圖的每個國家涂上一種顏色，使相鄰的國家涂不同的顏色，稱為對地圖的面著色,簡稱地圖著色.

地圖著色問題:用盡可能少的顏色給地圖著色.定義11.12

設G是一個平面嵌入,構造圖G*如下:在G的每一個面Ri中放置一個頂點vi*.設e為G的一條邊,若e在G的面Ri與Rj的公共邊界上,則作邊e*=(vi*,vj*)與e相交,且不與其他任何邊相交.若e為G中的橋且在面Ri的邊界上,則作以vi*為端點的環e*=(vi*,vi*).稱G*為G的對偶圖.

.46地圖著色與對偶圖地圖:連通無橋平面圖的平面嵌入.每一4647實例實線和空心點是平面嵌入,虛線和實心點是對偶圖.注意:這兩個平面嵌入是同一個平面圖的平面嵌入..47實例實線和空心點是平面嵌入,虛線和實心點是對偶圖..4748四色定理四色猜想(19世紀50年代,德摩根)五色定理(1890年,希伍德)四色定理(1976年,阿佩爾與黑肯)定理11.17

任何平面圖都是4-可著色的..48四色定理四色猜想(19世紀50年代,德摩根)五4849第十一章習題課

主要內容歐拉通路與歐拉回路,歐拉圖與半歐拉圖及判別哈密頓通路與哈密頓回路,哈密頓圖與半哈密頓圖及判別貨郎問題二部圖及其判別二部圖匹配及相關概念二部圖最大匹配的充要條件,存在完備匹配的條件平面圖及其性質(歐拉公式)平面圖的判別著色問題地圖著色與平面圖的對偶圖四色定理應用.49第十一章習題課主要內容.4950基本要求基本要求深刻理解歐拉圖,半歐拉圖,哈密頓圖,半哈密頓圖的定義掌握歐拉圖,半歐拉圖的判別會用哈密頓圖與半哈密頓圖的必要條件和充分條件會一筆畫出歐拉回路了解貨郎問題深刻理解二部圖的定義,掌握二部圖的判別深刻理解二部圖匹配及相關概念了解二部圖最大匹配的充要條件,會用存在完備匹配的條件(Hall定理與t條件).50基本要求基本要求.5051基本要求深刻理解平面圖及相關的概念牢記極大平面圖的主要性質和判別方法熟記歐拉公式及推廣形式，并能用歐拉公式及推廣形式證明有關定理與命題會用庫拉圖斯基定理證明非平面圖了解對偶圖的概念了解著色問題,地圖著色問題和四色定理會用上述概念和有關定理解決簡單的實際問題.51基本要求深刻理解平面圖及相關的概念.51521.設G為n(n2)階無向歐拉圖,證明G中無橋.證二用反證法.假設e=(u,v)是橋,則Ge產生兩個連通分支G1,G2,不妨設u在G1中,v在G2中.G中沒有奇度頂點,而刪除e,只使u,v的度數各減1,因而G1(G2)中只含一個奇度頂點,與任何圖中奇度頂點的個數是偶數矛盾.練習1證一設C為G中一條歐拉回路,eE(G),e在C上,

Ce連通,Ge也連通,所以e不為橋..521.設G為n(n2)階無向歐拉圖,證明G中無橋.證52532.

證明右圖不是哈密頓圖.證一

取V1={a,c,e,h,j,l}，

p(GV1)=7>6=|V1|練習

2證二

G為二部圖,V1={a,c,e,h,j,l},

V2={b,d,f,g,i,k,m},|V1||V2|.證三n=13,m=21.h,l,j為4度頂點,a,c,e為3度頂點,且它們關聯不相同的邊.而在哈密頓回路上,每個頂點關聯兩條邊,于是可能用于哈密頓回路的邊至多有21(32+31)=12.12條邊不可能構成經過13個頂點的回路..532.證明右圖不是哈密頓圖.證一取V1={53543．某次國際會議8人參加,已知每人至少與其余7人中的4人能用相同的語言,問服務員能否將他們安排在同一張圓桌就座,使得每個人都能與兩邊的人交談？解做無向圖G=<V,E>,其中V={v|v為與會者}，

E={(u,v)|u,vV,u與v有能用相同的語言,且u

v}.G為簡單圖且vV,d(v)4.于是,u,vV,d(u)+d(v)8,故G為哈密頓圖.服務員在G中找一條哈密頓回路,按回路中相鄰關系安排座位即可.練習3.543．某次國際會議8人參加,已知每人至少與其余7人中的454554.某公司招聘了3名大學畢業生,有5個部門需要人.部門領導與畢業生交談后,雙方都愿意的結果如表所示.如果每個部門只能接收一名畢業生,問這3名畢業生都能到他滿意的部門工作嗎?試給出分配方案.練習4解

作二部圖G=<V1,V2,E>

部門1部門2部門3部門4部門5畢業生A

畢業生B

畢業生C

1ABC2345一個分配方案是G的一個匹配.G滿足t條件,t=3,有完備匹配.如,A1,B2,C3;A3,B2,C5等..554.某公司招聘了3名大學畢業生,有5個部門需要人.5556練習5解設G的階數,邊數,面數分別為n,m,r.(1)用反證法.假設所有面的次數大于等于5,由歐拉公式得

2m5r=5(2+mn)①由(G)3及握手定理有2m

3n②得m30又有r=2+mn<12③③與②又可得m<30,矛盾.5.設G是連通的簡單平面圖,面數r<12,(G)3.(1)證明G中存在次數4的面.(2)舉例說明當r=12時,(1)中結論不真.(2)

正十二面體是一個反例.56練習5解設G的階數,邊數,面數分別為n,m,56576.設G是階數11的非平凡簡單無向圖,證明G和不可能全是平面圖.證

用反證法.假設與G都是平面圖,則G與的邊數m,m應滿足

不妨設

由于G是平面圖,又有m

3n6

得n213n+240

解得2

n10

與n11矛盾.練習6.576.設G是階數11的非平凡簡單無向圖,證明G和57587.證明下圖為非平面圖練習7證一含子圖K3,3:刪去頂點a和邊(c,d)證二含與K5同胚的子圖:刪去(a,f),收縮(a,e)和(f,g).587.證明下圖為非平面圖練習7證一含子圖K3,3:5859練習88.

給下圖著色至少要用幾種顏色?解由于a,b,c彼此相鄰,至少要用3種顏色,設它們分別著顏色1,2,3.最少還要用這三種顏色給d,e,f著色.而g與d,e,f相鄰只能用第4種顏色.故至少要用4種顏色..59練習88.給下圖著色至少要用幾種顏色?解由于a,b5960練習99.某校計算機系三年級學生在本學期共有6門選修課Ci,i=1,2,…,6.設S(Ci)為選Ci課的學生集.已知

S(Ci)S(C6)

,i=1,2,…,5，

S(Ci)S(Ci+1)

,i=1,2,3,4，

S(C5)S(C1)

.問這6門課至少幾天能考完？解做無向圖G=<V,E>,其中

V={C1,C2,…,C6}

E={(Ci,Cj)|S(Ci)S(Cj)}最少要用4種顏色著色,故最少要4天.60練習99.某校計算機系三年級學生在本學期共有6門選修課6061第十一章幾種特殊的圖主要內容歐拉圖哈密頓圖二部圖與匹配平面圖著色.1第十一章幾種特殊的圖主要內容.616211.1

歐拉圖歷史背景：哥尼斯堡七橋問題.211.1歐拉圖歷史背景：哥尼斯堡七橋問題.6263歐拉圖定義定義11.1圖(無向圖或有向圖)中所有邊恰好通過一次且經過所有頂點的通路稱為歐拉通路.圖中所有邊恰好通過一次且經過所有頂點的回路稱為歐拉回路．具有歐拉回路的圖稱為歐拉圖.具有歐拉通路而無歐拉回路的圖稱為半歐拉圖．說明：規定平凡圖為歐拉圖.環不影響圖的歐拉性..3歐拉圖定義定義11.1圖(無向圖或有向圖)中所有邊恰好6364歐拉圖實例歐拉圖不是半歐拉圖歐拉圖不是半歐拉圖.4歐拉圖實例歐拉圖不是半歐拉圖歐拉圖不是半歐拉圖.6465歐拉圖的判別法定理11.1(1)無向圖G是歐拉圖當且僅當G是連通的且沒有奇度頂點．(2)無向圖G是半歐拉圖當且僅當G是連通的且恰有兩個奇度頂點．(3)有向圖D是歐拉圖當且僅當D是強連通的且每個頂點的入度等于出度．(4)有向圖D是半歐拉圖當且僅當D是單向連通的且恰有兩個奇度頂點,其中一個頂點的入度比出度大1,另一個頂點出度比入度大1,其余頂點的入度等于出度．例1

設G是非平凡的歐拉圖，則(G)2.證只需證明G的任意一條邊e都不是橋.設C是一條歐拉回路,e在C上，因而Ge仍是連通的，故e不是橋．.5歐拉圖的判別法定理11.1(1)無向圖G是歐拉圖當且6566Fleury算法算法：(1)任取v0V(G),令P0=v0,i=0.(2)設Pi=v0e1v1e2…eivi，

如果E(G)-{e1,e2,…,ei}中沒有與vi關聯的邊,則計算結束;

否則按下面方法從E(G){e1,e2,…,ei}中選取ei+1：

(a)ei+1與vi關聯；

(b)除非無別的邊可供選擇,否則ei+1不應為

G{e1,e2,…,ei}

中的橋.

設ei+1=(vi,vi+1),把ei+1vi+1加入Pi.(3)令i=i+1,返回(2)..6Fleury算法算法：.6667實例一筆畫出一條歐拉回路.7實例一筆畫出一條歐拉回路.6768實例一筆畫出一條歐拉回路.8實例一筆畫出一條歐拉回路.686911.2

哈密頓圖歷史背景：哈密頓周游世界問題

(1)(2).911.2哈密頓圖歷史背景：哈密頓周游世界問題6970哈密頓圖與半哈密頓圖定義11.2經過圖中所有頂點一次且僅一次的通路稱作哈密頓通路.經過圖中所有頂點一次且僅一次的回路稱作哈密頓回路.具有哈密頓回路的圖稱作哈密頓圖.具有哈密頓通路且無哈密頓回路的圖稱作半哈密頓圖.規定:平凡圖是哈密頓圖.哈密頓圖半哈密頓圖哈密頓圖例不是.10哈密頓圖與半哈密頓圖定義11.2經過圖中所有頂點一次且7071無向哈密頓圖的一個必要條件定理11.2

設無向圖G=<V,E>是哈密頓圖，對于任意V1V且V1，均有p(GV1)|V1|證設C為G中一條哈密頓回路(1)p(CV1)|V1|(2)p(GV1)

p(CV1)|V1|（因為CG）推論設無向圖G=<V,E>是半哈密頓圖，對于任意的V1V且V1均有

p(GV1)|V1|+1證設為從u到v的哈密頓通路，令G=G(u,v)，則G為哈密頓圖.于是

p(GV1)=p(GV1(u,v))

p(GV1)+1|V1|+1.11無向哈密頓圖的一個必要條件定理11.2設無向圖G=<7172例題例2判斷下面的圖是不是哈密頓圖,是不是半哈密頓圖.解(a)取V1={a,f},p(GV1)=|{b,c,d,e}|=4>|V1|=2,不是哈密頓圖，也不是半哈密頓圖．(b)取V1={a,g,h,i,c},p(GV1)=|{b,e,f,j,k,d}|=6>|V1|=5,不是哈密頓圖.而baegjckhfid是一條哈密頓通路,是半哈密頓圖．(c)abcdgihjefa是一條哈密頓回路，是哈密頓圖．.12例題例2判斷下面的圖是不是哈密頓圖,是不是半哈密頓7273例題例3設G為n階無向連通簡單圖，若G中有割點或橋，則G不是哈密頓圖.證設v為割點，則p(Gv)2>|{v}|=1.K2有橋，它顯然不是哈密頓圖.除K2外，其他有橋的連通圖均有割點..13例題例3設G為n階無向連通簡單圖，若G中有割點或橋，7374無向哈密頓圖的一個充分條件定理11.3

設G是n階無向簡單圖,若對于任意不相鄰的頂點vi,vj,均有

d(vi)+d(vj)

n1()則G中存在哈密頓通路.推論設G為n(n3)階無向簡單圖,若對于G中任意兩個不相鄰的頂點vi,vj,均有

d(vi)+d(vj)

n

（）則G中存在哈密頓回路..14無向哈密頓圖的一個充分條件定理11.3設G是n階無向7475判斷是否為哈密頓圖判斷是否為(半)哈密頓圖至今還是一個難題.(1)觀察出一條哈密頓回路或哈密頓通路.(2)證明滿足充分條件.(3)證明不滿足必要條件.例4

證明右圖(周游世界問題)是哈密頓圖證a

b

c

d

e

f

g

h

i

j

k

l

m

no

p

q

r

s

t

a是一條哈密頓回路.注意，此圖不滿足定理11.3推論的條件.例5

完全圖Kn(n3)是哈密頓圖.證

任何兩個頂點u,v，d(u)+d(v)=2(n1)

n.15判斷是否為哈密頓圖判斷是否為(半)哈密頓圖至今還是一個7576貨郎問題貨郎問題:有n個城市,給定城市之間道路的長度(長度可以為,對應這兩個城市之間無交通線).貨郎從某個城市出發,要經過每個城市一次且僅一次,最后回到出發的城市,問如何走才能使他走的路線最短?圖論方法描述如下:設G=<V,E,W>為一個n階完全帶權圖Kn,各邊的權非負,且可能為.求G中的一條最短的哈密頓回路.不計出發點和方向,Kn(n3)中有(n1)!/2條不同的哈密頓回路.16貨郎問題貨郎問題:有n個城市,給定城市之間道路的長度7677

解C1=a

b

c

d

a,W(C1)=10

C2=a

b

d

c

a,W(C2)=11

C3=a

c

b

d

a,W(C3)=9最短

例6

求下面帶權圖K4中最短哈密頓回路.

例題.17解C1=abcda,W(C777811.3二部圖與匹配定義11.3

設G=<V,E>為一個無向圖,若能將V分成V1和V2(V1V2=V,V1V2=),使得G中的每條邊的兩個端點都是一個屬于V1,另一個屬于V2,則稱G為二部圖(或稱二分圖,偶圖),稱V1和V2為互補頂點子集,常將二部圖G記為<V1,V2,E>.又若G是簡單二部圖,V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖,記為Kr,s,其中r=|V1|,s=|V2|..1811.3二部圖與匹配定義11.3設G=<V,E>7879實例例K2,3K3,3.19實例例K2,3K3,3.7980二部圖的判別法定理11.4

無向圖G=<V1,V2,E>是二部圖當且僅當G中無奇圈.證

必要性.若G中無圈,結論成立.若G中有圈,設G中的一個圈C=v1v2vlv1,l≥2.不妨設v1V1,v1,v2,,vl

依次交替屬于V1,

V2且vlV2,因而l為偶數.得證C為偶圈．充分性.不妨設G為連通圖,否則可對每個連通分支進行討論,

孤立點可根據需要分屬V1和V2.設v0為G中任意一個頂點,令V1={v|vV(G)d(v0,v)為偶數}V2={v|vV(G)d(v0,v)為奇數}d(v0,v)是v0到v的最短路徑的邊數(每條邊的權為1).V1，V2,V1V2=,V1V2=V(G).要證V1中任意兩點不相鄰．.20二部圖的判別法定理11.4無向圖G=<V1,V2,E8081證明假若存在vi,vjV1相鄰,記e=(vi,vj),設v0到vi,vj的最短路徑分別為i,j,由i,j和e構成一條長度為奇數的回路.這條回路可能是一條復雜回路,可以分解成若干由i,j共有的邊構成的回路(實際上是每條邊重復一次的路徑)和由i,j不共有的邊及e構成的圈.由i,j共有的邊構成的回路的長度為偶數,故在由i,j不共有的邊(可以還包括e)構成的圈中一定有奇圈,這與已知條件矛盾.得證V1中任意兩頂點不相鄰.由對稱性,V2中也不存在相鄰的頂點,得證G為二部圖．.21證明假若存在vi,vjV1相鄰,記e=(vi,vj)8182最大匹配定義11.4設G=<V1,V2,E>為二部圖,ME,如果M中的任意兩條邊都不相鄰,則稱M是G的一個匹配.G中邊數最多的匹配稱作最大匹配.又設|V1||V2|,如果M是G的一個匹配且|M|=|V1|,則稱M是V1到V2的完備匹配.當|V2|=|V1|時,完備匹配又稱作完美匹配．例完備匹配完美匹配最大匹配.22最大匹配定義11.4設G=<V1,V2,E>為二部圖,8283與匹配有關的概念定義11.5設M是二部圖G=<V1,V2,E>的一個匹配.稱M中的邊為匹配邊,不在M中的邊為非匹配邊.與匹配邊相關聯的頂點為飽和點,不與匹配邊相關聯的頂點為非飽和點.G中由匹配邊和非匹配邊交替構成的路徑稱為交錯路徑,起點和終點都是非飽和點的交錯路徑稱為可增廣的交錯路徑．M為G的完備匹配當且僅當V1或V2中的每個頂點都是飽和點．M為G的完美匹配當且僅當G中的每個頂點都是飽和點．.23與匹配有關的概念定義11.5設M是二部圖G=<V1,8384可增廣的交錯路徑例左圖,飽和點:u1,u3,u4,v1,v2,v3;非飽和點:u2,v4;可增廣的交錯路徑:u2v3u4v2u1v4.由得到多一條邊的匹配.設M為G的一個匹配,是關于M的可增廣的交錯路徑,則

M

=ME()=(ME())(ME())是比M多一條邊的匹配.定理11.5

M為G的最大匹配G中不含M的可增廣的交錯路徑.u1u1u2u2u3u3u4u4v1v2v3v4v1v2v3v4.24可增廣的交錯路徑例左圖,飽和點:u1,u3,u4,v8485Hall定理定理11.6(Hall定理)設二部圖G=<V1,V2,E>,其中|V1||V2|,則

G中存在從V1到V2的完備匹配當且僅當V1中任意k(1k|V1|)個頂點至少與V2中的k個頂點相鄰.(相異性條件)證

必要性顯然.證充分性.設M為G的最大匹配,若M不是完備的,則存在非飽和點vxV1.于是,存在eE1=EM與vx關聯,且V2中與vx相鄰的頂點都是飽和點.考慮從vx出發的盡可能長的所有交錯路徑,這些交錯路徑都不是可增廣的,因此每條路徑的另一個端點一定是飽和點,從而全在V1中.令

S={v|vV1且v在從vx出發的交錯路徑上}T={v|vV2且v在從vx出發的交錯路徑上}除vx外,S和T中的頂點都是飽和點,且由匹配邊給出兩者之間的一一對應,因而|S|=|T|+1.這說明V1中有|T|+1個頂點只與V2中|T|個頂點相鄰,與相異性條件矛盾..25Hall定理定理11.6(Hall定理)設二部圖G=8586t條件定理11.7

設二部圖G=<V1,V2,E>,如果存在t使得,V1中每個頂點至少關聯t條邊,而V2中每個頂點至多關聯t條邊,則G中存在V1到V2的完備匹配.(t條件)證V1中任意k(1k|V1|)個頂點至少關聯kt條邊,而V2中每個頂點至多關聯t條邊,這kt條邊至少關聯V2中k個頂點.G滿足相異性條件．第2個圖不滿足t條件,但有完備匹配.例前兩個滿足相異性條件,第3個不滿足.26t條件定理11.7設二部圖G=<V1,V2,E>,8687一個應用實例例7

某課題組要從a,b,c,d,e5人中派3人分別到上海、廣州、香港去開會.已知a只想去上海，b只想去廣州，c,d,e都表示想去廣州或香港.問該課題組在滿足個人要求的條件下，共有幾種派遣方案？解令G=<V1,V2,E>，其中V1={s,g,x}，s,g,x分別表示上海、廣州和香港.V2={a,b,c,d,e},E={(u,v)|uV1,vV2,v想去u}.每個V1到V2的完備匹配給出一個派遣方案,共有9種.如a到上海,b到廣州,c到香港.

.27一個應用實例例7某課題組要從a,b,c,d,8788(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.11.4平面圖定義11.6如果能將無向圖G畫在平面上使得除頂點處外無邊相交,則稱G是可平面圖,簡稱平面圖.畫出的無邊相交的圖稱為G的平面嵌入.無平面嵌入的圖稱為非平面圖．例

(1)(2)(3)(4).28(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.18889平面圖的性質K5,K3,3都是非平面圖（定理11.13）平行邊與環不影響平面性.定理11.8

平面圖的子圖都是平面圖,非平面圖的母圖都是非平面圖．例如,所有度數不超過4的簡單圖都是平面圖.

當|V1|=1和2時二部圖G=<V1,V2,E>是平面圖.

Kn(n5)和Ks,t(s,t3)都是非平面圖..29平面圖的性質K5,K3,3都是非平面圖（定理11.138990平面圖的面與次數定義11.7給定平面圖G的平面嵌入,G的邊將平面劃分成若干個區域,每個區域都稱為G的一個面,其中有一個面的面積無限,