圖論及應(yīng)用剖析

圖論簡介圖論是數(shù)學(xué)的一個分支,以圖為研究對象.這種圖由若干給定的點和連接兩點的線構(gòu)成,借以描述某些事物之間的關(guān)系.用點代表事物,用連接兩點的線表示兩個事物之間具有特定關(guān)系.圖論起源于18世紀,追朔到1736年瑞士數(shù)學(xué)家L.Euler出版第一本圖論著作,提出和解決著名Konigsberg七橋問題.從那時以來,圖論不僅在許多領(lǐng)域,如計算機科學(xué),運籌學(xué),心理學(xué)等方面得到了廣泛的應(yīng)用,而且學(xué)科本身也獲得長足發(fā)展,形成了擬陣理論,超圖理論,代數(shù)圖論,拓撲圖論等新分支.(8.5,8.8二節(jié)不講)圖的定義與記號圖G是一個二重組:G=V,E,其中V是非空有限集合,它的元素稱為結(jié)點,E

也是(可空)有限集合,它的元素稱為邊.圖G的邊e是一個結(jié)點二重組:a,b,a,bV,e可以是有序的,稱為有向邊,簡稱為弧,a稱為弧e的始點,b稱為e的終點;e也可以是無序的,稱為無向邊.e=a,b時,稱e與a,b關(guān)聯(lián),或a,b與e關(guān)聯(lián),或a與b相鄰接;關(guān)聯(lián)于同一結(jié)點的一條邊稱為自回路.每條邊都是無向邊的圖稱為無向圖;每條邊都是有向邊的圖稱為有向圖;我們僅討論無向圖和有向圖.(看圖8.1-1和圖8.1-2)圖的定義與記號續(xù)不與任何結(jié)點鄰接的結(jié)點稱為孤立結(jié)點,全為孤立結(jié)點組成的圖(視為無向圖有向圖均可)稱為零圖.在無向圖中兩結(jié)點間(包括結(jié)點自身)若多于一條邊，則稱這幾條邊為平行邊.在有向圖中若同始點和同終點的邊多于一條,則稱這幾條邊為平行邊,平行邊的條數(shù)稱為該邊的重數(shù).含平行邊的圖稱為多重圖,非多重圖稱為線圖.無自回路的線圖稱為簡單圖.例子見圖8.1-3.有向圖去掉方向所得無向圖稱為該圖的底圖.常用一個圖形來表示圖稱為圖的圖示deg+(1)=2,deg-(1)=0,deg(1)=deg(2)=…deg+(2)=deg-(2)=1,…=deg(6)=3.deg(1)=…=deg(4)=2.1234abcd123456abcdef結(jié)點的度(次數(shù))有向圖中,以結(jié)點v為始點的邊數(shù)稱為v的出度,記為deg+(v);以結(jié)點v為終點的邊數(shù)稱為v的入度,記為deg-(v);它們的和:

deg(v)=deg+(v)+deg-(v)稱為v的度.無向圖中,與結(jié)點v相關(guān)聯(lián)的邊數(shù)稱為v的度,記為deg(v).各結(jié)點的度都相等的圖稱為正則圖,或k-正則圖,其中k為結(jié)點度的公共值.(注:可以只考慮正則的無向圖,然后再定義其底圖的無向圖是正則圖的有向圖為正則有向圖.)例子見上一張幻燈片和圖8.1-5.關(guān)于有

n

結(jié)點

m

邊的(n,m)圖度的定理定理8.1-1

令

v1,…,vn為圖的所有結(jié)點,則

i=1n

deg(vi)=2m.(1)證:對于公式(1)左邊的和式,圖的每條邊貢獻的度數(shù)恰為2,從而結(jié)論成立.注:對有向圖(1)可寫成

i=1n

deg+(v)+

i=1n

deg-(v)=2m.定理8.1-2

任何圖中度為奇數(shù)的結(jié)點必為偶數(shù)個.證:因偶度點度的和為偶數(shù),若奇度點為奇數(shù)個,則奇度點度的和必為奇數(shù).但偶數(shù)加奇數(shù)得奇數(shù),便與(1)式右邊為偶數(shù)相矛盾.8.1#4(c)簡單無向圖

G

必有2結(jié)點同度證:令G={v1,…,vn}.若

G

中沒有孤立點,則

G

中

n個結(jié)點的度只取

n-1

個可能值:

1,2,…,n-1,從而

G

中至少有兩個結(jié)點的度相同.否則,G中有孤立點,不妨設(shè)vk,vk+1,…,vn為全部孤立點,則

v1,…,vk-1的度只取

k-2個可能值:

1,2,…,k-2,從而此

k-1個結(jié)點中至少有兩個同度點.圖的同構(gòu)定義:對給定兩個圖G=V,E,G=V,E,若存在雙射f:VV

使對任意a,bV,(a,b)E

(f(a),f(b))E,并且(a,b)與(f(a),f(b))有相同重數(shù),則稱

G

與

G同構(gòu),記為

GG.注:①

兩圖同構(gòu)是相互的:GG

GG.②

兩圖同構(gòu)時不僅結(jié)點之間要有一一對應(yīng)關(guān)系,而且要求這種對應(yīng)關(guān)系保持結(jié)點間的鄰接關(guān)系.對有向圖同構(gòu)還要求保持邊的方向.③

尋求判斷圖同構(gòu)的簡單有效方法仍是圖論待解決的重要問題.同構(gòu)圖舉例

