離散數(shù)學(xué)第8章圖論

1、第8章 圖論,8.1 圖的基本概念 8.2 路徑和回路8.３ 圖的矩陣表示8.４ 二部圖8.5 平面圖8.6 樹8.7 有向樹8.8 運(yùn)輸網(wǎng)絡(luò),問題是要從這四塊陸地中任何一塊開始，通過(guò)每一座橋正好一次，再回到起點(diǎn)。 歐拉在1736年解決了這個(gè)問題 。,判定法則：如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿足要求的路線便不存在了。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若

2、沒有一個(gè)地 方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn),定義8.1―1 一個(gè)圖G是一個(gè)三重組〈V(G),E(G),ΦG〉,其中V(G)是一個(gè)非空的結(jié)點(diǎn)(或叫頂點(diǎn))集合,E(G)是邊的集合,ΦG是從邊集E到結(jié)點(diǎn)偶對(duì)集合上的函數(shù)。一個(gè)圖可以用一個(gè)圖形表示。 例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é)點(diǎn)偶對(duì)可以是有序的,也可以是無(wú)序的。若邊e所對(duì)應(yīng)的偶對(duì)〈a,b〉是有序的,則稱e是有向邊。有向邊簡(jiǎn)稱弧,a叫弧e的始點(diǎn),b叫弧e的終點(diǎn),統(tǒng)稱為e的端點(diǎn)。稱e是關(guān)聯(lián)于結(jié)點(diǎn)a和b的,結(jié)點(diǎn)a和結(jié)點(diǎn)b是鄰

4、接的。若邊e所對(duì)應(yīng)的偶對(duì)(a,b)是無(wú)序的,則稱e是無(wú)向邊。無(wú)向邊簡(jiǎn)稱棱,除無(wú)始點(diǎn)和終點(diǎn)的術(shù)語(yǔ)外,其它術(shù)語(yǔ)與有向邊相同。 每一條邊都是有向邊的圖稱為有向圖, 第三章中的關(guān)系圖都是有向圖的例子。每一條邊都是無(wú)向邊的圖稱為無(wú)向圖；如果在圖中一些邊是有向邊,而另一些邊是無(wú)向邊,則稱這個(gè)圖是混合圖。我們僅討論有向圖和無(wú)向圖,且V(G)和E(G)限于有限集合。,約定用〈a,b〉表示有向邊,(a,b)表示無(wú)向邊,既表示有向邊

5、又表示無(wú)向邊時(shí)用［a,b］。 有向圖和無(wú)向圖也可互相轉(zhuǎn)化。例如,把無(wú)向圖中每一條邊都看作兩條方向不同的有向邊,這時(shí)無(wú)向圖就成為有向圖。又如,把有向圖中每條有向邊都看作無(wú)向邊,就得到無(wú)向圖。這個(gè)無(wú)向圖習(xí)慣上叫做該有向圖的底圖。 在圖中,不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為弧立結(jié)點(diǎn)；全由孤立結(jié)點(diǎn)構(gòu)成的圖稱為零圖。關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊稱為自回路；自回路的方向不定。自回路的有無(wú)不使有關(guān)圖論的各個(gè)定理發(fā)生重大變化,所以有許多場(chǎng)合都略去

6、自回路。,在有向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若同始點(diǎn)和同終點(diǎn)的邊多于一條,則這幾條邊稱為平行邊。在無(wú)向圖中,兩結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若多于一條邊,則稱這幾條邊為平行邊。兩結(jié)點(diǎn)a、b間互相平行的邊的條數(shù)稱為邊［a,b］的重?cái)?shù)。僅有一條時(shí)重?cái)?shù)為1,無(wú)邊時(shí)重?cái)?shù)為0。 定義8.1―2含有平行邊的圖稱為多重圖。非多重圖稱為線圖。無(wú)自回路的線圖稱為簡(jiǎn)單圖。 在圖8.1―3中,(a)、(b)是多

7、重圖,(c)是線圖,(d)是簡(jiǎn)單圖,關(guān)系圖都是線圖。,圖 8.1―3,定義 8.1―3賦權(quán)圖G是一個(gè)三重組 〈V,E,g〉或四重組〈V,E,f,g〉,其中V是結(jié)點(diǎn)集合, E是邊的集合,f是定義在V上的函數(shù),g是定義在E上的函數(shù)。 右圖給出一個(gè)賦權(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é)點(diǎn)的次數(shù) 定義8.1―4在有向圖中,對(duì)于任何結(jié)點(diǎn)v,以v為始點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引出次數(shù)(或出度),記為deg+(v);以v為終點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引入次數(shù)(或入度),記為deg-(v);結(jié)點(diǎn)v的引出次數(shù)和引入次數(shù)之和稱為結(jié)點(diǎn)v的次數(shù)(或度數(shù)),記作deg(v)。在無(wú)向圖中,結(jié)點(diǎn)v的次數(shù)是與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù),也記為deg(v)。孤

