版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、第8章 圖論,8.1 圖的基本概念 8.2 路徑和回路8.3 圖的矩陣表示8.4 二部圖8.5 平面圖8.6 樹8.7 有向樹8.8 運輸網(wǎng)絡(luò),問題是要從這四塊陸地中任何一塊開始,通過每一座橋正好一次,再回到起點。 歐拉在1736年解決了這個問題 。,判定法則:如果通奇數(shù)座橋的地方不止兩個,那么滿足要求的路線便不存在了。如果只有兩個地方通奇數(shù)座橋,則可從其中任何一地出發(fā)找到所要求的路線。若
2、沒有一個地 方通奇數(shù)座橋,則從任何一地出發(fā),所求的路線都能實現(xiàn),定義8.1―1 一個圖G是一個三重組〈V(G),E(G),ΦG〉,其中V(G)是一個非空的結(jié)點(或叫頂點)集合,E(G)是邊的集合,ΦG是從邊集E到結(jié)點偶對集合上的函數(shù)。一個圖可以用一個圖形表示。 例1設(shè)G=〈V(G),E(G),ΦG〉,其中V(G)={a,b,c,d},E(G)={e1,e2,e3,e4, e5,e6,e7},ΦG(e1)=(a,b)
3、,ΦG(e2)=(a,c),ΦG(e3)=(b,d), ΦG(e4)=(b,c),ΦG(e5)=(d,c),ΦG(e6)=(a,d),ΦG(e7)=(b,b)則圖G可用圖8.1―1表示。,8.1 圖的基本概念,8.1.1 圖,定義中的結(jié)點偶對可以是有序的,也可以是無序的。若邊e所對應(yīng)的偶對〈a,b〉是有序的,則稱e是有向邊。有向邊簡稱弧,a叫弧e的始點,b叫弧e的終點,統(tǒng)稱為e的端點。稱e是關(guān)聯(lián)于結(jié)點a和b的,結(jié)點a和結(jié)點b是鄰
4、接的。若邊e所對應(yīng)的偶對(a,b)是無序的,則稱e是無向邊。無向邊簡稱棱,除無始點和終點的術(shù)語外,其它術(shù)語與有向邊相同。 每一條邊都是有向邊的圖稱為有向圖, 第三章中的關(guān)系圖都是有向圖的例子。每一條邊都是無向邊的圖稱為無向圖;如果在圖中一些邊是有向邊,而另一些邊是無向邊,則稱這個圖是混合圖。我們僅討論有向圖和無向圖,且V(G)和E(G)限于有限集合。,約定用〈a,b〉表示有向邊,(a,b)表示無向邊,既表示有向邊
5、又表示無向邊時用[a,b]。 有向圖和無向圖也可互相轉(zhuǎn)化。例如,把無向圖中每一條邊都看作兩條方向不同的有向邊,這時無向圖就成為有向圖。又如,把有向圖中每條有向邊都看作無向邊,就得到無向圖。這個無向圖習(xí)慣上叫做該有向圖的底圖。 在圖中,不與任何結(jié)點鄰接的結(jié)點稱為弧立結(jié)點;全由孤立結(jié)點構(gòu)成的圖稱為零圖。關(guān)聯(lián)于同一結(jié)點的一條邊稱為自回路;自回路的方向不定。自回路的有無不使有關(guān)圖論的各個定理發(fā)生重大變化,所以有許多場合都略去
6、自回路。,在有向圖中,兩結(jié)點間(包括結(jié)點自身間)若同始點和同終點的邊多于一條,則這幾條邊稱為平行邊。在無向圖中,兩結(jié)點間(包括結(jié)點自身間)若多于一條邊,則稱這幾條邊為平行邊。兩結(jié)點a、b間互相平行的邊的條數(shù)稱為邊[a,b]的重數(shù)。僅有一條時重數(shù)為1,無邊時重數(shù)為0。 定義8.1―2含有平行邊的圖稱為多重圖。非多重圖稱為線圖。無自回路的線圖稱為簡單圖。 在圖8.1―3中,(a)、(b)是多
7、重圖,(c)是線圖,(d)是簡單圖,關(guān)系圖都是線圖。,圖 8.1―3,定義 8.1―3賦權(quán)圖G是一個三重組 〈V,E,g〉或四重組〈V,E,f,g〉,其中V是結(jié)點集合, E是邊的集合,f是定義在V上的函數(shù),g是定義在E上的函數(shù)。 右圖給出一個賦權(quán)圖。 V={v1,v2,v3} E={e1,e2}={(v1,v2),(v2,v3)} f(v1)=5,f(v2)=8,f(v3)=1
8、1 g(e1)=4.6,g(e2)=7.5,8.1.2 結(jié)點的次數(shù) 定義8.1―4在有向圖中,對于任何結(jié)點v,以v為始點的邊的條數(shù)稱為結(jié)點v的引出次數(shù)(或出度),記為deg+(v);以v為終點的邊的條數(shù)稱為結(jié)點v的引入次數(shù)(或入度),記為deg-(v);結(jié)點v的引出次數(shù)和引入次數(shù)之和稱為結(jié)點v的次數(shù)(或度數(shù)),記作deg(v)。在無向圖中,結(jié)點v的次數(shù)是與結(jié)點v相關(guān)聯(lián)的邊的條數(shù),也記為deg(v)。孤
9、立結(jié)點的次數(shù)為零。,定理8.1―1 設(shè)G是一個(n,m)圖,它的結(jié)點集合為V={v1,v2,…,vn},則,證 因為每一條邊提供兩個次數(shù),而所有各結(jié)點次數(shù)之和為m條邊所提供,所以上式成立。 在有向圖中,上式也可寫成:,定理8.1―2在圖中,次數(shù)為奇數(shù)的結(jié)點必為偶數(shù)個。 證 設(shè)次數(shù)為偶數(shù)的結(jié)點有n1個,記為 (i=1,2,…,n1)。次數(shù)為奇數(shù)的結(jié)點有n2個,記為 (i=1,2,
10、…,n2)。由上一定理得,因為次數(shù)為偶數(shù)的各結(jié)點次數(shù)之和為偶數(shù)。所以前一項次數(shù)為偶數(shù);若n2為奇數(shù),則第二項為奇數(shù),兩項之和將為奇數(shù),但這與上式矛盾。故n2必為偶數(shù)。證畢。,,圖 8.1―5,定義8.1―5各結(jié)點的次數(shù)均相同的圖稱為正則圖,各結(jié)點的次數(shù)均為k時稱為k―正則圖。 下圖所示的稱為彼得森(Petersen)圖,是3―正則圖。,8.1.3 圖的同構(gòu) 定義8.1.6設(shè)G=〈V
11、,E〉和G′=〈V′,E′〉是兩個圖,若存在從V到V′的雙射函數(shù)Φ,使對任意a、b∈V,[a,b∈E當(dāng)且僅當(dāng)[Φ(a),Φ(b)]∈E′,并且[a,b]和[Φ(a),Φ(b)]有相同的重數(shù),則稱G和G′是同構(gòu)的。 上述定義說明,兩個圖的各結(jié)點之間,如果存在一一對應(yīng)關(guān)系,而且這種對應(yīng)關(guān)系保持了結(jié)點間的鄰接關(guān)系(在有向圖時還保持邊的方向)和邊的重數(shù),則這兩個圖是同構(gòu)的,兩個同構(gòu)的圖除了頂點和邊的名稱不同外實際上代表同樣
12、的組合結(jié)構(gòu)。,,例2 (a)、(b)兩圖是同構(gòu)的。因為可作映射:g(1)=v3,g(2)=v1,g(3)=v4,g(4)=v2。在這映射下,邊〈1,3〉,〈1,2〉,〈2,4〉和〈3,4〉分別映射到〈v3,v4〉,〈v3,v1〉,〈v1,v2〉和〈v4,v2〉,而后面這些邊又是(b)中僅有的邊。,兩圖同構(gòu)的必要條件: (1) 結(jié)點數(shù)相等; (2) 邊數(shù)相等; (3) 度數(shù)相同的結(jié)點數(shù)
13、相等。 但這不是充分條件。例如下圖中(a)、(b)兩圖雖然滿足以上3條件,但不同構(gòu)。(a)中的x應(yīng)與(b)中的y對應(yīng),因為次數(shù)都是3。但(a)中的x與兩個次數(shù)為1的點u,v鄰接,而(b)中的y僅與一個次數(shù)為1的點w鄰接。,8.1.4 圖的運算 圖的常見運算有并、交、差、環(huán)和等,現(xiàn)分別定義于下: 定義8.1―7設(shè)圖G1=〈V1,E1〉和圖G2=〈V2,E2〉 (1)
14、G1與G2的并,定義為圖G3=〈V3,E3〉,其中V3=V1∪V2,E3=E1∪E2,記為G3=G1∪G2。 (2)G1與G2的交,定義為圖G3=〈V3,E3〉,其中V3=V1∩V2,E3=E1∩E2,記為G3=G1∩G2。,(3)G1與G2的差,定義為圖G3=〈V3,E3〉,記為G3=G1-G2。 其中E3=E1-E2,V3=(V1-V2)∪{E3中邊所關(guān)聯(lián)的頂點}。 (4)G1與G2的環(huán)和,定義為圖G3=〈V3,E
15、3〉,G3=(G1∪G2)-(G1∩G2),記為G3=G1G2。,除以上4種運算外,還有以下兩種操作: (1) 刪去圖G的一條邊e; (2)刪去圖G的一個結(jié)點v。它的實際意義是刪去結(jié)點v和與v關(guān)聯(lián)的所有邊。,8.1.5 子圖與補圖 定義8.1―8設(shè)G=〈V,E〉和G′=〈V′,E′〉是兩個圖。 (1) 如果V′ V和E′ E,則稱G′是G的子圖。如果V′ V和E′
16、 E,則稱G′ G的真子圖。(注意:“G′是圖”已隱含著“E′中的邊僅關(guān)聯(lián)V′中的結(jié)點”的意義。) (2) 如果V′=V和E′ E,則稱G′為G的生成子圖。 (3) 若子圖G′中沒有孤立結(jié)點,G′由E′唯一確定,則稱G′為由邊集E′導(dǎo)出的子圖。,(4)若在子圖G′中,對V′中的任意二結(jié)點u、v,當(dāng)[u,v]∈E時有[u,v]∈E′,則G′由V′唯一確定,此時稱G′為由結(jié)點集V′
17、導(dǎo)出的子圖。,定義8.1―9在n個結(jié)點的有向圖G=〈V,E〉中,如果E=V×V,則稱G為有向完全圖;在n個結(jié)點的無向圖G=〈V,E〉中,如果任何兩個不同結(jié)點間都恰有一條邊,則稱G為無向完全圖,記為Kn。 圖8.1―11是4個結(jié)點的有向完全圖和無向完全圖的圖示。 定義8.1―10 設(shè)線圖G=〈V,E〉有n個頂點,線圖H=〈V,E′〉也有同樣的頂點,而E′是由n個頂點的完全圖的邊刪
18、去E所得,則圖H稱為圖G的補圖,記為 ,顯然, 。,8.2 路徑和回路,8.2.1 路徑和回路 定義8.2―1在有向圖中,從頂點v0到頂點vn的一條路徑是圖的一個點邊交替序列(v0e1v1e2v2…envn),其中vi-1和vi分別是邊ei的始點和終點,i=1,2,…,n。在序列中,如果同一條邊不出現(xiàn)兩次,則稱此路徑是簡單路徑,如果同一頂點不出現(xiàn)兩次,則
19、稱此路徑是基本路徑(或叫鏈)。,基本路徑也一定是簡單路徑。,如果路徑的始點v0和終點vn相重合,即v0=vn,則此路徑稱為回路,沒有相同邊的回路稱為簡單回路,通過各頂點不超過一次的回路稱為基本回路。 (a)P1=(v1e1v2e7v5) 是一條基本路徑。 (b)P2=(v2e2v3e3v3e4v1e1v2) 是一簡單回路 非基本回路。,,,在無向圖上,以上各術(shù)語的定義完
20、全類似,故不重復(fù)。路徑和回路可僅用邊的序列表示,在非多重圖時也可用頂點序列表示。,定義8.2―2 路徑P中所含邊的條數(shù)稱為路徑P的長度。長度為0的路徑定義為單獨一個頂點。(但注意習(xí)慣上不定義長度為0的回路。) 定理8.2―1在一個具有n個結(jié)點的簡單圖G=〈V,E〉中,如果從v1到v2有一條路徑,則從v1到v2有一條長度不大于n-1的基本路徑。,簡證 假定從v1到v2存在一條路徑,(v1,…,vi,…,v2)是所
21、經(jīng)的結(jié)點,如果其中有相同的結(jié)點vk,例 (v1,…,vi,…,vk,…,vk,…,v2),則刪去從vk到vk的這些邊,它仍是從v1到v2的路徑,如此反復(fù)地進行直至(v1,…,vi,…,v2)中沒有重復(fù)結(jié)點為止。此時,所得的就是基本路徑?;韭窂降拈L度比所經(jīng)結(jié)點數(shù)少1,圖中共n個結(jié)點,故基本路徑長度不超過n-1。,定理8.2―2在一個具有n個結(jié)點的簡單圖G=〈V,E〉中,如果經(jīng)v1有一條簡單回路,則經(jīng)v1有一條長度不超過n的基本回路。
22、 定義8.2―3在圖G=〈V,E〉中,從結(jié)點vi到vj最短路徑的長度叫從vi到vj的距離,記為d(vi,vj)。若從vi到vj不存在路徑,則d(vi,vj)=∞。 注意,在有向圖中,d(vi,vj)不一定等于d(vj,vi),但一般地滿足以下性質(zhì): (1) d(vi,vj)≥0; (2) d(vi,vi)=0;
23、 (3) d(vi,vj)+d(vj,vk)≥d(vi,vk)。,,,8.2.2 連通圖 定義8.2―4設(shè)G=〈V,E〉是圖,且vi、vj∈V。如果從vi到vj存在一條路徑,則稱vj從vi可達。vi自身認為從vi可達。 定義8.2―5在無向圖G中,如果任兩結(jié)點可達,則稱圖G是連通的;如果G的子圖G′是連通的,沒有包含G′的更大的子圖G″是連通的,則稱G′是G
24、的連通分圖(簡稱分圖)。,,圖 8.2―2,一個無向圖或者是一個連通圖,如圖8.2―2(a)所示,或者是由若干個連通分圖組成,如圖8.2―2(b)所示。,定理8.2―3設(shè)G是任一(n,m)無向簡單圖,ω是其分圖個數(shù),則,定義8.2―6在有向圖中,如果在任兩結(jié)點偶對中,至少從一個結(jié)點到另一個結(jié)點是可達的,則稱圖G是單向連通的;如果在任兩結(jié)點偶對中,兩結(jié)點都互相可達,則稱圖G是強連通的;如果它的底圖是連通的,則稱圖G是弱連通的。,強連
25、通的也一定是單向連通和弱連通的,單向連通的一定是弱連通的,但其逆均不真。在下圖中,(a)是強連通的,(b)是單向連通的,(c)是弱連通的。,定義8.2―7在有向圖G=〈V,E〉中,G′是G的子圖,若G′是強連通的(單向連通的,弱連通的),沒有包含G′的更大子圖G″是強連通的(單向連通的,弱連通的),則稱G′是G的強分圖(單向分圖,弱分圖)。 在下圖中,強分圖集合是: {〈{1,2,3},{e1,e2,e3}〉,〈{4},φ
26、〉,〈{5},φ〉, 〈{6},φ〉,〈{7,8},{e7,e8}〉},單向分圖集合是: {〈{1,2,3,4,5},{e1,e2,e3,e4,e5}〉,〈{6,5},{e6}〉, 〈{7,8},{e7,e8}〉}
27、弱分圖集合是: {〈{1,2,3,4,5,6},{e1,e2,e3,e4,e5,e6}〉, 〈{7,8},{e7,e8}〉},8.2.3 賦權(quán)圖中的最短路徑 設(shè)G=〈V,E,W〉是個賦權(quán)圖,W是從E到正實數(shù)集合的函數(shù),邊[i,j]的權(quán)記為W(i,j),稱為邊的長度。若i和j之間沒
28、有邊,那么W(i,j)=∞。路徑P的長度定義為路徑中邊的長度之和,記為W(P)。圖G中從結(jié)點u到結(jié)點v的距離記為d(u,v),定義為 min{W(P)|P為G中從u到v的路徑} ∞ 當(dāng)從u到v不可達時,本小節(jié)主要討論在一個賦權(quán)的簡單連通無向圖 G=〈V,E,W〉中,求一結(jié)點a(稱為源點)到其它結(jié)點x
29、的最短路徑的長度,通常稱它為單源問題。下面介紹1959年迪克斯特拉(E.W.Dijkstra)提出的單源問題的算法,其要點如下: (1) 把V分成兩個子集S和T。初始時,S={a},T=V-S。 (2) 對T中每一元素t計算D(t),根據(jù)D(t)值找出T中距a最短的一結(jié)點x,寫出a到x的最短路徑的長度D(x)。 (3)置S為S∪{x},置T為T-{x},若T=
30、,則停止,否則再重復(fù)2。,算法中步驟(1)和(3)是清楚的,現(xiàn)在對2給以說明。 D(t)表示從a到t的不包含T中其它結(jié)點的最短通路的長度,但D(t)不一定是從a到t的距離,因為從a到t可能有包含T中另外結(jié)點的更短通路。 首先我們證明“若x是T中具有最小D值的結(jié)點,則D(x)是從a到x的距離”,用反證法。若另有一條含有T中另外結(jié)點的更短通路,不妨設(shè)這個通路中第一個屬于T-{x}的結(jié)點是t
31、1,于是D(t1)<D(x),但這與題設(shè)矛盾??梢娨陨蠑嘌猿闪?。,其次說明計算D(t)的方法。初始時,D(t)=W(a,t),現(xiàn)在我們假設(shè)對T中的每一個t已計算了D值。設(shè)x是T中D值最小的一個結(jié)點,記S′=S∪{x},T′=T-{x},令D′(t)表示T′中結(jié)點t的D值,則 D′(t)=min[D(t),D(x)+W(x,t)] 現(xiàn)分情況證明上式。,(a)如果從a到t有一條最短路徑,它不包
32、含T′中的其它結(jié)點,也不含x點,則D′(t)=D(t)。 (b)如果從a到t有一條最短路徑,它從a到x不包含T′中的結(jié)點,接著是邊W(x,t),在此情況下,D′(t)是D(x)+W(x,t)。,例1 考慮圖8.2―7中的圖,起初S={a},T={v1,v2,v3,v4},D(a)=0,D(v1)=2,D(v2)=+∞,D(v3)=+∞,D(v4)=10。因為D(v1)=2是T中最小的D值,所以選x=v1。
33、 置S為S∪{x}={a,v1},置T為T-{x}={v2,v3,v4}。然后計算: D(v2)=min(+∞,2+3)=5 D(v3)=min(+∞,+∞)=+∞ D(v4)=min(10,2+7)=9 如此類推,直至T= 終止。整個過程概括于表8.2―1中。,圖 8.2―7,表 8.2―1,8.2.4 歐
34、拉路徑和歐拉回路 哥尼斯堡(Konigsberg,現(xiàn)加里寧格勒)位于普雷格爾(Pregel)河畔,河中有兩島。城市的各部分由7座橋接通,如圖8.2―8(a)所示。古時城中居民熱衷于一個問題:游人從任一地點出發(fā),怎樣才能做到穿過每座橋一次且僅一次后又返回原出發(fā)地。1736年歐拉用圖論方法解決了此問題,寫了第一篇圖論的論文,從而成為圖論的創(chuàng)始人。,不難看出,如果用結(jié)點代表陸地,用邊代表橋,哥尼斯堡七橋問題就等價在于圖
35、8.2―8(b)中找到這樣一條路徑,它穿程每條邊一次且僅一次。 穿程于圖G的每條邊一次且僅一次的路徑,稱為歐拉路徑。穿程于圖G的每條邊一次且僅一次的回路,稱為歐拉回路,具有歐拉回路的圖稱為歐拉圖。 顯然,具有歐拉路徑的圖除孤立結(jié)點外是連通的,而孤立結(jié)點不影響歐拉路徑的討論。因此,下邊討論歐拉路徑有關(guān)問題時均假定圖是連通的。,圖 8.2―8,定理8.2―4無向連通圖G具有一條歐拉路徑
36、當(dāng)且僅當(dāng)G具有零個或兩個奇數(shù)次數(shù)的頂點。 證必要性。如果圖具有歐拉路徑,那么順著這條路徑畫出的時候,每次碰到一個頂點,都需通過關(guān)聯(lián)于這個頂點的兩條邊,并且這兩條邊在以前未畫過。因此,除路徑的兩端點外,圖中任何頂點的次數(shù)必是偶數(shù)。如果歐拉路徑的兩端點不同,那么它們就是僅有的兩個奇數(shù)頂點,如果它們是重合的,那么所有頂點都有偶數(shù)次數(shù),并且這條歐拉路徑成為一條歐拉回路。因此必要性得證。,充分性。我們從兩個奇數(shù)次數(shù)的頂點
37、之一開始(若無奇數(shù)次數(shù)的頂點,可從任一點開始),構(gòu)造一條歐拉路徑。以每條邊最多畫一次的方式通過圖中的邊。對于偶數(shù)次數(shù)的頂點,通過一條邊進入這個頂點,總可通過一條未畫過的邊離開這個頂點。因此,這樣的構(gòu)造過程一定以到達另一個奇數(shù)次數(shù)頂點而告終(若無奇數(shù)次數(shù)的頂點,則以回到原出發(fā)點而告終)。如果圖中所有邊已用這種方法畫過,顯然,這就是所求的歐拉路徑。如果圖中不是所有邊被畫過,我們?nèi)サ粢旬嬤^的邊,得到由剩下邊組成的一個子圖,這個子圖的頂點次數(shù)全
38、是偶數(shù)。,并且因為原來的圖是連通的,因此,這個子圖必與我們已畫過的路徑在一個點或多個點相接。由這些頂點中的一個開始,我們再通過邊構(gòu)造路徑,因為頂點次數(shù)全是偶數(shù),因此,這條路徑一定最終回到起點。我們將這條路徑已構(gòu)造好的路徑組合成一條路徑。如果必要,這一論證重復(fù)下去,直到我們得到一條通過圖中所有邊的路徑,即歐拉路徑。因此充分性得證。,例2 (a)一筆畫問題。就是判斷一個圖形能否一筆畫成,實質(zhì)上就是判斷圖形是否存在歐拉路
39、徑和歐拉回路的問題。例如,圖8.2―9(a)和(b)均可一筆畫成,因為符合存在歐拉路徑和歐拉回路條件。,(b)我們想知道是否可能將28塊不同的多米諾骨牌排成一個圓形,使得在這個排列中,每兩塊相鄰的多米諾骨牌其相鄰的兩個半面是相同的。我們構(gòu)造一個具有7個頂點的圖,這些頂點對應(yīng)于空白、1、2、3、4、5和6,在每兩個頂點之間都有一條邊,我們把這條邊當(dāng)作一塊多米諾骨牌,并且把這條邊相關(guān)聯(lián)的兩個頂點當(dāng)作它的兩個半面。,圖 8.2―9,定理8.
40、2―5一個有向連通圖具有歐拉回路,當(dāng)且僅當(dāng)它的每個頂點的引入次數(shù)等于引出次數(shù)。一個有向連通圖具有歐拉路徑,當(dāng)且僅當(dāng)它的每個頂點的引入次數(shù)等于引出次數(shù),可能有兩個頂點是例外,其中一個頂點的引入次數(shù)比它的引出次數(shù)大1,另一個頂點的引入次數(shù)比它的引出崐次數(shù)小1。證明是類似的,不重復(fù)。,例3布魯英(DeBruijn)序列?,F(xiàn)以旋轉(zhuǎn)鼓設(shè)計為例說明布魯英序列。 旋轉(zhuǎn)鼓的表面分成8塊扇形,如圖8.2―10所示。圖中陰影區(qū)表示
41、用導(dǎo)電材料制成,空白區(qū)用絕緣材料制成,終端a、b和c是接地或不是接地分別用二進制信號0或1表示。因此,鼓的位置可用二進制信號表示。試問應(yīng)如何選取這8個扇形的材料使每轉(zhuǎn)過一個扇形都得到一個不同的二進制信號,即每轉(zhuǎn)一周,能得到000到111的8個數(shù)。,圖 8.2―10,圖 8.2―10,8.2.5 哈密爾頓路徑與哈密爾頓回路 在無向圖G=〈V,E〉中,穿程于G的每個結(jié)點一次且僅一次的路徑稱為哈密爾頓路徑。穿程于G的
42、每個結(jié)點一次且僅一次的回路稱為哈密爾頓回路。具有哈密爾頓回路的圖稱為哈密爾頓圖。 哈密爾頓,愛爾蘭數(shù)學(xué)家,1859年他首先提出這一類問題。它的問題如下: 如何沿12面體的棱線,通過每個角一次且僅一次?(稱為環(huán)游全世界游戲。),圖 8.2―11,定理8.2―6 若G=〈V,E〉是哈密爾頓圖,則對V的每個非空真子集S均成立: ω(
43、G-S)≤|S| 這里|S|表示S中的頂點數(shù),ω(G-S)表示G刪去頂點集S后得到的圖的連通分圖個數(shù)。 證 設(shè)C是圖的一條哈密爾頓回路,則對于V的任一非空真子集S有 ω(C-S)≤|S|,這里ω(C-S),是C刪去子集S后得到的圖的分圖個數(shù)。但G是由C和一些不在C中的邊構(gòu)成的,C-S是G-S的生成子圖,所以
44、 ω(G-S)≤ω(C-S)≤|S| 應(yīng)用本定理可以判定某些圖不是哈密爾頓圖,例如,圖8.2―12所示的圖,刪去其中3個黑點,即知此圖不符合必要條件,因而不是哈密爾頓圖。但一般要考察多個真子集,應(yīng)用不方便,例4給出了一種較簡便的否定一個圖是哈密爾頓圖的方法,但也不是通用的。,圖 8.2―12,例4 證明圖8.2―13(a)中的圖沒有哈密爾頓路徑。 證用A標記頂點
45、a,所有與A鄰接的頂點標記為B。繼續(xù)不斷地用A標記所有鄰接于B的頂點,用B標記所有鄰接于A的頂點,直到所有頂點標記完,得到如圖8.2―13(b)所示的圖,圖中有3個頂點標A和5個頂點標B,標號A和B崐相差2個,因此不可能存在一條哈密爾頓路徑。,圖 8.2―13,定理8.2―6中的條件不是充分的,圖8.1―5中給出的彼得森圖,它對任意SV都滿足ω(G-S)≤|S|,但不是哈密爾頓圖。 定理8.2―7設(shè)G=〈V,E
46、〉是具有n個頂點的簡單無向圖,若在G中每一對頂點的次數(shù)之和大于等于n,則在G中存在一條哈密爾頓回路。,證用反證法。設(shè)G是符合題設(shè)條件,但不是哈密爾頓圖,通過把不相鄰的頂點加邊,總可得到一個最大的非哈密爾頓圖G′。由于G′是最大的非哈密爾頓圖,所以給G′的不相鄰的頂點u和v加上邊(u,v),這時有(v1,v2,…,vn,v1)這條哈密爾頓回路,不妨設(shè)v1=u,vn=v,因為回路必經(jīng)過(u,v)。于是必存在兩個相鄰的頂點vi和vi-1使v1
47、與vi,vi-1與vn相鄰,如圖8.2―14所示。若不然,設(shè)在G′中v1與 相鄰,而vn與 都不相鄰,則deg(vn)≤n-k-1,這樣deg(v1)+deg(vn)≤n-1<n,與題設(shè)不符。,圖 8.2―14,v1與vi相鄰,vn與vi-1相鄰,于是G′存在一條哈密爾頓回路(v1,v2,…,vi-1,vn,vn-1,…,vi+
48、1,vi,v1),但這與G′是最大的非哈密爾頓圖矛盾。證畢。 容易看出定理8.2―7的條件是充分的但非必要。例如,設(shè)G是一個n邊形,n>5,任何兩個頂點的度數(shù)之和是4,但在G中有一條哈密爾頓回路。,推論8.2―7在簡單無向圖中,若每一頂點的度數(shù) ,則該圖是哈密爾頓圖。 在有向圖中,也可類似地定義出哈密爾頓有向回路和哈密爾頓有向
49、路徑,但結(jié)論不全相似,限于篇幅不詳述了,現(xiàn)在介紹一個與哈密爾頓回路有聯(lián)系的問題——巡回售貨員問題。,一個售貨員希望去訪問n個城市的每一個,開始和結(jié)束于v1城市。每兩城市間都有一條直接通路,我們記vi城市到vj城市的距離為W(i,j),問題是去設(shè)計一個算法,它將找出售貨員能采取的最短路徑。 這個問題用圖論術(shù)語敘述就是:G=〈V,E,W〉是n個頂點的無向完全圖,這里W是從E到正實數(shù)集的一個函數(shù),對在V中任意三點vi,
50、vj,vk滿足 W(i,j)+W(j,k)≥W(i,k) 試求出賦權(quán)圖上的最短哈密爾頓回路。,至今未找出有效的方法,但已找到了若干近似算法,現(xiàn)介紹其一——最鄰近算法,它為巡回售貨員問題得出一個近似解。 (1)選任意點作為始點,找出一個與始點最近的點,形成一條邊的初始路徑。然后用第(2)步方法逐點擴充這條路徑。 (2)設(shè)x表示最新
51、加到這條路徑上的點,從不在路徑上的所有點中,選一個與x最鄰近的點,把連接x與此點的邊加到這條路徑中。重復(fù)這一步,直至G中所有頂點包含在路徑中。,圖 8.2―15,(3)把始點和最后加入的頂點之間的邊放入,這樣就得出一個回路。 例如,對于圖8.2―15(a)所示的圖,如果我們從a點開始,根據(jù)最鄰近算法構(gòu)造一個哈密爾頓回路,過程如圖(b)到(e)所示,所得回路的總距離是44, 其實圖8.2―15(
52、a)的最小哈密爾頓回路應(yīng)如(f)所示,總距離是43。,8.4 二部圖,定義8.4―1若無向圖G=〈V,E〉的頂點集合V可以劃分成兩個子集X和Y,使G中的每一條邊e的一個端點在X中,另一個端點在Y中,則稱G為二部圖或偶圖。二部圖可記為G=〈X,E,Y〉,X和Y稱為互補結(jié)點子集。 由定義可知,二部圖不會有自回路。,,定義8.4―2二部圖G=〈X,E,Y〉中,若X的每一頂點都與Y的每一頂點鄰接,則稱G為完全二部圖
53、,記為Km,n,這里m=|X|,n=|Y|。 下圖給出K2,4和K3,3的圖示。,定理8.4―1無向圖G=〈V,E〉為二部圖的充分必要條件為G中所有回路的長度均為偶數(shù)。 定義8.4―3給定一個二部圖G=〈X,E,Y〉,如果E的子集M中的邊無公共端點,則稱M為二部圖G的一個匹配。含有最多邊數(shù)的匹配稱為G的最大匹配。 例如,下圖中,M={(x1,y5),(x3,
54、y1),(x4,y3)}是G的一個匹配。求最大匹配要應(yīng)用交替鏈概念,其定義如下。,,,定義8.4―4如果二部圖G中的一條鏈由不屬于匹配M的邊和屬于M的邊交替組成,且鏈的兩端點不是M中邊的端點,那么稱此鏈為G中關(guān)于匹配M的交替鏈。 例如,下圖中的(x2,y1,x3,y4)是交替鏈。,交替鏈可用標記法找出,標記法的過程如下: 首先把X中所有不是M的邊的端點用()加以標記,然后交替進行以下所述
55、的過程Ⅰ和Ⅱ。 Ⅰ.選一個X的新標記過的結(jié)點,比如說xi,用(xi)標記不通過在M中的邊與xi鄰接且未標記過的Y的所有結(jié)點。對所有X的新標記過的結(jié)點重復(fù)這一過程。 Ⅱ.選一個Y的新標記過的結(jié)點,比如說yi,用(yi)標記通過M的邊與yi鄰接且未標記過的X的所有結(jié)點。對所有Y的新標記過結(jié)點重復(fù)這一過程。,例如,在下圖中,可用如下標記過程: (1) 把x’2標記(*)。
56、 (2) 從x2出發(fā),應(yīng)用過程Ⅰ,把y1和y3標記(x2)。 (3)從y1出發(fā),應(yīng)用過程Ⅱ,把x3標記(y1)。從y3出發(fā),應(yīng)用過程Ⅱ,把x4標記(y3)。 (4)從x3出發(fā),應(yīng)用過程Ⅰ,把y4標記(x3),因y4不是M中邊的端點,說明已找到了一條交替鏈,即(x2,y1,x3,y4)。,在二部圖G中,如果能找出一條關(guān)于匹配M的交替鏈γ,則把γ中屬于M的邊從M中刪去,
57、而把γ中不屬于M的邊添到M中,得到一新集合M′,此M′也是G的匹配。這是因為添入的邊自身不相交,又不與M中不屬于γ的邊相交。例如在圖8.4―2中作這樣變換后,所得的M′(用粗黑線標出)如圖8.4―3所示。但M′比M多一條邊。因此,反復(fù)進行這樣的過程,直至找不出關(guān)于M的交替鏈為止,就可崐求出G的最大匹配,即M。,圖 8.4―3,例1求出圖8.4―4中的二部圖的最大匹配。解步驟、操作內(nèi)容及M情況(1)置M為 M=
58、(2) 找出一條邊的交替鏈(x2,y2) M={(x2,y2)}(3)找出一條邊的交替鏈(x3,y3) M={(x2,y2),(x3,y3)}(4)找出一條邊的交替鏈(x4,y4) M={(x2,y2),(x3,y3),(x4,y4)},(5)用標記法找出交替鏈(x1,y3,x3,y2,x2,y1),進行變換得
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 離散數(shù)學(xué)第7章-圖論-習(xí)題
- 離散數(shù)學(xué)圖論
- 離散數(shù)學(xué)-第8章-函數(shù)
- 離散數(shù)學(xué)圖論復(fù)習(xí)
- 離散數(shù)學(xué)第5章
- 離散數(shù)學(xué)第7章
- 離散數(shù)學(xué)第4章
- 第01章-離散數(shù)學(xué)
- 離散數(shù)學(xué)第1章習(xí)題
- 離散數(shù)學(xué)第4章屈
- 離散數(shù)學(xué)第1章屈
- 離散數(shù)學(xué)第2章第1節(jié)
- 離散數(shù)學(xué)第1章習(xí)題答案
- 離散數(shù)學(xué)課件第1章
- 離散數(shù)學(xué)課件第6章
- 離散數(shù)學(xué)高教版第3章
- 離散數(shù)學(xué)課件第7章
- 離散數(shù)學(xué)高教版第4章
- 離散數(shù)學(xué)第10章-謂詞邏輯
- 離散數(shù)學(xué)課件第2章
評論
0/150
提交評論