G

G’

H

H’1

a,2

b,3

c,1

a,2

b,3

c,4

d4

d,5

e,6

f1234abcd123456abcdefGG’HH’非同構(gòu)圖舉例存在結(jié)點數(shù)及每個結(jié)點對應(yīng)度都相等的兩個圖仍然不同構(gòu)的情況.一個例子是圖8.1-8;另一例如下:(注意:兩個4度點或鄰接或不相鄰接)GG’子圖的概念定義:給定兩個無(有)向圖G=V,E,G=V,E.若VV

和

EE,則稱

G是G的子圖;若VV,EE,且

GG,則稱

G是

G

的真子圖;若V=V

和

EE,則稱

G是

G

的生成子圖;若子圖

G無孤立結(jié)點且G由E唯一確定,則稱G是由邊集E導(dǎo)出的子圖;若對子圖

G=V,E中任二結(jié)點

u,v,(u,v)E

(u,v)E,則稱

G是由結(jié)點集V導(dǎo)出的子圖(易見:V導(dǎo)出的子圖G是以V為其結(jié)點集,所有在G中同時關(guān)聯(lián)于V中兩點的邊為其邊集).有向圖子圖舉例(圖8.1-10)①:由{(1,2),(1,4),(5,1)}導(dǎo)出的子圖;②:由{(1,2),(3,2),(3,4),(1,4)}導(dǎo)出的子圖(也是此4點導(dǎo)出的子圖);③:由{1,2,4,5}導(dǎo)出的子圖.①②③11112222555334444完全圖與補圖E=VV的有向圖G=V,E稱為有向完全圖.n個結(jié)點的無向簡單圖如果任二不同結(jié)點都相鄰時,稱為n結(jié)點無向完全圖,記為

Kn.完全圖的例子見圖8.1-11.n

結(jié)點線圖G=V,E與H=V,E’稱互為補圖(記為G=H’或H=G’),如果E’是n結(jié)點完全圖的邊集與E的差集.下列二無向圖G與H互為補圖.GHK48.1#13的用紅,蘭色給

K6邊著色命題:對任意一種著色方案的著色結(jié)果,或者有一個紅K3,或者有一個蘭K3.證:令a,b,c,d,e,f為K6的6結(jié)點.因過f的5條邊必有三邊著為同色,不失一般性,設(shè)(a,f),(b,f),(c,f)已著紅色.若(a,b),(a,c),(b,c)已著蘭色,則{a,b,c}導(dǎo)出的子圖是一個蘭K3,從而結(jié)論成立.否則此三邊必有一邊,例如(a,b)已著紅色,則{a,b,f}導(dǎo)出的的子圖是紅K3.證畢.推論:任何6人的人群中,或者有3人互相認識,或者有3人彼此陌生.(當(dāng)二人x,y互相認識,邊(x,y)著紅色,否則著蘭色.則6人認識情況對應(yīng)于K6邊的一個二著色.由上述命題知或者有紅K3或者有蘭K3.)fabcabc6改5結(jié)論不成立路徑與回路圖

G=V,E

的點邊交替序列

P=v0e1v1e2v2

envn稱為

G

的一條從v0

到vn的長為

n

的路徑,其中,ei=(vi-1,vi)E,i=1,…,n(對有向圖要求vi-1,vi為ei的始,終點).P

稱為簡單路徑,如果e1,,en

兩兩不同;P

稱為基本路徑(鏈),如果v0,v1,,vn

兩兩不同(易見鏈必為簡單路徑);P

稱為回路,如果v0=

vn;回路

P

稱為簡單(基本)回路,如果e1,,en(v1,,vn)兩兩不同.路徑

P

可只用邊序列

e1e2en表示.若

G

為線圖,則路徑

P

也可只用結(jié)點序列

v0v1

vn

表示.例見圖8.2-1.

任何圖

G

中有從

u

到

w

的路徑(回路)必有從

u

到

w

的基本路徑(回路)由于G有從u到w的路徑,G必有一條長度最小的從u到w的路徑:P.如果P不是基本路徑,則

P=ue1v1e2

viei+1

vjej+1

enw

中

vi=vj,于是

P-{ei+1,,ej}仍是G的一條從u到w的路徑,但長度比P長度還要小,得出矛盾.vivj+1vj-1vi+1vn-1uwv1P在

n

結(jié)點的圖中任何鏈的長度都不大于n-1;任何基本回路的長度都不大于

n證:設(shè)任一鏈

P

的長度為k,則

P穿程于

k+1個結(jié)點:P

=

v0e1v1e2v2

ekvkvk.

因

v0,v1,,vk

兩兩不同,故

k+1n,從而

kn-1.同理,長度為k的基本回路有

k

個不同結(jié)點，從而

kn.距離的概念圖

G=V,E中,從結(jié)點

u

到

w

的最短路徑(必為鏈)的長度稱為

G

的從

u

到

w

的距離,記為

d(u,w).

如果從

u

到

w沒有路徑,則令

d(u,w)=+.(注意:在無向圖中恒有

d(u,w)=d(w,u),而在有向圖中可能出現(xiàn)d(u,w)d(w,u).)對任意

u,v,wV,d(u,v)是非負整數(shù)或+;d(u,v)0;d(u,v)=0

當(dāng)且僅當(dāng)

u=w;d(u,v)+d(v,w)d(u,w)(三角不等式,距離特性)三角不等式的證明:若