9、立結(jié)點(diǎn)的次數(shù)為零。,定理8.1―1 設(shè)G是一個(gè)(n,m)圖,它的結(jié)點(diǎn)集合為V={v1,v2,…,vn},則,證 因?yàn)槊恳粭l邊提供兩個(gè)次數(shù),而所有各結(jié)點(diǎn)次數(shù)之和為m條邊所提供,所以上式成立。 在有向圖中,上式也可寫成:,定理8.1―2在圖中,次數(shù)為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。 證 設(shè)次數(shù)為偶數(shù)的結(jié)點(diǎn)有n1個(gè),記為 (i=1,2,…,n1)。次數(shù)為奇數(shù)的結(jié)點(diǎn)有n2個(gè),記為 (i=1,2,

10、…,n2)。由上一定理得,因?yàn)榇螖?shù)為偶數(shù)的各結(jié)點(diǎn)次數(shù)之和為偶數(shù)。所以前一項(xiàng)次數(shù)為偶數(shù);若n2為奇數(shù),則第二項(xiàng)為奇數(shù),兩項(xiàng)之和將為奇數(shù),但這與上式矛盾。故n2必為偶數(shù)。證畢。,,圖 8.1―5,定義8.1―5各結(jié)點(diǎn)的次數(shù)均相同的圖稱為正則圖,各結(jié)點(diǎn)的次數(shù)均為k時(shí)稱為k―正則圖。 下圖所示的稱為彼得森(Petersen)圖,是3―正則圖。,8.1.3 圖的同構(gòu) 定義8.1.6設(shè)G=〈V

11、,E〉和G′=〈V′,E′〉是兩個(gè)圖,若存在從V到V′的雙射函數(shù)Φ,使對(duì)任意a、b∈V,［a,b∈E當(dāng)且僅當(dāng)［Φ(a),Φ(b)］∈E′,并且［a,b］和［Φ(a),Φ(b)］有相同的重?cái)?shù),則稱G和G′是同構(gòu)的。 上述定義說(shuō)明,兩個(gè)圖的各結(jié)點(diǎn)之間,如果存在一一對(duì)應(yīng)關(guān)系,而且這種對(duì)應(yīng)關(guān)系保持了結(jié)點(diǎn)間的鄰接關(guān)系(在有向圖時(shí)還保持邊的方向)和邊的重?cái)?shù),則這兩個(gè)圖是同構(gòu)的,兩個(gè)同構(gòu)的圖除了頂點(diǎn)和邊的名稱不同外實(shí)際上代表同樣

12、的組合結(jié)構(gòu)。,,例2 (a)、(b)兩圖是同構(gòu)的。因?yàn)榭勺饔成?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é)點(diǎn)數(shù)相等; (2) 邊數(shù)相等; (3) 度數(shù)相同的結(jié)點(diǎn)數(shù)

13、相等。 但這不是充分條件。例如下圖中(a)、(b)兩圖雖然滿足以上3條件,但不同構(gòu)。(a)中的x應(yīng)與(b)中的y對(duì)應(yīng),因?yàn)榇螖?shù)都是3。但(a)中的x與兩個(gè)次數(shù)為1的點(diǎn)u,v鄰接,而(b)中的y僅與一個(gè)次數(shù)為1的點(diǎn)w鄰接。,8.1.4 圖的運(yùn)算  圖的常見運(yùn)算有并、交、差、環(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)的頂點(diǎn)}。 (4)G1與G2的環(huán)和,定義為圖G3＝〈V3,E

15、3〉,G3=(G1∪G2)-(G1∩G2),記為G3=G1G2。,除以上4種運(yùn)算外,還有以下兩種操作: (1) 刪去圖G的一條邊e; (2)刪去圖G的一個(gè)結(jié)點(diǎn)v。它的實(shí)際意義是刪去結(jié)點(diǎn)v和與v關(guān)聯(lián)的所有邊。,8.1.5 子圖與補(bǔ)圖 定義8.1―8設(shè)G=〈V,E〉和G′=〈V′,E′〉是兩個(gè)圖。 (1) 如果V′ V和E′ E,則稱G′是G的子圖。如果V′ V和E′

