《離散數(shù)學(xué)》課件第8章

8.1圖的基本概念8.2路徑和回路8.3圖的矩陣表示8.4圖的支配集、獨立集和覆蓋

8.5二部圖8.6平面圖和圖的著色8.7樹8.8有向樹8.9運輸網(wǎng)絡(luò)第8章圖論8.1.1圖現(xiàn)實世界中許多現(xiàn)象能用某種圖形表示,這種圖形是由一些點和一些連接兩點間的連線所組成。例如,可用圖形表示某一城市中各工廠間的業(yè)務(wù)往來關(guān)系。以點代表工廠,以連接兩點的連線表示這兩工廠間有業(yè)務(wù)往來關(guān)系。對于這種圖形,我們的興趣在于有多少個點和哪些點對間有線連接,至于連線的長短曲直和點的位置都無關(guān)緊要。對它們進(jìn)行數(shù)學(xué)抽象我們就得到以下作為數(shù)學(xué)概念的圖的定義。8.1圖的基本概念

定義8.1―1

一個圖G是一個三重組〈V(G),E(G),ΦG〉,其中V(G)是一個非空的結(jié)點(或叫頂點)集合,E(G)是邊的集合,ΦG是從邊集E到結(jié)點偶對集合上的函數(shù)。一個圖可以用一個圖形表示。

例8.1-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),Φ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(a)或(b)表示。圖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是鄰接的。若邊e所對應(yīng)的偶對(a,b)是無序的,則稱e是無向邊。無向邊簡稱棱,除無始點和終點的術(shù)語外,其它術(shù)語與有向邊相同。每一條邊都是有向邊的圖稱為有向圖,如圖8.1―2所示。第三章中的關(guān)系圖,第六章中表示群的圖都是有向圖的例子。

每一條邊都是無向邊的圖稱為無向圖,如圖8.1―1所示。如果在圖中一些邊是有向邊,而另一些邊是無向邊,則稱這個圖是混合圖。我們僅討論有向圖和無向圖,且V(G)和E(G)限于有限集合。圖8.1―2

為方便敘述,我們約定用〈a,b〉表示有向邊,(a,b)表示無向邊,既表示有向邊又表示無向邊時用［a,b］。于是,圖8.1―1中的G和圖8.1―2中的G′可分別簡記為

G=〈V,E〉=〈{a,b,c,d},{(a,b),(a,c),(b,d),(b,c),(d,c),(a,d),(b,b)}〉G′=〈V′,E′〉=〈{a,b,c,d,e,f},{〈a,b〉,〈b,a〉,〈b,c〉,〈c,c〉,〈a,d〉,〈e,e〉}〉

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

在有向圖中,兩結(jié)點間(包括結(jié)點自身間)若同始點和同終點的邊多于一條,則這幾條邊稱為平行邊。在無向圖中,兩結(jié)點間(包括結(jié)點自身間)若多于一條邊,則稱這幾條邊為平行邊。兩結(jié)點a、b間互相平行的邊的條數(shù)稱為邊［a,b］的重數(shù)。僅有一條時重數(shù)為1,無邊時重數(shù)為0。

定義8.1―2含有平行邊的圖稱為多重圖。

非多重圖稱為線圖。無自回路的線圖稱為簡單圖。在圖8.1―3中,(a)、(b)是多重圖,(c)是線圖,(d)是簡單圖,關(guān)系圖都是線圖。圖8.1―3

對于多重圖,定義8.1―1中的ΦG有時是不可缺少的,對于線圖,因為每結(jié)點偶對間無平行邊,就可用結(jié)點偶對表示邊,而毋需引用ΦG。通常,我們就和上邊G和G′那樣表示一個圖,非必要時不出現(xiàn)ΦG。

從實際問題抽象出來的圖中往往結(jié)點和邊上都帶有信息,因此需要以下定義。

定義8.1―3賦權(quán)圖G是一個三重組

〈V,E,g〉或四重組〈V,E,f,g〉,其中V是結(jié)點集合,E是邊的集合,f是定義在V上的函數(shù),g是定義在E上的函數(shù)。圖8.1―4給出一個賦權(quán)圖。

V={v1,v2,v3}E={e1,e2}={(v1,v2),(v2,v3)}

f(v1)=5,f(v2)=8,f(v3)=11

g(e1)=4.6,g(e2)=7.5

圖8.1―48.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)。孤立結(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,…,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―正則圖。圖8.1―5所示的稱為彼得森(Petersen)圖,是3―正則圖。8.1.3圖的同構(gòu)

定義8.1.6設(shè)G=〈V,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)的圖除了頂點和邊的名稱不同外實際上代表同樣的組合結(jié)構(gòu)。

例8.1-2(1)圖8.1―6所示的(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)中僅有的邊。圖8.1―6(2)圖8.1―7所示的兩圖是同構(gòu)的。因為作映射g(vi)=v’i(i=1,2,…,6),可使(vi,vj)一一對應(yīng)于(g(vi),g(vj))。圖8.1―7