d(u,v)=+

或

d(v,w)=+,結(jié)論顯然成立.否則,有從

u

到

v

長度為

d(u,v)的路徑和從v到w長度為d(v,w)的路徑,從而有從u到w長度為d(u,v)+d(v,w)的路徑.無向圖的連通性在無向圖G中,若有從結(jié)點u到w的路徑(或從u到w的鏈,因有u-w路必有u-w鏈),則稱從u到w可達.約定每個結(jié)點到自身可達.(圖8.2-2(b))無向圖稱為是連通的,如果任二結(jié)點都可達.易見:G

連通當(dāng)且僅當(dāng)

G

有一個生成子圖連通.無向圖結(jié)點間的可達關(guān)系是等價關(guān)系(滿足自反,對稱和傳遞律),因此其商集給出

G

的結(jié)點集的一個劃分,屬于一個等價類的結(jié)點導(dǎo)出

G

的一個連通子圖,且不存在以此子圖為真子圖的連通子圖.故把這些連通子圖稱為G的連通分支.G的任何二結(jié)點相互可達當(dāng)且僅當(dāng)它們屬于同一個連通分支.G為連通當(dāng)且僅當(dāng)它恰有一個連通分支.G的連通分支數(shù)記為

(G).有向圖的連通性已知有向圖

G,若它的底圖是連通無向圖,則

G

稱為是弱連通的;若

G

的任二結(jié)點都相互可達,則G稱為是強連通的;若

G

的任二結(jié)點至少從一個到另一個可達,則

G

稱為是單向連通的.易見:強連通性

單向連通性

弱連通性;但反之不真.反例如下:

強連通單向連通非強連通弱連通非單向連通從a到b不可達從a到b不可達且從b到a不可達aabbcd有向圖的強(單向,弱)連通分支已知有向圖

G

及其子圖

G.若

G是強(單向,弱)連通的,并且

G

中沒有以

G為真子圖的強(單向,弱)連通子圖,則稱

G為

G

的強(單向,弱)連通分支.注①一個有向圖的上述三種連通分支可能是互不相同的,圖8.2-4中的圖就是這樣.②在有向圖中可用‘屬于同一強(弱)連通分支’引入結(jié)點間的等價關(guān)系.但對單向連通分支引入的關(guān)系不滿足傳遞性,從而不是等價關(guān)系(圖8.2-5).8.2#4無向圖

G恰有的2個奇度結(jié)點可達解1:令u,w為G恰有的2個奇度結(jié)點.考察u所在的連通分支G’.因任何圖的奇度點為偶數(shù),故G’至少還有另一奇度點.但G’的每個點在G和G’中有相同的度,所以G’恰有2個奇度點而且就是u和w.再由G’的連通性推出u到w可達.解2:可一般地證明在無向圖G中從任一奇度點u出發(fā)的一條最長簡單路的另一端點必為一個奇度點,原因是從u出發(fā)的最長簡單路不會終止在u處(否則d(u)為偶數(shù));也不會終止在任一偶度點v處(否則d(v)為奇數(shù)).賦權(quán)圖中的距離應(yīng)用廣泛的賦權(quán)圖是三重組:G=V,E,W,V,E

分別為

G

的結(jié)點集和邊集,W是從

E

到

R+的函數(shù),邊e=(i,j)的函數(shù)值

W(e)=W(i,j)稱為

e

的權(quán).

賦權(quán)圖

G的一條路徑

P=(e1,…,ek)的長度定義為:W(P)=W(e1)+…+W(ek).從結(jié)點u到w的距離定義為d(u,w)=min{W(P)|P為G中從u到w的路徑},約定:d(u,u)=0;d(u,w)=

,當(dāng)從u到w不可達.例如,對右邊的圖有d(a,c)=5;

d(a,d)=9;d(a,e)=7.21073245abcde求已知簡單連通賦權(quán)圖G中從源點a到其它各點x的最短距離的Dijkstra算法步驟①

把結(jié)點集V分割為二子集

S,T.開始時S={a},T=V-S.步驟②

對每結(jié)點

tT,求出

D(t)之后再定出xT

使得

D(x)=

min{D(x)|tT}.步驟③

置

S

為

S∪{x}置

T為T-{x}.若

T=則停止,否則轉(zhuǎn)步驟②作下一次循環(huán).將證:第②步求得的每一點x對應(yīng)有

D(x)=d(a,x).

開始時令

D(t)=W(a,t),結(jié)論顯然成立:D(x)=min{W(a,t)|tT}=d(a,x).

下一步對S=S∪{x},T=T-{x}令D(t)為T中結(jié)點的D(t)值,則D(t)=

min{D(t),D(x)+W(x,t)}.Dijkstra算法的標(biāo)號法舉例21073645210736452210736452107364510

2

95225599990000用Dijkstra算法的標(biāo)號法解8.2#11(b)11010141

05326101555462233881063

Euler路徑與Euler圖Konigsberg七橋問題(1736年).穿程于(有向或無向)圖

G

的每條邊一次且僅一次的路徑(回路)稱為

Euler

路徑(回路).

具有

Euler

回路的連通圖稱為Euler圖.Euler定理

無向連通圖G有一條Euler路徑當(dāng)且僅當(dāng)

G

有零個或兩個奇數(shù)度結(jié)點(證明見教本255頁);有向連通圖G有一條Euler路徑當(dāng)且僅當(dāng)