16、 E,則稱G′ G的真子圖。(注意:“G′是圖”已隱含著“E′中的邊僅關(guān)聯(lián)V′中的結(jié)點(diǎn)”的意義。) (2) 如果V′=V和E′ E,則稱G′為G的生成子圖。 (3) 若子圖G′中沒有孤立結(jié)點(diǎn),G′由E′唯一確定,則稱G′為由邊集E′導(dǎo)出的子圖。,(4)若在子圖G′中,對(duì)V′中的任意二結(jié)點(diǎn)u、v,當(dāng)［u,v］∈E時(shí)有［u,v］∈E′,則G′由V′唯一確定,此時(shí)稱G′為由結(jié)點(diǎn)集V′

17、導(dǎo)出的子圖。,定義8.1―9在n個(gè)結(jié)點(diǎn)的有向圖G=〈V,E〉中,如果E=V×V,則稱G為有向完全圖;在n個(gè)結(jié)點(diǎn)的無(wú)向圖G=〈V,E〉中,如果任何兩個(gè)不同結(jié)點(diǎn)間都恰有一條邊,則稱G為無(wú)向完全圖,記為Kn。 圖8.1―11是4個(gè)結(jié)點(diǎn)的有向完全圖和無(wú)向完全圖的圖示。 定義8.1―10 設(shè)線圖G=〈V,E〉有n個(gè)頂點(diǎn),線圖H=〈V,E′〉也有同樣的頂點(diǎn),而E′是由n個(gè)頂點(diǎn)的完全圖的邊刪

18、去E所得,則圖H稱為圖G的補(bǔ)圖,記為 ,顯然, 。,8.2 路徑和回路,8.2.1 路徑和回路 定義8.2―1在有向圖中,從頂點(diǎn)v0到頂點(diǎn)vn的一條路徑是圖的一個(gè)點(diǎn)邊交替序列（v0e1v1e2v2…envn）,其中vi-1和vi分別是邊ei的始點(diǎn)和終點(diǎn),i=1,2,…,n。在序列中,如果同一條邊不出現(xiàn)兩次,則稱此路徑是簡(jiǎn)單路徑,如果同一頂點(diǎn)不出現(xiàn)兩次,則

19、稱此路徑是基本路徑(或叫鏈)。,基本路徑也一定是簡(jiǎn)單路徑。,如果路徑的始點(diǎn)v0和終點(diǎn)vn相重合,即v0=vn,則此路徑稱為回路,沒有相同邊的回路稱為簡(jiǎn)單回路,通過(guò)各頂點(diǎn)不超過(guò)一次的回路稱為基本回路。 (a)P1=(v1e1v2e7v5) 是一條基本路徑。 (b)P2=(v2e2v3e3v3e4v1e1v2) 是一簡(jiǎn)單回路 非基本回路。,,,在無(wú)向圖上,以上各術(shù)語(yǔ)的定義完

20、全類似,故不重復(fù)。路徑和回路可僅用邊的序列表示,在非多重圖時(shí)也可用頂點(diǎn)序列表示。,定義8.2―2 路徑P中所含邊的條數(shù)稱為路徑P的長(zhǎng)度。長(zhǎng)度為0的路徑定義為單獨(dú)一個(gè)頂點(diǎn)。(但注意習(xí)慣上不定義長(zhǎng)度為0的回路。) 定理8.2―1在一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖G=〈V,E〉中,如果從v1到v2有一條路徑,則從v1到v2有一條長(zhǎng)度不大于n-1的基本路徑。,簡(jiǎn)證 假定從v1到v2存在一條路徑,(v1,…,vi,…,v2)是所

21、經(jīng)的結(jié)點(diǎn),如果其中有相同的結(jié)點(diǎn)vk,例 (v1,…,vi,…,vk,…,vk,…,v2),則刪去從vk到vk的這些邊,它仍是從v1到v2的路徑,如此反復(fù)地進(jìn)行直至(v1,…,vi,…,v2)中沒有重復(fù)結(jié)點(diǎn)為止。此時(shí),所得的就是基本路徑?；韭窂降拈L(zhǎng)度比所經(jīng)結(jié)點(diǎn)數(shù)少1,圖中共n個(gè)結(jié)點(diǎn),故基本路徑長(zhǎng)度不超過(guò)n-1。,定理8.2―2在一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖G=〈V,E〉中,如果經(jīng)v1有一條簡(jiǎn)單回路,則經(jīng)v1有一條長(zhǎng)度不超過(guò)n的基本回路。