兩圖同構(gòu)的必要條件:(1)結(jié)點數(shù)相等;(2)邊數(shù)相等;(3)度數(shù)相同的結(jié)點數(shù)相等。但這不是充分條件,例如圖8.1―8中(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―8

8.1.4圖的運算

圖的常見運算有并、交、差、環(huán)和等,現(xiàn)分別定義于下:

定義8.1―7設(shè)圖G1=〈V1,E1〉和圖

G2=〈V2,E2〉。

(1)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〉,

其中E3=E1-E2,V3=(V1-V2)∪{E3中邊所關(guān)聯(lián)的頂點},

記為G3=G1-G2。

(4)G1與G2的環(huán)和,定義為圖G3＝〈V3,E3〉,

G3=(G1∪G2)-(G1∩G2),記為G3=G1

G2。

除以上4種運算外,還有以下兩種操作:(1)刪去圖G的一條邊e;(2)刪去圖G的一個結(jié)點v。它的實際意義是刪去結(jié)點v和與v關(guān)聯(lián)的所有邊。為了幫助理解,在圖8.1―9中給出以上4種運算和兩種操作的圖示。

圖8.1―9

8.1.5子圖與補圖

定義8.1―8設(shè)G=〈V,E〉和G′=〈V′,E′〉是兩個圖。

(1)如果V′V和E′E,則稱G′是G的子圖。如果V′V和E′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′導(dǎo)出的子圖。圖8.1―10圖示了以上各術(shù)語。圖8.１―10

定義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個頂點的完全圖的邊刪去E所得,則圖H稱為圖G的補圖,記為,顯然,。

圖8.１―118.2.1路徑和回路定義8.2―1在有向圖中,從頂點v0到頂點vn的一

條路徑是圖的一個點邊交替序列（v0e1v1e2v2…envn）,其中vi-1和vi分別是邊ei的始點和終點,i=1,2,…,n。在序列中,如果同一條邊不出現(xiàn)兩次,則稱此路徑是簡單路徑,如果同一頂點不出現(xiàn)兩次,則稱此路徑是基本路徑(或叫鏈)。如果路徑的始點v0和終點vn相重合,即v0=vn,則此路徑稱為回路,沒有相同邊的回路稱為簡單回路,通過各頂點不超過一次的回路稱為基本回路。8.2路徑和回路

在圖8.2―1中:(a)P1=(v1e1v2e7v5)是一條基本路徑。(基本路徑也一定是簡單路徑。)(b)P2=(v2e2v3e3v3e4v1e1v2)是一簡單回路但非基本回路。

(c)P3=(v4e6v2e7v5e8v4e6v2e2v3)是一路徑。

(d)P4=(v2e7v5e8v4e6v2)是一基本回路。圖8.2―1

在無向圖上,以上各術(shù)語的定義完全類似,故不重復(fù)。路徑和回路可僅用邊的序列表示,在非多重圖時也可用頂點序列表示,例如上例的P3和P4可記為

(v4,v2,v5,v4,v2,v3)和(v2,v5,v4,v2)

并稱P3穿程于(v4,v2,v5,v4,v2,v3),P4穿程于(v2,v5,v4,v2)。

定義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)是所

經(jīng)的結(jié)點,如果其中有相同的結(jié)點vk,例

(v1,…,vi,…,vk,…,vk,…,v2),則刪去從vk到vk的這些邊,它仍是從v1到v2的路徑,如此反復(fù)地進(jìn)行直至(v1,…,vi,…,v2)中沒有重復(fù)結(jié)點為止。此時,所得的就是基本路徑。基本路徑的長度比所經(jīng)結(jié)點數(shù)少1,圖中共n個結(jié)點,故基本路徑長度不超過n-1。

定理8.2―2在一個具有n個結(jié)點的簡單圖G=〈V,E〉中,如果經(jīng)v1有一條簡單回路,則經(jīng)v1有一條長度不超過n的基本回路。證明是類似的,不再重復(fù)。