G的每點出,入度相等,只有兩點例外,并且它們出,入度之差一為1,一為-1.推論無向連通圖

G

是Euler圖當(dāng)且僅當(dāng)

G

的結(jié)點度數(shù)都是偶數(shù).應(yīng)用:Konigsberg七橋問題不可解,因?qū)?yīng)圖(見圖8.2-8(b))都是

3

度結(jié)點.用定理8.2-4的證明方法構(gòu)造Euler回路1155522233444111234113515245=123411352451=12341352451無向圖

G

能否一筆畫的問題等價于

G

是否有一條Euler路徑(回路)的問題若圖只有兩個奇結(jié)點,則任何Euler路徑必從其中一點開始到另一點結(jié)束.利用這條規(guī)律,先在此2奇點之間加條邊使之變成Euler圖并畫出一條Euler回路,然后再去掉所加的邊即得一條Euler路徑.ab123456789Hamilton路徑與Hamilton圖無向連通圖G穿程于G

的每一結(jié)點一次且僅一次的路徑(回路)稱為G

的一條Hamilton

路徑(回路);具有Hamilton回路的無向連通圖稱為Hamilton圖.由定義知Hamilton

路徑(回路)必為基本路徑(回路).1859年Ireland數(shù)學(xué)家Hamilton提出環(huán)游世界游戲給出Hamilton圖的一個經(jīng)典例子(圖8.2-11).可以證明:對任意正整數(shù)

n3

完全圖

Kn

恒有Hamilton回路(不難從任一點開始作出一條Hamilton回路,每一步都通到一個新結(jié)點,最后回到起點).(推廣到賦權(quán)圖的情形,求有最小權(quán)的Hamilton回路問題就是有名的貨郎問題)Hamilton圖的一個必要條件定理若G=V,E為Hamilton圖,則對每個

SV有

(G-S)|S|,其中(G-S)表示子圖G-S的連通分支數(shù).證:設(shè)C是G的一條Hamilton回路(必為基本回路),則對V的任意真子集S都有

(C-S)|S|,(1)(S={a1}時,(1)式成立等式;

S={a1,a2}時,C1=C-{a1}是鏈;

而

C-S=C1-{a2}是鏈,當(dāng)且僅當(dāng)a2為C1端點,否則

(C-S)=2.總之,(C-S)2=|S|.S={a1,…,ak,ak+1}時,由歸納法得

(C-S)

(C-{a1,…,ak})+1

|{a1,…,ak}|+1=k+1=|{a1,…,ak+1}|.)因生成子圖的連通分支數(shù)不比母圖的多和C-S是G-S的生成子圖,故得證

(G-S)(C-S)|S|.a1a2Ca1Ca28.2#15求簡單無向圖G:(b)G有E-回路但無H-回路;(d)G無E-回路也無H-回路左圖G無奇度點故有Euler回路;易見G無Hamilton回路(取S={a,b}時,有

(G-S)=3>2=|S|).右圖H有奇度點故無Euler回路;易見H無Hamilton回路(證明同上或用窮舉法驗證).GHabab非Hamilton圖舉例例①

圖8.2-12不是Hamilton圖,原因是:取S為3個黑點時有

(G-S)=4

>3=|S|.例②

圖8.1-5的Peterson圖不是Hamilton圖,但它滿足對一切非空子集SV有

(G-S)|S|,所以,定理8.2-6的條件不是充分的.例③

圖8.2-13不是Hamilton圖(用一種符號標(biāo)記法證明).結(jié)點符號標(biāo)記法補充圖標(biāo)記結(jié)束后,可能出現(xiàn)相鄰結(jié)點標(biāo)記符號相同的情況,此時應(yīng)先在該對結(jié)點之間增加一個新結(jié)點(此點必為2度點),同時將它標(biāo)以不同的符號.設(shè)所有有相同標(biāo)記的鄰點都做上述處理之后得到的圖記為G.則

G

有Hamilton路當(dāng)且僅當(dāng)G有Hamilton路.故若

G的不同標(biāo)記結(jié)點數(shù)不同時(如下圖)即可斷定

G

不是Hamilton圖.AAABBBAAABBBBGG

n(3)結(jié)點無向簡單圖G為Hamilton圖的一個充分條件:n/2,記最小度數(shù)證:用反證法.若結(jié)論不成立,則必有n結(jié)點的最大(邊數(shù)最多)非Hamilton圖G=V,E.因GKn,故G有結(jié)點u,v,(u,v)E,且G+(u,v)為Hamilton圖,同時G+(u,v)中任一Hamilton回路都含邊(u,v).于是G有從u到v的Hamilton路徑(u=v1,v2,…,vn=v)(見下圖).令S={vi|(u,vi+1)E},T={vi|(vi,v)E},則vnS∪T,|S∪T|<n.又

S∩T=(否則設(shè)某viS∩T,則如下圖所示G有Hamilton回路矛盾).因此

d(u)+d(v)=|S|+|T|=|S∪T|+|S∩T|<n,與假設(shè)矛盾.u=v1v2vi-1vi+1vivn=v注與例注由上面的證明可得更一般結(jié)論:n結(jié)點無向簡單圖G為Hamilton

圖,如果G的任2結(jié)點度數(shù)之和都不小于

n/2.例