22、 定義8.2―3在圖G=〈V,E〉中,從結(jié)點(diǎn)vi到vj最短路徑的長(zhǎng)度叫從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可達(dá)。vi自身認(rèn)為從vi可達(dá)。 定義8.2―5在無(wú)向圖G中,如果任兩結(jié)點(diǎn)可達(dá),則稱圖G是連通的;如果G的子圖G′是連通的,沒有包含G′的更大的子圖G″是連通的,則稱G′是G

24、的連通分圖(簡(jiǎn)稱分圖)。,,圖 8.2―2,一個(gè)無(wú)向圖或者是一個(gè)連通圖,如圖8.2―2(a)所示,或者是由若干個(gè)連通分圖組成,如圖8.2―2(b)所示。,定理8.2―3設(shè)G是任一(n,m)無(wú)向簡(jiǎn)單圖,ω是其分圖個(gè)數(shù),則,定義8.2―6在有向圖中,如果在任兩結(jié)點(diǎn)偶對(duì)中,至少?gòu)囊粋€(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的,則稱圖G是單向連通的;如果在任兩結(jié)點(diǎn)偶對(duì)中,兩結(jié)點(diǎn)都互相可達(dá),則稱圖G是強(qiáng)連通的;如果它的底圖是連通的,則稱圖G是弱連通的。,強(qiáng)連

25、通的也一定是單向連通和弱連通的,單向連通的一定是弱連通的,但其逆均不真。在下圖中,(a)是強(qiáng)連通的,(b)是單向連通的,(c)是弱連通的。,定義8.2―7在有向圖G=〈V,E〉中,G′是G的子圖,若G′是強(qiáng)連通的(單向連通的,弱連通的),沒有包含G′的更大子圖G″是強(qiáng)連通的(單向連通的,弱連通的),則稱G′是G的強(qiáng)分圖(單向分圖,弱分圖)。 在下圖中,強(qiáng)分圖集合是: {〈{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〉是個(gè)賦權(quán)圖,W是從E到正實(shí)數(shù)集合的函數(shù),邊［i,j］的權(quán)記為W(i,j),稱為邊的長(zhǎng)度。若i和j之間沒

28、有邊,那么W(i,j)=∞。路徑P的長(zhǎng)度定義為路徑中邊的長(zhǎng)度之和,記為W(P)。圖G中從結(jié)點(diǎn)u到結(jié)點(diǎn)v的距離記為d(u,v),定義為 min{W(P)|P為G中從u到v的路徑} ∞ 當(dāng)從u到v不可達(dá)時(shí),本小節(jié)主要討論在一個(gè)賦權(quán)的簡(jiǎn)單連通無(wú)向圖 G=〈V,E,W〉中,求一結(jié)點(diǎn)a(稱為源點(diǎn))到其它結(jié)點(diǎn)x

29、的最短路徑的長(zhǎng)度,通常稱它為單源問題。下面介紹1959年迪克斯特拉(E.W.Dijkstra)提出的單源問題的算法,其要點(diǎn)如下: (1) 把V分成兩個(gè)子集S和T。初始時(shí),S={a},T=V-S。 (2) 對(duì)T中每一元素t計(jì)算D(t),根據(jù)D(t)值找出T中距a最短的一結(jié)點(diǎn)x,寫出a到x的最短路徑的長(zhǎng)度D(x)。 (3)置S為S∪{x},置T為T-{x},若T=

30、,則停止,否則再重復(fù)2。,算法中步驟(1)和(3)是清楚的,現(xiàn)在對(duì)2給以說(shuō)明。 D(t)表示從a到t的不包含T中其它結(jié)點(diǎn)的最短通路的長(zhǎng)度,但D(t)不一定是從a到t的距離,因?yàn)閺腶到t可能有包含T中另外結(jié)點(diǎn)的更短通路。 首先我們證明“若x是T中具有最小D值的結(jié)點(diǎn),則D(x)是從a到x的距離”,用反證法。若另有一條含有T中另外結(jié)點(diǎn)的更短通路,不妨設(shè)這個(gè)通路中第一個(gè)屬于T-{x}的結(jié)點(diǎn)是t

31、1,于是D(t1)＜D(x),但這與題設(shè)矛盾。可見以上斷言成立。,其次說(shuō)明計(jì)算D(t)的方法。初始時(shí),D(t)=W(a,t),現(xiàn)在我們假設(shè)對(duì)T中的每一個(gè)t已計(jì)算了D值。設(shè)x是T中D值最小的一個(gè)結(jié)點(diǎn),記S′=S∪｛x},T′=T-{x},令D′(t)表示T′中結(jié)點(diǎn)t的D值,則 D′(t)=min［D(t),D(x)+W(x,t)］ 現(xiàn)分情況證明上式。,(a)如果從a到t有一條最短路徑,它不包

32、含T′中的其它結(jié)點(diǎn),也不含x點(diǎn),則D′(t)=D(t)。 (b)如果從a到t有一條最短路徑,它從a到x不包含T′中的結(jié)點(diǎn),接著是邊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。因?yàn)镈(v1)=2是T中最小的D值,所以選x=v1。

