圖論及應用剖析

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

也是(可空)有限集合,它的元素稱為邊.圖G的邊e是一個結點二重組:a,b,a,bV,e可以是有序的,稱為有向邊,簡稱為弧,a稱為弧e的始點,b稱為e的終點;e也可以是無序的,稱為無向邊.e=a,b時,稱e與a,b關聯(lián),或a,b與e關聯(lián),或a與b相鄰接;關聯(lián)于同一結點的一條邊稱為自回路.每條邊都是無向邊的圖稱為無向圖;每條邊都是有向邊的圖稱為有向圖;我們僅討論無向圖和有向圖.(看圖8.1-1和圖8.1-2)圖的定義與記號續(xù)不與任何結點鄰接的結點稱為孤立結點,全為孤立結點組成的圖(視為無向圖有向圖均可)稱為零圖.在無向圖中兩結點間(包括結點自身)若多于一條邊，則稱這幾條邊為平行邊.在有向圖中若同始點和同終點的邊多于一條,則稱這幾條邊為平行邊,平行邊的條數(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結點的度(次數(shù))有向圖中,以結點v為始點的邊數(shù)稱為v的出度,記為deg+(v);以結點v為終點的邊數(shù)稱為v的入度,記為deg-(v);它們的和:

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

n

結點

m

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

令

v1,…,vn為圖的所有結點,則

i=1n

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

i=1n

deg+(v)+

i=1n

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

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

G

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

G

中沒有孤立點,則

G

中

n個結點的度只取

n-1

個可能值:

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

G

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

v1,…,vk-1的度只取

k-2個可能值:

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

k-1個結點中至少有兩個同度點.圖的同構定義:對給定兩個圖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同構,記為

GG.注:①

兩圖同構是相互的:GG

GG.②

兩圖同構時不僅結點之間要有一一對應關系,而且要求這種對應關系保持結點間的鄰接關系.對有向圖同構還要求保持邊的方向.③

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

G

G’

H

H’1

a,2

b,3

c,1

a,2

b,3

c,4

d4

d,5

e,6

f1234abcd123456abcdefGG’HH’非同構圖舉例存在結點數(shù)及每個結點對應度都相等的兩個圖仍然不同構的情況.一個例子是圖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無孤立結點且G由E唯一確定,則稱G是由邊集E導出的子圖;若對子圖

G=V,E中任二結點

u,v,(u,v)E

(u,v)E,則稱

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

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

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

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

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

也可只用結點序列

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

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

n證:設任一鏈

P

的長度為k,則

P穿程于

k+1個結點:P

=

v0e1v1e2v2

ekvkvk.

因

v0,v1,,vk

兩兩不同,故

k+1n,從而

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

k

個不同結點，從而

kn.距離的概念圖

G=V,E中,從結點

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

當且僅當

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

d(u,v)=+

或

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

u

到

v

長度為

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

連通當且僅當

G

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

G

的結點集的一個劃分,屬于一個等價類的結點導出

G

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

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

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

G

稱為是弱連通的;若

G

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

G

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

G

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

單向連通性

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

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

G

及其子圖

G.若

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

G

中沒有以

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

G為

G

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

G恰有的2個奇度結點可達解1:令u,w為G恰有的2個奇度結點.考察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ù)).賦權圖中的距離應用廣泛的賦權圖是三重組:G=V,E,W,V,E

分別為

G

的結點集和邊集,W是從

E

到

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

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

e

的權.

賦權圖

G的一條路徑

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

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

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

把結點集V分割為二子集

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

對每結點

tT,求出

D(t)之后再定出xT

使得

D(x)=

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

置

S

為

S∪{x}置

T為T-{x}.若

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

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

開始時令

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

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

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

2

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

05326101555462233881063

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

G

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

Euler

路徑(回路).

具有

Euler

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

無向連通圖G有一條Euler路徑當且僅當

G

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

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

G

是Euler圖當且僅當

G

的結點度數(shù)都是偶數(shù).應用:Konigsberg七橋問題不可解,因對應圖(見圖8.2-8(b))都是

3

度結點.用定理8.2-4的證明方法構造Euler回路1155522233444111234113515245=123411352451=12341352451無向圖

G

能否一筆畫的問題等價于

G

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

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

的一條Hamilton

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

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

n3

完全圖

Kn

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

SV有

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

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

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

而

C-S=C1-{a2}是鏈,當且僅當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圖(用一種符號標記法證明).結點符號標記法補充圖標記結束后,可能出現(xiàn)相鄰結點標記符號相同的情況,此時應先在該對結點之間增加一個新結點(此點必為2度點),同時將它標以不同的符號.設所有有相同標記的鄰點都做上述處理之后得到的圖記為G.則

G

有Hamilton路當且僅當G有Hamilton路.故若

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

G

不是Hamilton圖.AAABBBAAABBBBGG

n(3)結點無向簡單圖G為Hamilton圖的一個充分條件:n/2,記最小度數(shù)證:用反證法.若結論不成立,則必有n結點的最大(邊數(shù)最多)非Hamilton圖G=V,E.因GKn,故G有結點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=(否則設某viS∩T,則如下圖所示G有Hamilton回路矛盾).因此

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

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

n/2.例

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

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

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

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

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

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

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

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

當且僅當G中有過vi的回路.方法①

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

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

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

d(1,5)=3.因A(k)與Ak的對應元素同時為0或同時不為0,故用Ak代替A(k)也可以求兩結點的距離.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.用結點標記法判斷已知圖G是否為二部圖方法:步驟:①

任選一點標為A;②

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

判斷原則:如果標記后的圖沒有任何相鄰二點有相同的標記,則G是二部圖,其互補結點子集X,Y分別為兩種標記點的集;否則,G不是二部圖.AAAAAAAABBBBBBB非二部圖二部圖無向圖G為二部圖當且僅當所有回路長為偶數(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ù).充分性:不妨設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.能否適當分配他們的任務,使4位教師擔任4門不同課并且不發(fā)生安排教師教他不能教的課的情況?此問題可歸結為二部圖的數(shù)學模型:G={A,B,C,D},E,{1,2,3,4,5},(X,y)E,如果X能教y.一個滿足要求的工作分配正是一個含有4條邊的一個最大匹配.ABCD12345求圖G最大匹配的方法首先

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

①

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

②

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

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

④:要證若G連通且m=n-1,則G無回路且加一邊得唯一回路.先對n用歸納法證明G無回路.n=2時顯然成立.設n=k時結論已成立并考慮n=k+1的情形.此時若G無1度點,則2m2n與m=n-1矛盾.故G必有1度點w.易見G-w連通且滿足條件(邊數(shù)比點數(shù)少1),由歸納假設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刪去一邊不連通的假設矛盾.⑥

①:要證若G任二點間有唯一路徑則G是樹.任2點都可達表示G連通.若G有回路,則G必有兩點其間有兩條路徑,與條件⑥矛盾.推論由條件⑤,樹是結點數(shù)固定下邊數(shù)最少的連通圖,并且min{m|(n,m)圖連通}=n-1.由條件④,樹是結點數(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ù)（關于樹根的高).對T-w的任二不同結點u,v,u和v相鄰僅當|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連通當且僅當G有生成樹.最小生成樹的概念定義賦權簡單連通無向圖G=V,E,W的子圖

H的權定義為

H

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

若A∪{ek}導出的子圖無回路,則

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

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

√

√

√

√

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

若A無回路,則A是最小生成樹,算法結束,否則轉步驟②.步驟②

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

318.6#5

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

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

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

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

其底