n結(jié)點無向k-正則圖必為Hamilton圖只要kn/2.(因=kn/2)Hamilton圖的一個應(yīng)用(習(xí)題8.2#6)BCDEFG7位客人入席,A只會講英語,B會講英,漢語,C會講英,意大利,俄語,D會講日,漢語,E會講德,意大利語,F會講法,日,俄語,G會講法,德語.能否安排圓桌席位使每位客人與其左右鄰不用翻譯便可交談?建立無向圖模型:結(jié)點為客人;會共同語言的2結(jié)點相鄰接.則問題歸結(jié)為求此圖的一條Hamilton回路.不難驗證,此圖有一條Hamilton回路是:(A,B,D,F,G,E,C,A).按此回路安排席位可滿足要求.A英英法德俄意日漢Hamilton圖對編碼的一個應(yīng)用把圓周等分成2n個扇形,每一扇形代表一個n位二進制串用以表示旋轉(zhuǎn)指針的位置(不難設(shè)計指針上的n個觸點來實現(xiàn)這個數(shù)).當(dāng)n=3時右下圖是一例.由于交界附近會出現(xiàn)誤差,自然要求相鄰二數(shù)盡可能接近,即要求ijk與uvw相鄰必須滿足|{i,j,k}∩{u,v,w}|=2(1)此問題可歸結(jié)為求立方圖G=V,E,V={000,001,…,111},ijk,uvwE當(dāng)且僅當(dāng)條件(1)成立,的一條Hamilton路.(解存在但不唯一)111110101100000010011001000001011111110100101010有向線圖的鄰接矩陣定義將有向線圖G=V,E的結(jié)點集強行命名(標(biāo)定次序)為

V={1,2,…,n},則n階(0,1)方陣A=(aij)稱為的G鄰接矩陣,其中當(dāng)(i,j)E,aij=1;否則,aij=0.注①鄰接矩陣與結(jié)點的標(biāo)定次序有關(guān),不同的標(biāo)定次序?qū)?yīng)的鄰接矩陣不同,但這兩個矩陣置換相似,即適當(dāng)?shù)亟粨Q行和列的次序能從一個鄰接矩陣變到另一個.或者說,它們對應(yīng)的有向線圖同構(gòu).

②有向線圖在標(biāo)定次序后得到唯一鄰接矩陣;一個n階(0,1)方陣對應(yīng)唯一標(biāo)定次序的有向線圖.換句話說,不計圖的同構(gòu)和矩陣的置換相似有向線圖與一個n階(0,1)方陣一一對應(yīng).有限集V上的關(guān)系R的圖示是以為V結(jié)點集的一個有向線圖易見:關(guān)系R的關(guān)系矩陣正是R的圖示作為有向線圖的鄰接矩陣.一個有向線圖G=V,E對應(yīng)的關(guān)系R的逆關(guān)系R~對應(yīng)的有向線圖G~=V,E~

稱為G的逆圖.G與G~有相同(的強行命名)的結(jié)點集,并且(i,j)E(j,i)E~.逆圖G~的鄰接矩陣A~與原圖的鄰接矩陣A之間的關(guān)系是:A~=AT.無向線圖與賦權(quán)圖的鄰接矩陣定義無向線圖G=V,E,V={1,2,…,n}的鄰接矩陣是n階(0,1)方陣A=(aij),其中當(dāng)(i,j)E,aij=aji=1;否則,aij=aji=0.由此可見,無向線圖的鄰接矩陣是對稱矩陣:A=AT.例如,零圖的鄰接矩陣是零矩陣;

完全圖Kn的鄰接矩陣是恰有n個0并全在對角線上的n階(0,1)方陣.定義賦權(quán)圖G=V,E,W,V={1,2,…,n}的鄰接矩陣是n階(0,1)方陣A=(aij),其中當(dāng)(i,j)E,aij=W(i,j);否則,aij=0.鄰接矩陣的圖論意義設(shè)A為有向線圖G的鄰接矩陣.①A的第i行(列)和等于第i結(jié)點的出(入)度,i=1,…n.②B=AAT=(bij)的元素

bij=ai1aj1+…+ainajn=k表示有k個點,它們都是從i,j引出的有向邊的公共交點.特別,bii是第i結(jié)點的出度.對偶地可討論ATA的元素的圖論意義.③A2=AA=(aij(2))的元素aij(2)=ai1a1j+…+ainanj=k表示有k個點,它們都是從i到j(luò)長為2的有向路徑的中點,即從i到j(luò)長為2的路徑恰有k條.一般地,從i到j(luò)長為m的路徑恰有aij(m)條;過i的長為m的回路恰有aii(m)條.ij有向線圖的可達矩陣將任一有向多重圖G的多重邊只保留其中一邊所得的線圖記為G’,則G’是G的生成子圖,并且任2結(jié)點在G內(nèi)可達當(dāng)且僅當(dāng)它們在G’可達.因此可以只限于研究有向線圖G’的可達性.為了研究有向線圖結(jié)點間的可達性而引入可達矩陣的概念.其定義如下:設(shè)G=V,E是有向線圖,V={1,2,…,n}.n階(0,1)矩陣P=(pij)稱為G的可達矩陣,其元素定義為:當(dāng)點i到點j可達,pij=1;否則,pij=0,i,jV(i到i可達指過i有回路).例如,右之有向圖的可達矩陣是

A=1234如何求n結(jié)點線圖G的可達矩陣?先求出G的鄰接矩陣A和矩陣B=A+A(2)+…+A(n).因為G的基本路徑長不超過n-1和沒有基本u-w路便沒有任何u-w路,故對ij,bij0