定義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;(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在無向圖G中,如果任兩結(jié)點可達(dá),則稱圖G是連通的;如果G的子圖G′是連通的,沒有包含G′的更大的子圖G″是連通的,則稱G′是G的連通分圖(簡稱分圖)。一個無向圖或者是一個連通圖,如圖8.2―2(a)所示,或者是由若干個連通分圖組成,如圖8.2―2(b)所示。圖8.2―2

定理8.2―3設(shè)G是任一(n,m)無向簡單圖,ω是

其分圖個數(shù),則

證先證n-ω≤m。對m作歸納。

m=0時,G是零圖,ω=n,命題成立。設(shè)m-1時成立,現(xiàn)證明m時也成立。我們從G上刪去一條邊得G′,G′有兩種可能:(i)有n個頂點,ω個分圖,m-1條邊,根據(jù)歸納假設(shè)n-ω≤m-1,顯然在G中成立n-ω≤m。(ii)有n個頂點,ω+1個分圖,m-1條邊,根據(jù)歸納假設(shè)n-(ω+1)≤m-1,顯然在G中成立n-ω≤m成立。故對一切m，n-ω≤m成立。再證m≤

(n-ω)(n-ω+1)。

ω=1時是連通圖，上式顯然成立?，F(xiàn)證ω≥2的情況。不妨設(shè)每個連通分圖都是完全圖，Gi和Gj是任兩個分圖，分別有ni和nj個結(jié)點，且ni≥nj。給Gi增加一個結(jié)點，Gj減少一個結(jié)點，總結(jié)點數(shù)不變，但要保持Gi和Gj是完全圖，邊數(shù)增加了

這說明要使G的邊數(shù)最大，G必須由n-ω+1個頂點的完全圖和ω-1個孤立點組成。因此

無向簡單圖即使是連通的，連通程度也還是有差別，因此需要以下定義。

定義8.2-6

一個無向簡單圖G=〈V，E〉，V′

V。如果

(1)ω(G-V′)>ω(G);

(2)不存在V′的真子集V″使得ω(G-V″)>ω(G)，則稱點集V′是圖G的點割。若只要求V′滿足條件(1)而不必滿足條件(2)，則稱V′是圖G的泛點割。若V′={v}，則稱v為割點。圖8.2-3(a)中三個黑點構(gòu)成點割，(b)中三個黑點構(gòu)成泛點割但非點割，因為刪去上下兩個黑點足以使圖不連通。(c)中黑點v是割點(頂點u也是割點)。從定義可看出，點割也是泛點割，反之不真。但泛點割中含有點割，只需把泛點割中對滿足條件(1)不起作用的頂點除去，便成為點割。圖8.2-3

定義8.2-7

G=〈V，E〉是無向簡單連通圖。G中含有頂點數(shù)最小的點割的大小稱為G的點連通度，記為κ0(G)。κ0(G)≥k時，稱G為k－點連通的。規(guī)定完全圖Kn的κ0(Kn)=n-1，平凡圖G的κ0(G)=0，不連通圖G的κ0(G)=0。簡而言之，κ0(G)就是要使連通圖G變成不連通圖或平凡圖必須刪去的頂點數(shù)。在圖8.2-4(a)中的圖是3-點連通的，也是2-點連通的、1-點連通的。(b)中圖是1點連通的，因為它有割點。圖8.2-4

定義8.2-8

一個無向簡單圖G=〈V，E〉，E′

E。如果

(1)ω(G-E′)>ω(G)

(2)不存在E′的真子集E″使得ω(G-E″)>ω(G),則稱邊集E′是圖G的割集。若只要求E′滿足條件(1)而不必滿足條件(2)，則稱E′為圖G的泛割集。若E′={e}，則稱e為橋。圖8.2-5(a)中，三條粗邊組成圖的割集;(b)中三條粗邊組成圖的泛割集，但非割集，因為刪去邊e足以使圖不連通;圖(c)中邊e1是橋(e2也是橋）。割集也是泛割集，反之不真。但泛割集中含有割集，理由類似于泛點割中含有點割。圖8.2-5

定義8.2-9

G=〈V，E〉是無向簡單連通圖，G中含有邊數(shù)最小的割集的大小稱為G的連通度，記為κ1(G)。規(guī)定平凡圖G的κ1(G)=0，不連通圖G的κ1(G)=0。κ1(G)≥k時稱圖G是k-連通的。圖8.2-6(a)的圖是3-連通的，也是2-連通和1-連通的。(b)的圖是1-連通的，因含有橋e。圖8.2-6

定理8.2-4

G是無向簡單連通圖，則κ0(G)≤κ1(G)≤δ(G)。

證先證κ1(G)≤δ(G)。刪去具有度數(shù)δ(G)的一個頂點v的所有關(guān)聯(lián)邊，所得的圖顯然是不連通的，所以κ1(G)≤δ(G)。再證κ0(G)≤κ1(G)。當(dāng)κ1(G)=0或1時，結(jié)論顯然成立?，F(xiàn)設(shè)κ1(G)≥2。圖中存在一割集C，|C|=κ1(G)。留下C中任一條邊(u，v)，對其余κ1(G)-1條邊，每選一條邊e，進(jìn)行以下操作:

(1)若e的一個端點是u或v，則將e的另一個端點w刪除，把w并入V′(初始時V′=?)。

(2)若e不關(guān)聯(lián)u和v，則任取e的一個端點w刪除，把w并入V′。操作完成后|V′|≤κ1(G)-1。若刪去V′中所有頂點后圖已不連通，顯然κ0(G)≤|V′|≤κ1(G)-1<κ1(G)。若刪去V′中所有頂點后圖仍連通，所得圖有一橋(u，v)，刪去橋的兩端點之一，肯定使圖不連通或成為平凡圖，這樣κ0(G)≤|V′|+1≤κ1(G)。證畢。

定理8.2-5

設(shè)E′是無向簡單連通圖G的割集，則ω(G-E′)=2。

證設(shè)E′={e1,e2,…,ek}，按割集的定義，刪去e1,e2,…,ek-1時，G-{e1，e2，…，ek-1}仍連通，它有一橋ek。因此刪去橋ek，G-E′成為兩個連通分圖，即ω(G-E′)=2。

定理8.2-6

無向簡單連通圖G有一割點v，當(dāng)且僅當(dāng)存在兩個頂點u、w，使u到w的任何路徑都經(jīng)過v。

證必要性。v是割點，刪去v，G分成若干個連通分圖，在某兩個分圖上各取一個頂點，不妨說一個是u，一個是w，刪去v前G是連通的，所以u到w的路徑都經(jīng)過v。充分性。存在u和w，使u到w的所有路徑都經(jīng)過v，刪去v，G便不連通，所以v是割點。

定理8.2-7

無向簡單連通圖G沒有割點當(dāng)且僅當(dāng)G的任意兩點u、v同在一條基本回路上。

證充分性。G的任意兩點u和v同在一條基本回路上，刪去u或v圖仍連通，所以圖G無割點。必要性。G沒有割點，G是2點連通的，根據(jù)定理8.2-4，G是2連通的?，F(xiàn)對u、v的距離d(u，v)作歸納以證明必要性。基礎(chǔ):d(u，v)=1時，刪去邊(u，v)，因G是2連通的，u到v仍存在一條基本路徑P。邊(u，v)加上P構(gòu)成一條經(jīng)過u、v的基本回路。歸納:設(shè)d(u，v)=k-1(k≥2)時成立。設(shè)d(u，v)=k時，u到v的最短路徑上與v鄰接的頂點是w，即d(u，w)=k-1。由歸納假設(shè)知存在一條基本回路C經(jīng)過u、w兩點(參看圖8.2-7，其中C1和C2構(gòu)成C)。刪去點w，由于G是2點連通的，所以u到v仍存在一條基本路徑P。不妨設(shè)P與C相交而與v最近的交點是x。這樣從u開始沿C1到x、從x沿P到v，經(jīng)過邊(v，w)，再沿C2到u，構(gòu)成一條含有u、v的基本回路。(P與C可能不相交，但這種情況組成基本回路更方便，就不寫出來了)。證畢。圖8.2-7

定理8.2-8

無向簡單連通圖G=〈V，E〉沒有割點，當(dāng)且僅當(dāng)圖中任一點u和任一邊(w，v)同在一條基本回路上。

定理8.2-9

無向簡單連通圖G=〈V，E〉沒有割點，當(dāng)且僅當(dāng)任何兩條邊(u，v)、(w，x)同在一條基本回路上。點連通度和連通度的概念在某些工程中有實用意義。例如在通信網(wǎng)中，把通信站看做結(jié)點，把通信線路看做邊，所得圖的點連通度就是通信站遭受破壞仍能保持其余網(wǎng)點通信可忍受的程度，連通度就是通信線路遭受破壞仍能保持所有網(wǎng)點通信可忍受的程度。

定義8.2-10

設(shè)G=〈V，E〉是有向圖，vi，vj∈V。如果從vi到vj存在一條有向路徑，則稱vj從vi可達(dá)。vi自身認(rèn)為從vi可達(dá)。

定義8.2―11在有向圖中,如果在任兩結(jié)點偶對中,至少從一個結(jié)點到另一個結(jié)點是可達(dá)的,則稱圖G是單向連通的;崐如果在任兩結(jié)點偶對中,兩結(jié)點都互相可達(dá),則稱圖G是強連通的;如果它的底圖是連通的,則稱圖G是弱連通的。顯然,強連通的也一定是單向連通和弱連通的,單向連通的一定是弱連通的,但其逆均不真。在圖8.2―3中,(a)是強連通的,(b)是單向連通的,(c)是弱連通的。圖8.2―8

定義8.2―12

在有向圖G=〈V,E〉中,G′是G的子

圖,若G′是強連通的(單向連通的,弱連通的),沒有包含G′的更大子圖G″是強連通的(單向連通的,弱連通的),則稱G′是G的強分圖(單向分圖,弱

分圖)。在圖8.2―4中,強分圖集合是:{〈{1,2,3},{e1,e2,e3}〉,〈{4},φ〉,〈{5},φ〉,〈｛6｝,φ〉,〈｛7,8｝,{e7,e8}〉｝

單向分圖集合是:{〈{1,2,3,4,5},{e1,e2,e3,e4,e5}〉,〈{6,5},{e6}〉,〈｛7,8｝,{e7,e8}〉｝弱分圖集合是:{〈{1,2,3,4,5,6},{e1,e2,e3,e4,e5,e6}〉,〈｛7,8｝,{e7,e8}〉｝圖8.2―9

容易證明,“在同一連通分圖中”,“在同一強分圖中”,“在同一弱分圖中”都是圖的頂點集V上的等價關(guān)系。這個等價關(guān)系把V劃分成若干個等價類,即分圖,V中每一頂點在且只在一個分圖中。在無向圖和弱連通中,一條邊所關(guān)聯(lián)的兩端點總是在同一分圖中,所以這個等價關(guān)系也把邊全部劃歸到分圖中。對強連通而言,一條邊所關(guān)聯(lián)的兩端點未必同在一分圖中,所以有些邊不屬于任一分圖,例如,圖8.2―9中的邊e4,e5,e6。

“在同一單向分圖中”不是頂點集V上的等價關(guān)系,因為若vi和vj、vj和vk在同一單向分圖中,但vi和vk不一定單向可達(dá),不一定在同一單向分圖中,傳遞性不成立,如圖8.2―10所示。所以,有些頂點可以同時在兩個分圖中,如圖8.2―10中的vj,既在{vi,vj}構(gòu)成的分圖中,又在{vj,vk}構(gòu)成的分圖中。但在單向連通中,一條邊所關(guān)聯(lián)的兩端點總在一個分圖中,所以每條邊在且只在一個分圖中。圖8.2―10

下邊舉一例說明連通性在計算機中的應(yīng)用。在多道程序的計算機系統(tǒng)中,在同一時間內(nèi)幾個程序要穿插執(zhí)行,各程序?qū)Y源(指CPU、內(nèi)存、外存、輸入輸出設(shè)備、編譯程序等)的請求可能出現(xiàn)沖突。例如程序P1控制著資源r1而又請求資源r2;程序P2控制著資源r2而又請求r1。在這種情況下,P1和P2將長期得不到執(zhí)行,這被稱為計算機系統(tǒng)處于“死鎖”狀態(tài)?？捎糜邢驁D來模擬對資源的請求,從而便于檢出和糾正“死鎖”狀態(tài)。圖8.2―11

設(shè)At={P1,P2,P3,P4}是t時刻運行的程序集合,Rt={r1,r2,r3,r4}是t時刻所需的資源集合。

P1據(jù)有資源r4且請求r1;P2據(jù)有資源r1且請求r2和r3;P3據(jù)有資源r2且請求資源r3;P4據(jù)有資源r3且請求資源r1和r4。于是可畫出如圖8.2―12所示的資源分配圖。圖8.2―128.2.3賦權(quán)圖中的最短路徑設(shè)G=〈V,E,W〉是個賦權(quán)圖,W是從E到正實數(shù)集合的函數(shù),邊［i,j］的權(quán)記為W(i,j),稱為邊的長度。若i和j之間沒有邊,那么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不可達(dá)時

本小節(jié)主要討論在一個賦權(quán)的簡單連通無向圖

G=〈V,E,W〉中,求一結(jié)點a(稱為源點)到其它結(jié)點x的最短路徑的長度,通常稱它為單源問題。下面介紹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=,則停止,否則再重復(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é)點是t1,于是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)分情況證明上式。

現(xiàn)分情況證明上式:情況1:如果從a到t有一條最短路徑，它不包含T′中的其它結(jié)點，也不含x點，則D′(t)=D(t)。情況2:如果從a到t有一條最短路徑，它從a到x，不包含T′中的結(jié)點，接著是邊W(x,t)，在此情況下，D′(t)是D(x)+W(x,t)。除以上兩種情況外不再有其它更短的不含T′另外結(jié)點的路徑了。因為如果有一條從a經(jīng)x到q∈S再到t的最短路徑，則從a到q有一條不包含x的更短的路徑，因為根據(jù)算法的第(3)條知，對S中任何結(jié)點q，從a到q有一條只含S中結(jié)點的最短路徑，所以結(jié)果仍化簡為情況1。這樣就證明了公式。

例8.2-1

考慮圖8.2―13中的圖,起初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。置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―13表8.2―1

8.2.4歐拉路徑和歐拉回路哥尼斯堡(Konigsberg,現(xiàn)加里寧格勒)位于普雷格爾(Pregel)河畔,河中有兩島。城市的各部分由7座橋接通,如圖8.2―14(a)所示。古時城中居民熱衷于一個問題:游人從任一地點出發(fā),怎樣才能做到穿過每座橋一次且僅一次后又返回原出發(fā)地。1736年歐拉用圖論方法解決了此問題,寫了第一篇圖論的論文,從而成為圖論的創(chuàng)始人。

不難看出,如果用結(jié)點代表陸地,用邊代表橋,哥尼斯堡七橋問題就等價在于圖8.2―14(b)中找到這樣一條路徑,它穿程每條邊一次且僅一次。

穿程于圖G的每條邊一次且僅一次的路徑,稱為歐拉路徑。穿程于圖G的每條邊一次且僅一次的回路,稱為歐拉回路,具有歐拉回路的圖稱為歐拉圖。顯然,具有歐拉路徑的圖除孤立結(jié)點外是連通的,而孤立結(jié)點不影響歐拉路徑的討論。因此,下邊討論歐拉路徑有關(guān)問題時均假定圖是連通的。圖8.2―14

定理8.2―10無向連通圖G具有一條歐拉路徑當(dāng)且

僅當(dāng)G具有零個或兩個奇數(shù)次數(shù)的頂點。

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

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

并且因為原來的圖是連通的,因此,這個子圖必與我們已畫過的路徑在一個點或多個點相接。由這些頂點中的一個開始,我們再通過邊構(gòu)造路徑,因為頂點次數(shù)全是偶數(shù),因此,這條路徑一定最終回到起點。我們將這條路徑已構(gòu)造好的路徑組合成一條路徑。如果必要,這一論證重復(fù)下去,直到我們得到一條通過圖中所有邊的路徑,即歐拉路徑。因此充分性得證。

例8.2-2(1)一筆畫問題。就是判斷一個圖形能否一筆畫成,實質(zhì)上就是判斷圖形是否存在歐拉路徑和歐拉回路的問題。例如,圖8.2―15(a)和(b)均可一筆畫成,因為符合存在歐拉路徑和歐拉回路條件。(2)我們想知道是否可能將28塊不同的多米諾骨牌排成一個圓形,使得在這個排列中,每兩塊相鄰的多米諾骨牌其相鄰的兩個半面是相同的。我們構(gòu)造一個具有7個頂點的圖,這些頂點對應(yīng)于空白、1、2、3、4、5和6,在每兩個頂點之間都有一條邊,我們把這條邊當(dāng)作一塊多米諾骨牌,并且把這條邊相關(guān)聯(lián)的兩個頂點當(dāng)作它的兩個半面。圖8.2―15

定理8.2―11

一個有向連通圖具有歐拉回路,當(dāng)且僅當(dāng)它的每個頂點的引入次數(shù)等于引出次數(shù)。一個有向連通圖具有歐拉路徑,當(dāng)且僅當(dāng)它的每個頂點的引入次數(shù)等于引出次數(shù),可能有兩個頂點是例外,其中一個頂點的引入次數(shù)比它的引出次數(shù)大1,另一個頂點的引入次數(shù)比它的引出次數(shù)小1。證明是類似的,不重復(fù)。

例8.2-3布魯英(DeBruijn)序列?，F(xiàn)以旋轉(zhuǎn)鼓設(shè)計為說明布魯英序列。旋轉(zhuǎn)鼓的表面分成8塊扇形,如圖8.2―16(a)所示。圖中陰影區(qū)表示用導(dǎo)電材料制成,空白區(qū)用絕緣材料制成,終端a、b和c是接地或不是接地分別用二進(jìn)制信號0或1表示。因此,鼓的位置可用二進(jìn)制信號表示。試問應(yīng)如何選取這8個扇形的材料使每轉(zhuǎn)過一個扇形都得到一個不同的二進(jìn)制信號,即每轉(zhuǎn)一周,能得到000到111的8個數(shù)。圖8.2―168.2.5哈密爾頓路徑與哈密爾頓回路在無向圖G=〈V,E〉中,穿程于G的每個結(jié)點一次且僅一次的路徑稱為哈密爾頓路徑。穿程于G的每個結(jié)點一次且僅一次的回路稱為哈密爾頓回路。具有哈密爾頓回路的圖稱為哈密爾頓圖。哈密爾頓,愛爾蘭數(shù)學(xué)家,1859年他首先提出這一類問題。它的問題如下:

如何沿12面體的棱線,通過每個角一次且僅一次?(稱為環(huán)游全世界游戲。)圖8.2―17

定理8.2―12

若G=〈V,E〉是哈密爾頓圖,則對V的每個非空真子集S均成立:ω(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的生成子圖,所以

ω(G-S)≤ω(C-S)≤|S|

應(yīng)用本定理可以判定某些圖不是哈密爾頓圖,例如,圖8.2―18所示的圖,刪去其中3個黑點,即知此圖不符合必要條件,因而不是哈密爾頓圖。但一般要考察多個真子集,應(yīng)用不方便,例4給出了一種較簡便的否定一個圖是哈密爾頓圖的方法,但也不是通用的。圖8.2―18

例8.2-4證明圖8.2―19(a)中的圖沒有哈密爾頓路徑。證用A標(biāo)記頂點a,所有與A鄰接的頂點標(biāo)記為B。繼續(xù)不斷地用A標(biāo)記所有鄰接于B的頂點,用B標(biāo)記所有鄰接于A的頂點,直到所有頂點標(biāo)記完,得到如圖8.2―19(b)所示的圖,圖中有3個頂點標(biāo)A和5個頂點標(biāo)B,標(biāo)號A和B崐相差2個,因此不可能存在一條哈密爾頓路徑。圖8.2―19

定理8.2―12中的條件不是充分的,圖8.1―5中給出的彼得森圖,它對任意SV都滿足ω(G-S)≤|S|,但不是哈密爾頓圖。

定理8.2―13

設(shè)G=〈V,E〉是具有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與vi,vi-1與vn相鄰,如圖8.2―20所示。若不然,設(shè)在G′中v1與

相鄰,而vn與

都不相鄰,則deg(vn)≤n-k-1,這樣deg(v1)+deg(vn)≤n-1＜n,與題設(shè)不符。

圖8.2―20v1與vi相鄰,vn與vi-1相鄰,于是G′存在一條哈密爾頓回路(v1,v2,…,vi-1,vn,vn-1,…,vi+1,vi,v1),但這與G

′是最大的非哈密爾頓圖矛盾。證畢。容易看出定理8.2―13的條件是充分的但非必要。例如,設(shè)G是一個n邊形,n＞5,任何兩個頂點的度數(shù)之和是4,但在G中有一條哈密爾頓回路。

推論8.2―13在簡單無向圖中,若每一頂點的度

數(shù),則該圖是哈密爾頓圖。在有向圖中,也可類似地定義出哈密爾頓有向回路和哈密爾頓有向路徑,但結(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,vj,vk滿足

W(i,j)+W(j,k)≥W(i,k)

試求出賦權(quán)圖上的最短哈密爾頓回路。

至今未找出有效的方法,但已找到了若干近似算法,現(xiàn)介紹其一——最鄰近算法,它為巡回售貨員問題得出一個近似解。

(1)選任意點作為始點,找出一個與始點最近的點,形成一條邊的初始路徑。然后用第(2)步方法逐點擴(kuò)充這條路徑。

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

其實圖8.2―21(a)的最小哈密爾頓回路應(yīng)如(f)所示,總距離是43。8.３圖的矩陣表示

矩陣是研究圖的性質(zhì)的最有效工具之一?？蛇\用矩陣運算求出圖的路徑、回路和其它性質(zhì)。定義8.3―1設(shè)G=〈V,E〉是有向線圖,其中

V={v1,v2,…,vn},并假定各結(jié)點已經(jīng)有了從v1到vn的次序。定義一個n×n的矩陣A,其中各元素aij為如果〈vi,vj〉∈E

如果〈vi,vj〉E

稱這樣的矩陣是圖的鄰接矩陣。

從定義可看出,有向線圖G=〈V,E〉的鄰接矩陣不唯一而與V中的元素標(biāo)定次序有關(guān),對于V中各元素不同的標(biāo)定次序可得到同一圖G的不同鄰接矩陣。但這些鄰接矩陣,適當(dāng)?shù)亟粨Q行和列的次序,能從一個鄰接矩陣變到另一個鄰接矩陣,且根據(jù)不同鄰接矩陣所作出的有向圖都是同構(gòu)的。因此,我們可選V元素的任一種標(biāo)定所得的鄰接矩陣作為圖G的鄰接矩陣。

當(dāng)有向線圖代表關(guān)系時,鄰接矩陣就是前邊講過的關(guān)系矩陣。根據(jù)關(guān)系圖和關(guān)系矩陣的對應(yīng)關(guān)系,易知:有向圖是自反的,矩陣的對角線元素全為1;有向圖是反自反的,矩陣的對角線元素全為0;有向圖是對稱的,對所有i和j,矩陣的元素aij=aji。有向圖是反對稱的,對所有i和j,aij=1蘊含aji=0,但aij=0,不一定aji=1。零圖的鄰接矩陣的元素全為零,稱為零矩陣。每一頂點都有自回路而無其它邊的圖的鄰接矩陣是單位矩陣。設(shè)有向線圖G=〈V,E〉的鄰接矩陣是A,則G的逆圖

的鄰接矩陣是A的轉(zhuǎn)置矩陣,記AT。

鄰接矩陣的概念可以推廣到無向線圖,只需將以上定義中的〈vi,vj〉換成(vi,vj)即可,無向圖的鄰接矩陣是對稱的,對有向線圖推出的結(jié)論,都可并行地用到無向線圖上。另外,鄰接矩陣的概念還可推廣到多重圖和賦權(quán)圖,對多重圖,aij代表從vi到vj的邊的重數(shù);對賦權(quán)圖,aij代表權(quán)W(i,j),從vi到vj不存在邊時,規(guī)定aij=0。

例8.3―1所示有向線圖的鄰接矩陣。圖8.3―1

現(xiàn)在我們計算上例中的AAT、ATA、A(2)、A(3)、

A(4)1等，并研究它們的元素的意義。1.AAT的元素的意義設(shè)B=［bij］=AA

T,則 。當(dāng)且僅當(dāng)aik和ajk都是1時,aik·ajk=1。aik=1和ajk=1意味著存在邊〈vi,vk〉和〈vj,vk〉。于是得出以下結(jié)論:從結(jié)點vi和vj兩者引出的邊,如果能共同終止于一些結(jié)點,則這些終止結(jié)點的數(shù)目就是bij的值;特別,i=j時,對角線上的元素bii就是結(jié)點vi的引出次數(shù)。例如,在圖8.3―1中,①選i=2,j=3,于是b23=1,說明從v2和v3引出的邊能共同終止于同一結(jié)點的只有一個,即v4;②選i=2,j=2,于是b22=2,說明v2的引出次數(shù)為2。2.ATA的元素的意義設(shè)B=［bij］=ATA,則

。當(dāng)且僅當(dāng)aki和akj都是1時,aki·akj=1。aki=1和akj=1意味著存在邊〈vk,vi〉和〈vk,vj〉。于是得出以下結(jié)論:從一些結(jié)點引出的邊,如果同時終止于vi和vj,則這樣的結(jié)點數(shù)目就是bij的值。特別,對角線上元素的值是各結(jié)點的引入次數(shù)。3.A(n)的元素的意義

n=1時,aij=1,說明存在一條邊〈vi,vj〉,或者說,從vi到vj存在一條長度為1的路徑。n=2時,用a(2)ij表示A(2)各元素,于是

當(dāng)且僅當(dāng)aik和akj都等于1時,aik·akj=1。aik

和akj等于1,表明存在邊〈vi,vk〉和〈vk,vj〉,于是存在

一條從vi到vj長度為2的路徑。所以,a(2)ij等于從vi到vj長度為2的不同路徑的條數(shù)。

容易推想到,A(n)的元素a(n)ij是從vi到vj的長度為n的不同路徑的數(shù)目。這可用歸納法證明。設(shè)n=m時,上述斷言成立,現(xiàn)證n=m+1時,此斷言亦成立。因為A(m+1)=A(m)·A,所以

例如,在圖8.3―1中,a(4)34=3,所以從v3到v4長度為4

的路徑是3條。a13=0而a(2)13=1,所以從v1到v3的距

離是2?，F(xiàn)在考察矩陣:

Br=A+A(2)+A(3)+…+A(r)

的元素bij的意義。容易看出，bij是表示從結(jié)點vi到vj長度小于和等于r的不同路徑總數(shù)。因此，若要研究是否存在一條從vi到vj的任意長的路徑，須求出 。但這樣做實際上不是必要的，根據(jù)定理8.2-1和8.2-2，在n個結(jié)點的簡單有向圖中，基本路徑長度不超過n-1，基本回路長度不超過n，因此僅需考察Bn-1=A+A(2)+A(3)+…+A(n-1)

(i≠j時)或Bn=A+A(2)+A(3)+…+An

(i≠j時)

例8.3-2

根據(jù)圖8.3―2中的有向圖和矩陣B5,驗證

以下斷言:(a)b52=0,所以v2和v5分屬兩個強分圖。

(b)b11=0,所以沒有經(jīng)過v1的回路。

(c)b53=3,所以從v5到v3長度不超過5的路徑有3條。圖8.3―2

定義8.3―2設(shè)G=〈V,E〉是有向線圖,其中｜V｜=n,并假定各結(jié)點是有序的,定義一個n×n的矩陣P,它的元素當(dāng)vi到vj至少存在一條非零長度的路徑0

當(dāng)vi到vj不存在一條非零長度的路徑稱矩陣P為圖G的可達(dá)性矩陣?？蛇_(dá)性矩陣不能給出圖的完整的信息,但是簡便,在應(yīng)用上還是重要的。如果已知Bn或Bn-1,則只需將其中非零元素寫成1,即得可達(dá)性矩陣。例如,例8.3-2所給的圖的可達(dá)性矩陣是

但一般計算Bn或Bn-1工作量較大,可把鄰接矩陣作為布爾矩陣,用布爾矩陣運算直接求得。我們在3.2節(jié)中已介紹過布爾矩陣運算方法,這里不重述。

例8.3-3求例8.3-2的圖的可達(dá)性矩陣。所以,

這里An的元素anij的意義與A(n)的元素a(n)ij類似,anij=1,是表示從vi到vj存在長度為n的路徑,anij=0時,表示不存在從vi到vj長度為n的路徑?？蛇_(dá)性矩陣P并沒有表達(dá)出每一元素自身可達(dá)的概念,若實際情況需要,可“或上”A°(單位矩陣)以表達(dá)每一結(jié)點自身可達(dá),即

P′=A°∨P=A°∨A∨A2V…∨An

例如例3的P′是

下邊介紹如何利用一個圖的可達(dá)性矩陣,求出這個圖的所有強分圖。設(shè)P是圖G的可達(dá)性矩陣,其元素為pij,PT是P的轉(zhuǎn)置矩陣,其元素是pTij,則圖G的強分圖可從矩陣P∧PT求得。因為從vi到vj可達(dá)則pij=1,從vj到vi可達(dá),則pji=1,即pTij=1,于是當(dāng)且僅當(dāng)vi和vj相互可達(dá)時,P∧P

T的第(i,j)個元素的值為1。

例8.3-4求例2給出的圖的強分圖。說明各強分圖的頂點集為:{v1},{v2},{v3,v4,v5}。若取P為同樣說明各強分圖的頂點集為:{v1},{v2},{v3,v4,v5}。除了鄰接矩陣外，圖還可用關(guān)聯(lián)矩陣表示。關(guān)聯(lián)矩陣的定義如下。

定義8.3-3

設(shè)G=〈V，E〉是無向圖，V={v1，v2，…，vn}，E={e1，e2，…，em}，一個n×m矩陣M=(mij)稱為G的關(guān)聯(lián)矩陣，其中mij是結(jié)點vi和邊ej的關(guān)聯(lián)次數(shù)。

定義8.3-4

設(shè)G=〈V，E〉是有向簡單圖，V={v1，v2，…，vn}，E={e1，e2，…，