33、 置S為S∪{x}={a,v1},置T為T-{x}={v2,v3,v4}。然后計(jì)算: D(v2)=min(+∞,2+3)=5 D(v3)=min(+∞,+∞)=+∞ D(v4)=min(10,2+7)=9 如此類推,直至T= 終止。整個(gè)過(guò)程概括于表8.2―1中。,圖 8.2―7,表 8.2―1,8.2.4 歐

34、拉路徑和歐拉回路 哥尼斯堡(Konigsberg,現(xiàn)加里寧格勒)位于普雷格爾(Pregel)河畔,河中有兩島。城市的各部分由7座橋接通,如圖8.2―8(a)所示。古時(shí)城中居民熱衷于一個(gè)問題:游人從任一地點(diǎn)出發(fā),怎樣才能做到穿過(guò)每座橋一次且僅一次后又返回原出發(fā)地。1736年歐拉用圖論方法解決了此問題,寫了第一篇圖論的論文,從而成為圖論的創(chuàng)始人。,不難看出,如果用結(jié)點(diǎn)代表陸地,用邊代表橋,哥尼斯堡七橋問題就等價(jià)在于圖

35、8.2―8(b)中找到這樣一條路徑,它穿程每條邊一次且僅一次。  穿程于圖G的每條邊一次且僅一次的路徑,稱為歐拉路徑。穿程于圖G的每條邊一次且僅一次的回路,稱為歐拉回路,具有歐拉回路的圖稱為歐拉圖。 顯然,具有歐拉路徑的圖除孤立結(jié)點(diǎn)外是連通的,而孤立結(jié)點(diǎn)不影響歐拉路徑的討論。因此,下邊討論歐拉路徑有關(guān)問題時(shí)均假定圖是連通的。,圖 8.2―8,定理8.2―4無(wú)向連通圖G具有一條歐拉路徑

36、當(dāng)且僅當(dāng)G具有零個(gè)或兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)。 證必要性。如果圖具有歐拉路徑,那么順著這條路徑畫出的時(shí)候,每次碰到一個(gè)頂點(diǎn),都需通過(guò)關(guān)聯(lián)于這個(gè)頂點(diǎn)的兩條邊,并且這兩條邊在以前未畫過(guò)。因此,除路徑的兩端點(diǎn)外,圖中任何頂點(diǎn)的次數(shù)必是偶數(shù)。如果歐拉路徑的兩端點(diǎn)不同,那么它們就是僅有的兩個(gè)奇數(shù)頂點(diǎn),如果它們是重合的,那么所有頂點(diǎn)都有偶數(shù)次數(shù),并且這條歐拉路徑成為一條歐拉回路。因此必要性得證。,充分性。我們從兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)

37、之一開始(若無(wú)奇數(shù)次數(shù)的頂點(diǎn),可從任一點(diǎn)開始),構(gòu)造一條歐拉路徑。以每條邊最多畫一次的方式通過(guò)圖中的邊。對(duì)于偶數(shù)次數(shù)的頂點(diǎn),通過(guò)一條邊進(jìn)入這個(gè)頂點(diǎn),總可通過(guò)一條未畫過(guò)的邊離開這個(gè)頂點(diǎn)。因此,這樣的構(gòu)造過(guò)程一定以到達(dá)另一個(gè)奇數(shù)次數(shù)頂點(diǎn)而告終(若無(wú)奇數(shù)次數(shù)的頂點(diǎn),則以回到原出發(fā)點(diǎn)而告終)。如果圖中所有邊已用這種方法畫過(guò),顯然,這就是所求的歐拉路徑。如果圖中不是所有邊被畫過(guò),我們?nèi)サ粢旬嬤^(guò)的邊,得到由剩下邊組成的一個(gè)子圖,這個(gè)子圖的頂點(diǎn)次數(shù)全