當(dāng)且僅當(dāng)vi到vj可達(bij是G的長度不超過n的所有路徑數(shù)).又因G的基本回路長不超過n,故bii0

當(dāng)且僅當(dāng)G中有過vi的回路.方法①

利用矩陣B確定可達矩陣P=(pij):當(dāng)bij=0,pij=0;否則,pij=1.方法②

直接由鄰接矩陣確定可達矩陣:P=A∨A2∨…∨An,其中Ak為A的布爾方冪,例如(易見A(k)與Ak的對應(yīng)元素同時為0或同時不為0)例2(p265)計算中的一些說明由B或P可求得G的強連通分支對應(yīng)結(jié)點集為:{1},{2},{3,4,5}.由A,A(2),…,A(n)的(i,j)元決定i到j(luò)的距離我們知道:當(dāng)B=A+A(2)+…+A(n)的(i,j)元不為0時,G至少有一條長度不超過n的i-j路徑,從而i到j(luò)可達.不僅如此,使aij(k)0的最小正整數(shù)k恰好就是i到j(luò)的距離:d(i,j).例如,k=2,aij=0,aij(2)0

說明點i與j不相鄰,但存在某點m滿足aim=amj=1,即有從i到j(luò)的長為2的路,所以d(i,j)=2.實例在教本p.265例2中有a15=a15(2)=0,a15(3)0,由此推出

d(1,5)=3.因A(k)與Ak的對應(yīng)元素同時為0或同時不為0,故用Ak代替A(k)也可以求兩結(jié)點的距離.8.3#5如何從鄰接矩陣判斷是否歐拉圖?解:首先,利用圖G的鄰接矩陣的第i行(列)和求出

d+(vi)(d-(vi));其次,利用可達矩陣

P=A∨A2∨…∨An

是否為全1矩陣判斷圖G是否為強連通;最后,利用下列等價式判斷圖G是否為歐拉圖:G為歐拉圖

d+(vi)=d-(vi),i=1,…,n

∧G為強連通二部圖的概念定義:簡單無向圖G=V,E稱為二部圖,如果V可劃分為兩個子集X和Y使得E中每條邊的二端點都分別屬于X,Y.二部圖G常記為

G=X,E,Y.二部圖G=X,E,Y稱為完全二部圖,如果X的每一點都與Y的每一點鄰接,完全二部圖常記為Km,n,其中,m=|X|,n=|Y|.例圖8.4-1.用結(jié)點標(biāo)記法判斷已知圖G是否為二部圖方法:步驟:①

任選一點標(biāo)為A;②

把所有與上一步標(biāo)為A(B)的點相鄰的點標(biāo)為B(A),照此繼續(xù),直到每點都被標(biāo)記為止.③

判斷原則:如果標(biāo)記后的圖沒有任何相鄰二點有相同的標(biāo)記,則G是二部圖,其互補結(jié)點子集X,Y分別為兩種標(biāo)記點的集;否則,G不是二部圖.AAAAAAAABBBBBBB非二部圖二部圖無向圖G為二部圖當(dāng)且僅當(dāng)所有回路長為偶數(shù)證

必要性:若G=X,E,Y為二部圖,C=(v0,v1,v2,…,vk,v0)為任一回路,則{v0,v2,…,vk-1},{v1,v3,…,vk}分屬X,Y.因此k為奇數(shù),從而C的長度k+1是偶數(shù).充分性:不妨設(shè)G為任何回路長度均為偶數(shù)的連通圖.取定v0V后,定義V的一個劃分:X={v|d(v0,v)是偶數(shù)}(易見v0X);

Y=V-X用反證法證Y(X)的任二點不相鄰.若vi,vjY∧(vi,vj)E,則d(v0,vi),d(v0,vj)都為奇數(shù),由此推出G中有過v0,vi,vj的長為奇數(shù)的回路的矛盾.v0vivj二部圖的匹配與最大匹配定義:(二部)圖

G=X,E,Y

的邊集E的子集M稱為G的一個匹配,如果M的任二邊都沒有公共端點;G中邊數(shù)最多的匹配稱為最大匹配(不唯一);含有G的每一點的匹配稱為完美匹配(必為最大匹配仍不唯一).下面是最大,完美匹配的例子(用粗線表示):工作分配問題問題某教研室有4位教師:A,B,C,D.A能教課程5;B能教1,2;C能教1,4;D能教課程3.能否適當(dāng)分配他們的任務(wù),使4位教師擔(dān)任4門不同課并且不發(fā)生安排教師教他不能教的課的情況?此問題可歸結(jié)為二部圖的數(shù)學(xué)模型:G={A,B,C,D},E,{1,2,3,4,5},(X,y)E,如果X能教y.一個滿足要求的工作分配正是一個含有4條邊的一個最大匹配.ABCD12345求圖G最大匹配的方法首先