38、是偶數(shù)。,并且因?yàn)樵瓉?lái)的圖是連通的,因此,這個(gè)子圖必與我們已畫過(guò)的路徑在一個(gè)點(diǎn)或多個(gè)點(diǎn)相接。由這些頂點(diǎn)中的一個(gè)開始,我們?cè)偻ㄟ^(guò)邊構(gòu)造路徑,因?yàn)轫旤c(diǎn)次數(shù)全是偶數(shù),因此,這條路徑一定最終回到起點(diǎn)。我們將這條路徑已構(gòu)造好的路徑組合成一條路徑。如果必要,這一論證重復(fù)下去,直到我們得到一條通過(guò)圖中所有邊的路徑,即歐拉路徑。因此充分性得證。,例2 (a)一筆畫問題。就是判斷一個(gè)圖形能否一筆畫成,實(shí)質(zhì)上就是判斷圖形是否存在歐拉路

39、徑和歐拉回路的問題。例如,圖8.2―9(a)和(b)均可一筆畫成,因?yàn)榉洗嬖跉W拉路徑和歐拉回路條件。,(b)我們想知道是否可能將28塊不同的多米諾骨牌排成一個(gè)圓形,使得在這個(gè)排列中,每?jī)蓧K相鄰的多米諾骨牌其相鄰的兩個(gè)半面是相同的。我們構(gòu)造一個(gè)具有7個(gè)頂點(diǎn)的圖,這些頂點(diǎn)對(duì)應(yīng)于空白、1、2、3、4、5和6,在每?jī)蓚€(gè)頂點(diǎn)之間都有一條邊,我們把這條邊當(dāng)作一塊多米諾骨牌,并且把這條邊相關(guān)聯(lián)的兩個(gè)頂點(diǎn)當(dāng)作它的兩個(gè)半面。,圖 8.2―9,定理8.

40、2―5一個(gè)有向連通圖具有歐拉回路,當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的引入次數(shù)等于引出次數(shù)。一個(gè)有向連通圖具有歐拉路徑,當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的引入次數(shù)等于引出次數(shù),可能有兩個(gè)頂點(diǎn)是例外,其中一個(gè)頂點(diǎn)的引入次數(shù)比它的引出次數(shù)大1,另一個(gè)頂點(diǎn)的引入次數(shù)比它的引出崐次數(shù)小1。證明是類似的,不重復(fù)。,例3布魯英(DeBruijn)序列?，F(xiàn)以旋轉(zhuǎn)鼓設(shè)計(jì)為例說(shuō)明布魯英序列。 旋轉(zhuǎn)鼓的表面分成8塊扇形,如圖8.2―10所示。圖中陰影區(qū)表示

41、用導(dǎo)電材料制成,空白區(qū)用絕緣材料制成,終端a、b和c是接地或不是接地分別用二進(jìn)制信號(hào)0或1表示。因此,鼓的位置可用二進(jìn)制信號(hào)表示。試問應(yīng)如何選取這8個(gè)扇形的材料使每轉(zhuǎn)過(guò)一個(gè)扇形都得到一個(gè)不同的二進(jìn)制信號(hào),即每轉(zhuǎn)一周,能得到000到111的8個(gè)數(shù)。,圖 8.2―10,圖 8.2―10,8.2.5 哈密爾頓路徑與哈密爾頓回路 在無(wú)向圖G=〈V,E〉中,穿程于G的每個(gè)結(jié)點(diǎn)一次且僅一次的路徑稱為哈密爾頓路徑。穿程于G的

42、每個(gè)結(jié)點(diǎn)一次且僅一次的回路稱為哈密爾頓回路。具有哈密爾頓回路的圖稱為哈密爾頓圖。 哈密爾頓,愛爾蘭數(shù)學(xué)家,1859年他首先提出這一類問題。它的問題如下: 如何沿12面體的棱線,通過(guò)每個(gè)角一次且僅一次?(稱為環(huán)游全世界游戲。),圖 8.2―11,定理8.2―6 若G=〈V,E〉是哈密爾頓圖,則對(duì)V的每個(gè)非空真子集S均成立: ω(

43、G-S)≤｜S｜ 這里|S|表示S中的頂點(diǎn)數(shù),ω(G-S)表示G刪去頂點(diǎn)集S后得到的圖的連通分圖個(gè)數(shù)。 證 設(shè)C是圖的一條哈密爾頓回路,則對(duì)于V的任一非空真子集S有 ω(C-S)≤|S|,這里ω(C-S),是C刪去子集S后得到的圖的分圖個(gè)數(shù)。但G是由C和一些不在C中的邊構(gòu)成的,C-S是G-S的生成子圖,所以