任取一個匹配(含一邊也可)M作為起點.接著按下列方法逐步調(diào)整當(dāng)前匹配(每一步使它調(diào)整為邊數(shù)多1的匹配)最后達到一個最大匹配:步驟①在X中選定一個不屬于M的點xi標(biāo)記(*).步驟②在X的新標(biāo)記的點中選一點,如xi,用(xi)標(biāo)記通過不屬于M的邊與xi鄰接并且尚未標(biāo)記的點(如yi);在Y的新標(biāo)記的點中選一點(如yi),用(yi)標(biāo)記通過M的邊與yi鄰接并且尚未標(biāo)記的點;照此繼續(xù),直到發(fā)現(xiàn)標(biāo)記到Y(jié)的一個點,該點不與X中任一邊相關(guān)聯(lián)或標(biāo)記不到任何這樣的點為止.出現(xiàn)前一情況,便找到一條關(guān)于M的交替鏈(定義8.4-4);利用它可調(diào)整M到一個比M多一邊的匹配;出現(xiàn)后一情況便表示M已為最大匹配.求最大匹配舉例解:①取一個初始匹配M={Bb,Cc,Dd}.②用標(biāo)記法從點A開始求得一條交替鏈:=(AcCe)(左圖).③用調(diào)整匹配M:將中屬于M的邊刪去并將其中不屬于M的其它邊添加到M中得到比M多一邊的新匹配M’(如右圖示).④因?qū)’用標(biāo)記法只能從E或F開始,但都不能求出M’的任何交替鏈,故判定M’是一個最大匹配.A(c)BCD(d)abc(D)d(E)eE(*)F(*)fA(*)BC(c)Dabc(A)de(C)EFfM’樹的概念樹是應(yīng)用中特別重要的特殊圖,分無向樹和有向樹兩種.定義無回路的無向連通圖稱為無向樹.也可以說,無基本回路的無向連通圖稱為無向樹,因為:無回路等價于無基本回路.連通分支全為無向樹的圖,即無回路的無向圖,稱為森林.樹的1度點稱為樹葉,不是樹葉的點稱為分枝點.例圖8.6-1.(n,m)無向線圖G是樹的5個等價條件①G是樹—連通無回路.②G無回路且m=n-1.③G連通且m=n-1.④G無回路且加一邊得唯一回路.⑤G連通且少一邊不連通.⑥G任二點間有唯一(基本)路徑.證

①

②:2結(jié)點樹的邊數(shù)為1=2-1.假設(shè)k結(jié)點樹的邊數(shù)為k-1.要證k+1結(jié)點樹的邊數(shù)為k.事實上,樹G必有一樹葉w(否則G任一點的度都大于1,從任一點出發(fā)沿一邊進入另一點恒可沿另一邊離開.因G的結(jié)點有限,故有限步以后一定要回到前面的點,便與G無回路相矛盾).子圖G-{w}顯然是樹,其點數(shù)是k,按歸納假設(shè)其邊數(shù)是k-1,從而G的邊數(shù)是k=(k+1)-1,歸納證明完成.證

②

③:要證若G無回路且m=n-1,則G連通.不然的話,G有k(2)個無回路的連通分支(樹):T1,…,Tk,設(shè)Ti為(ni,mi)圖,則

m=m1+…+mk=(n1-1)+…+(nk-1)=(n1+…+nk)-k<n-1矛盾.③

④:要證若G連通且m=n-1,則G無回路且加一邊得唯一回路.先對n用歸納法證明G無回路.n=2時顯然成立.設(shè)n=k時結(jié)論已成立并考慮n=k+1的情形.此時若G無1度點,則2m2n與m=n-1矛盾.故G必有1度點w.易見G-w連通且滿足條件(邊數(shù)比點數(shù)少1),由歸納假設(shè)G-w無回路.因w為1度點,故G也無回路.再證G加任一邊e=(vi,vj)得唯一回路.G連通性保證有vi-vj路,從而G+e有回路.因刪去兩條回路中的任一邊仍有回路留下,故G+e不會有兩條回路(否則G有回路).證

④

⑤:要證若G無回路且加一邊得唯一回路,則G連通且刪去一邊不連通.用反證法,因G是森林,若G不連通,則在G的二連通分支的點間加邊不會得新回路,故G連通.若連通的G刪去一邊e還連通,便得出G=(G-e)∪{e}有回路的矛盾.⑤

⑥:要證若G連通且刪去一邊不連通,則G任二點間有唯一路徑.事實上,G連通性保證任2點u,w間有路徑.若有兩條這樣的u-w路徑便與G刪去一邊不連通的假設(shè)矛盾.⑥

①:要證若G任二點間有唯一路徑則G是樹.任2點都可達表示G連通.若G有回路,則G必有兩點其間有兩條路徑,與條件⑥矛盾.推論由條件⑤,樹是結(jié)點數(shù)固定下邊數(shù)最少的連通圖,并且min{m|(n,m)圖連通}=n-1.由條件④,樹是結(jié)點數(shù)固定下邊數(shù)最多的無回路圖,并且max{m|(n,m)圖無回路}=n-1.每棵樹至少有兩片樹葉(n2).證:若不是這樣便有d(v1)+…+d(vn)2(n-1)+1>2(n-1)=2m,與d(v1)+…+d(vn)=2m的已知規(guī)律矛盾.8.6#12

證任何無向樹T都是二部圖解:取定一點wT(樹根).對T-w的每一點v,w到v有唯一鏈,于是d(w,v)=h(v)是v的一個特性參數(shù)（關(guān)于樹根的高).對T-w的任二不同結(jié)點u,v,u和v相鄰僅當(dāng)|h(u)-h(v)|=1.于是令X={v|h(v)為偶數(shù)},Y={v|h(v)為奇數(shù)},則X(Y)的不同點不會相鄰,得證T=X,E,Y是二部圖.wvu生成樹的概念定義無向圖G=V,E的生成子圖T是樹,則稱T是G的一棵生成樹(不唯一,圖8.6-2).任何連通無向圖G至少有一棵生成樹.證(破圈法)若G無簡單回路,則G自己是一棵生成樹.否則,G有簡單回路C1,刪去C1的一邊所得G的生成子圖記為G1.若G1無回路,則G1為生成樹;否則G1有簡單回路C2,刪去C2的一邊所得G1的生成子圖記為G2.若G2無回路,則G2為生成樹;否則,…照此繼續(xù).易見經(jīng)m+1-n步必可找到G的一棵生成樹.推論無向圖G連通當(dāng)且僅當(dāng)G有生成樹.最小生成樹的概念定義賦權(quán)簡單連通無向圖G=V,E,W的子圖