44、 ω(G-S)≤ω(C-S)≤|S| 應(yīng)用本定理可以判定某些圖不是哈密爾頓圖,例如,圖8.2―12所示的圖,刪去其中3個(gè)黑點(diǎn),即知此圖不符合必要條件,因而不是哈密爾頓圖。但一般要考察多個(gè)真子集,應(yīng)用不方便,例4給出了一種較簡(jiǎn)便的否定一個(gè)圖是哈密爾頓圖的方法,但也不是通用的。,圖 8.2―12,例4 證明圖8.2―13(a)中的圖沒有哈密爾頓路徑。 證用A標(biāo)記頂點(diǎn)

45、a,所有與A鄰接的頂點(diǎn)標(biāo)記為B。繼續(xù)不斷地用A標(biāo)記所有鄰接于B的頂點(diǎn),用B標(biāo)記所有鄰接于A的頂點(diǎn),直到所有頂點(diǎn)標(biāo)記完,得到如圖8.2―13(b)所示的圖,圖中有3個(gè)頂點(diǎn)標(biāo)A和5個(gè)頂點(diǎn)標(biāo)B,標(biāo)號(hào)A和B崐相差2個(gè),因此不可能存在一條哈密爾頓路徑。,圖 8.2―13,定理8.2―6中的條件不是充分的,圖8.1―5中給出的彼得森圖,它對(duì)任意SV都滿足ω(G-S)≤|S|,但不是哈密爾頓圖。 定理8.2―7設(shè)G=〈V,E

46、〉是具有n個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖,若在G中每一對(duì)頂點(diǎn)的次數(shù)之和大于等于n,則在G中存在一條哈密爾頓回路。,證用反證法。設(shè)G是符合題設(shè)條件,但不是哈密爾頓圖,通過(guò)把不相鄰的頂點(diǎn)加邊,總可得到一個(gè)最大的非哈密爾頓圖G′。由于G′是最大的非哈密爾頓圖,所以給G′的不相鄰的頂點(diǎn)u和v加上邊(u,v),這時(shí)有(v1,v2,…,vn,v1)這條哈密爾頓回路,不妨設(shè)v1=u,vn=v,因?yàn)榛芈繁亟?jīng)過(guò)(u,v)。于是必存在兩個(gè)相鄰的頂點(diǎn)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是一個(gè)n邊形,n＞5,任何兩個(gè)頂點(diǎn)的度數(shù)之和是4,但在G中有一條哈密爾頓回路。,推論8.2―7在簡(jiǎn)單無(wú)向圖中,若每一頂點(diǎn)的度數(shù) ,則該圖是哈密爾頓圖。 在有向圖中,也可類似地定義出哈密爾頓有向回路和哈密爾頓有向

49、路徑,但結(jié)論不全相似,限于篇幅不詳述了,現(xiàn)在介紹一個(gè)與哈密爾頓回路有聯(lián)系的問題——巡回售貨員問題。,一個(gè)售貨員希望去訪問n個(gè)城市的每一個(gè),開始和結(jié)束于v1城市。每?jī)沙鞘虚g都有一條直接通路,我們記vi城市到vj城市的距離為W(i,j),問題是去設(shè)計(jì)一個(gè)算法,它將找出售貨員能采取的最短路徑。 這個(gè)問題用圖論術(shù)語(yǔ)敘述就是:G=〈V,E,W〉是n個(gè)頂點(diǎn)的無(wú)向完全圖,這里W是從E到正實(shí)數(shù)集的一個(gè)函數(shù),對(duì)在V中任意三點(diǎn)vi,

50、vj,vk滿足 W(i,j)+W(j,k)≥W(i,k) 試求出賦權(quán)圖上的最短哈密爾頓回路。,至今未找出有效的方法,但已找到了若干近似算法,現(xiàn)介紹其一——最鄰近算法,它為巡回售貨員問題得出一個(gè)近似解。 (1)選任意點(diǎn)作為始點(diǎn),找出一個(gè)與始點(diǎn)最近的點(diǎn),形成一條邊的初始路徑。然后用第(2)步方法逐點(diǎn)擴(kuò)充這條路徑。 (2)設(shè)x表示最新