H的權(quán)定義為

H

的所有邊的權(quán)和.G中權(quán)最小的生成樹稱為最小生成樹(對普通簡單連通圖不考慮最小生成樹).最小生成樹有很強的應(yīng)用背景,例如:設(shè)計聯(lián)系若干城市的最短線路通信網(wǎng);設(shè)計供應(yīng)若干居民點的最短自來水管線路等.求最小生成樹的Kruskal算法(避圈法)算法將賦權(quán)簡單連通無向圖G的邊排序:e1e2…em.開始時k:=1,A:=.步驟①

若A∪{ek}導(dǎo)出的子圖無回路,則

A:=A∪{ek}.步驟②

若|A|=n-1,算法結(jié)束;否則轉(zhuǎn)步驟①.例對左邊無向圖用Kruskal算法求得右邊的最小生成樹.123456789101112√

√

√

√

√

√√1234567=n-11234567891011121235689Kruskal算法的正確性證明:由Kruskal算法必可求得賦權(quán)簡單圖G的一棵生成樹T0(因G連通),不妨令T0的邊為e1,…,en-1.若T0不是最小生成樹,則G的每棵最小生成樹對應(yīng)一個i,使得ei+1T但{e1,…,ei}T(i=0表示T與T0無公共邊).由于最小生成樹有限,我們?nèi)為對應(yīng)最大i的那棵最小生成樹.于是,T+ei+1有唯一基本回路C(包含ei+1).因樹T0無回路,故有邊f(xié)C且fT0,即fT-T0.在T中以ei+1代f(仍無回路)得新生成樹T’=T+ei+1-f,其權(quán)為W(T’)=W(T)+W(ei+1)-W(f)W(T).于是W(ei+1)W(f).因T為樹,{e1,…,ei,f}誘導(dǎo)的子圖無回路,從而由Kruskal算法選邊的過程知W(ei+1)W(f).所以W(ei+1)=W(f).這意味著W(T’)=W(T),即T’也是G的最小生成樹.但T’包含{e1,…,ei,ei+1},他比T對應(yīng)更大的i值,引出矛盾.得證必須是最小生成樹.求最小生成樹的破圈法此法1975年由中國數(shù)學(xué)家管梅谷教授首先提出,具體算法如下:將賦權(quán)簡單連通無向圖G=V,E的邊排序:e1e2…em.開始時A:=E.步驟①

若A無回路,則A是最小生成樹,算法結(jié)束,否則轉(zhuǎn)步驟②.步驟②

在A中任取的一條回路C中取有最大權(quán)的邊e,置A:=A-e后轉(zhuǎn)步驟①.破圈法的正確性基于下列事實(定理8.6-9):G的任何一條簡單回路C中權(quán)最大的邊f(xié)一定不屬于任何最小生成樹T.(C必有一邊e不屬于T,若f屬于T,則以e代f所得的生成樹T’的權(quán)W(T’)=W(T)+W(e)-W(f)<W(T),產(chǎn)生矛盾.)123568947121110結(jié)點123456789101112刪去順序254

318.6#5

證連通簡單無向圖G的任一邊e都是G的某棵生成樹的邊解:令G的每一邊的權(quán)為1得出的賦權(quán)圖記為G’.顯然賦權(quán)圖G’的任一最小生成樹也是G的一棵生成樹.

在用Kruskal算法或破圈法求賦權(quán)圖G’的最小生成樹時,只要把所考慮的那邊e排在第一位(因為每邊的權(quán)相同,故任何邊都可排在第一位)就能保證所求得的最小生成樹中一定含有e.有向樹與有根樹的概念借鑒無向樹的概念可以建立有向樹的概念.定義

底圖為樹的有向圖稱為有向樹.有向樹稱為有根樹,如果存在一點(樹根)入度為0而其余每點入度都為1,或等價地,樹根到其它各點都有且僅有一條有向鏈(僅有一條顯然;從任何點一定可以反推到樹根).有根樹必為有向樹,反之不真(右圖為一反例).有根樹的特殊畫法:始點在上終點在下,箭頭略去.例圖8.7-1(a).(與Hasse圖類似)樹葉,分枝點,子樹的概念有根樹的典型例子是家譜樹.樹根是家譜的第一代老祖宗;每條弧始點和終點分別是父和子;每條路徑始點是祖先,終點是后裔.出度為0的結(jié)點(沒有兒子者)稱為樹葉,否則稱為分枝點;分枝點及其所有后裔組成子樹(非根的分枝點導(dǎo)出真子樹).從樹根r到一結(jié)點a有唯一有向路徑,其長度t稱為a的層次(a為第t代孫),有根樹各結(jié)點層次最大值稱為樹的高度.8.7#6

如何利用鄰接矩陣判斷有根樹?解:按定義有向圖G是有根樹

其底