51、加到這條路徑上的點(diǎn),從不在路徑上的所有點(diǎn)中,選一個(gè)與x最鄰近的點(diǎn),把連接x與此點(diǎn)的邊加到這條路徑中。重復(fù)這一步,直至G中所有頂點(diǎn)包含在路徑中。,圖 8.2―15,(3)把始點(diǎn)和最后加入的頂點(diǎn)之間的邊放入,這樣就得出一個(gè)回路。 例如,對(duì)于圖8.2―15(a)所示的圖,如果我們從a點(diǎn)開始,根據(jù)最鄰近算法構(gòu)造一個(gè)哈密爾頓回路,過(guò)程如圖(b)到(e)所示,所得回路的總距離是44, 其實(shí)圖8.2―15(

52、a)的最小哈密爾頓回路應(yīng)如(f)所示,總距離是43。,8.４ 二部圖,定義8.4―1若無(wú)向圖G=〈V,E〉的頂點(diǎn)集合V可以劃分成兩個(gè)子集X和Y,使G中的每一條邊e的一個(gè)端點(diǎn)在X中,另一個(gè)端點(diǎn)在Y中,則稱G為二部圖或偶圖。二部圖可記為G=〈X,E,Y〉,X和Y稱為互補(bǔ)結(jié)點(diǎn)子集。 由定義可知,二部圖不會(huì)有自回路。,,定義8.4―2二部圖G=〈X,E,Y〉中,若X的每一頂點(diǎn)都與Y的每一頂點(diǎn)鄰接,則稱G為完全二部圖

53、,記為Km,n,這里m=｜X｜,n=｜Y｜。 下圖給出K2,4和K3,3的圖示。,定理8.4―1無(wú)向圖G=〈V,E〉為二部圖的充分必要條件為G中所有回路的長(zhǎng)度均為偶數(shù)。 定義8.4―3給定一個(gè)二部圖G=〈X,E,Y〉,如果E的子集M中的邊無(wú)公共端點(diǎn),則稱M為二部圖G的一個(gè)匹配。含有最多邊數(shù)的匹配稱為G的最大匹配。 例如,下圖中,M={(x1,y5),(x3,

54、y1),(x4,y3)}是G的一個(gè)匹配。求最大匹配要應(yīng)用交替鏈概念,其定義如下。,,,定義8.4―4如果二部圖G中的一條鏈由不屬于匹配M的邊和屬于M的邊交替組成,且鏈的兩端點(diǎn)不是M中邊的端點(diǎn),那么稱此鏈為G中關(guān)于匹配M的交替鏈。 例如,下圖中的(x2,y1,x3,y4)是交替鏈。,交替鏈可用標(biāo)記法找出,標(biāo)記法的過(guò)程如下: 首先把X中所有不是M的邊的端點(diǎn)用()加以標(biāo)記,然后交替進(jìn)行以下所述

55、的過(guò)程Ⅰ和Ⅱ。 Ⅰ.選一個(gè)X的新標(biāo)記過(guò)的結(jié)點(diǎn),比如說(shuō)xi,用(xi)標(biāo)記不通過(guò)在M中的邊與xi鄰接且未標(biāo)記過(guò)的Y的所有結(jié)點(diǎn)。對(duì)所有X的新標(biāo)記過(guò)的結(jié)點(diǎn)重復(fù)這一過(guò)程。 Ⅱ.選一個(gè)Y的新標(biāo)記過(guò)的結(jié)點(diǎn),比如說(shuō)yi,用(yi)標(biāo)記通過(guò)M的邊與yi鄰接且未標(biāo)記過(guò)的X的所有結(jié)點(diǎn)。對(duì)所有Y的新標(biāo)記過(guò)結(jié)點(diǎn)重復(fù)這一過(guò)程。,例如,在下圖中,可用如下標(biāo)記過(guò)程: (1) 把x’2標(biāo)記(*)。

56、 (2) 從x2出發(fā),應(yīng)用過(guò)程Ⅰ,把y1和y3標(biāo)記(x2)。 (3)從y1出發(fā),應(yīng)用過(guò)程Ⅱ,把x3標(biāo)記(y1)。從y3出發(fā),應(yīng)用過(guò)程Ⅱ,把x4標(biāo)記(y3)。 (4)從x3出發(fā),應(yīng)用過(guò)程Ⅰ,把y4標(biāo)記(x3),因y4不是M中邊的端點(diǎn),說(shuō)明已找到了一條交替鏈,即(x2,y1,x3,y4)。,在二部圖G中,如果能找出一條關(guān)于匹配M的交替鏈γ,則把γ中屬于M的邊從M中刪去,

57、而把γ中不屬于M的邊添到M中,得到一新集合M′,此M′也是G的匹配。這是因?yàn)樘砣氲倪呑陨聿幌嘟?又不與M中不屬于γ的邊相交。例如在圖8.4―2中作這樣變換后,所得的M′(用粗黑線標(biāo)出)如圖8.4―3所示。但M′比M多一條邊。因此,反復(fù)進(jìn)行這樣的過(guò)程,直至找不出關(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)用標(biāo)記法找出交替鏈(x1,y3,x3,y2,x2,y1),進(jìn)行變換得