離散數(shù)學第七章圖的基本概念

1、第7章 圖的基本概念,7.1 無向圖及有向圖,7.2 通路、回路、圖的連通性,7.3 圖的矩陣表示,7.4 最短路徑及關鍵路徑,7.1 無向圖及有向圖,一.基本概念和術語,1.無向圖與有向圖,圖:圖G=,其中V為(非空)頂點集合,E是V中頂點偶對的集合,稱為邊.通常用V(G)和E(G)分別表示圖G的頂點集合和邊集合.,無向圖:若圖G中邊集合E(G)為無向邊的集合,則稱該圖為無向圖.有向圖:若圖G中邊集合E(G)為有向邊的集合,則稱該

2、圖為有向圖.有時用D=表示有向圖.,2.有限圖與n階圖 若G=中V,E都是有窮集合,則稱G為有限圖. 若|V|=n,則稱G為n階圖.,,,,,,例如:圖7.1中(1)為無向圖G=,V={v1,v2,v3,v4,v5}, E={(v1,v2),(v2,v2),(v2,v3),(v1,v3),(v1,v3)(v1,v4)};(2)為有向圖D=,V={v1,v2,v3,v4,v5},E={,,,,,, ,},3.零圖與

3、平凡圖 若G=中,E=φ,則稱G為零圖.若|V|=1,則稱G為平凡圖.,4.關聯(lián)與相鄰 設圖G=, u,v∈V, (u,v)∈E(有向圖∈E) 常記e=(u,v)(或有向圖e=),稱u,v為e的端點. (對有向圖中的有向邊來說,稱u為e的始點,v為e的終點) 稱e與u或v是彼此相關聯(lián)的;無邊關聯(lián)的頂點稱為孤立點. 若e關聯(lián)的兩個頂點重合,則稱e為環(huán); 若u≠v,則稱e與u(或v)的關聯(lián)次數(shù)為1; 若u=v

4、(即e為環(huán)),則稱e與u關聯(lián)的次數(shù)為2; 若頂點u,v之間有邊關聯(lián),則稱u與v相鄰; 若兩條邊至少有一個公共端點,則稱這兩條邊相鄰.,,,5.頂點的度數(shù) 設v為無向圖G中的一個頂點,稱v作為邊的端點的次數(shù)之和為v的度數(shù)或度,記作d(v). 若v為有向圖G中的一個頂點,稱v作為邊的始點次數(shù)之和為v的出度,記作d+(v);v作為邊的終點的次數(shù)之和為v的入度,記作d-(v),稱d+(v)+d-(v)為v的度數(shù)或度,記作d(v)

5、. G的最大度:Δ(G)=max{d(v)|v∈V(G)} G的最小度:δ(G)=min{d(v)|v∈V(G)},,6.簡單圖 對于無向圖,若關聯(lián)一對頂點的邊多于1條,則稱這些邊為平行邊. 對于有向圖,關聯(lián)一對頂點的方向相同的邊,如果多于1條,則稱這些邊為平行邊. 既不含平行邊,也不含環(huán)的圖,稱為簡單圖.,,7.完全圖 設G為n階(n個頂點)無向簡單圖,若G中任何兩個頂點均相鄰,則稱G為n階(無向)完全圖,記作

6、Kn.邊數(shù)n(n-1)/2 設D為n階(n個頂點)有向簡單圖,若G中任何兩個頂點之間均有兩條方向相反的邊,則稱G為n階有向完全圖.邊數(shù)n(n-1),,8.子圖 設G=,G’=,若V’?V, E’?E, 則稱G’為G的子圖.記作G’?G. 若G’?G且G’≠G,則稱G’為G的真子圖. 若G’?G且V’=V,則稱G’為G的生成子圖. 若V1?V且V1≠φ,稱以V1為頂點集,以兩個端點均在V1 中的邊為

7、邊集的圖為V1的導出子圖. 若E1?E且E1≠φ,稱以E1為邊集,以E1中邊關聯(lián)的頂點 為頂點集的圖為E1的導出子圖. 注)每個圖都是本身的子圖.,,9.補圖:設G=為n階簡單圖,稱以V為頂點集,以使G成為n階完全圖所添加的邊為邊集的圖為G的補圖,記作,,二.握手定理(圖論基本定理),任何圖G中各頂點的度數(shù)之和等于邊數(shù)的2倍.若G為有向圖,則各頂點的入度之和等于各頂點的出度之和.都等于邊數(shù).,推論:任何圖G中,奇度頂

8、點的個數(shù)為偶數(shù).說明:圖G的度數(shù)序列為{d(v1),d(v2),…,d(vn)},www.yongshengsuoye.com 吺唍咦,例7.1 (1)(3,3,2,3),(5,2,3,1,4)能成為圖的度數(shù)序列嗎?為什么? (2)已知圖G中有10條邊,4個3度頂點,其余頂點的度數(shù)均小于等于2,問G中至少有多少個頂點?為什么?,三.圖的同構,設G1=,G2=為兩個無向圖,若存在雙射函數(shù)f:V1->V2,使得對于任意的e=(v

9、1,v2)∈E1當且僅當e’=(f(v1),f(v2))∈E2,且e與e’的重數(shù)相同,則稱G1與G2同構.記作G1≌G2.,例7.2(1)畫出4個頂點3條邊的所有可能非同構的無向簡單圖 (2)畫出3個頂點2條邊的所有可能非同構的有向簡單圖,7.2 通路、回路、圖的連通性,一.術語,1.通路與回路,設Γ=v0e1v1e2…ekvk為圖G中的頂點與邊的交替序列,若Γ滿足:vi-1,vi為ei的端點(若G為有向圖,vi-1是ei的

10、始點,vi是ei的終點)i=1,2,…,k,則稱Γ為G中通路,v0,vk分別稱為通路的始點和終點,Γ中邊的數(shù)目k稱為通路長度.若v0=vk,則通路稱為回路.若Γ中各邊互不相同,則稱Γ為簡單通路,若v0=vk,則稱Γ為簡單回路.若Γ中各頂點互不相同,則稱Γ為初級通路,若Γ中除v0=vk外,各頂點各不相同,并且各邊也互不相同,則稱Γ為初級回路或圈.有邊重復出現(xiàn)的通路和回路分別稱為復雜通路和回路.,,圖7.7,圖7.7,定理1:在一個

11、n階圖中,若從頂點vi到vj(vi≠vj)存在通路, 則從vi到vj存在長度小于等于n-1的通路.推論:在一個n階圖中,若從頂點vi到vj(vi≠vj)存在通路, 則從vi到vj存在長度小于等于n-1的初級通路.,定理1:在一個n階圖中,如果存在vi到自身的回路, 則從vi到自身存在長度小于等于n的回路.推論:在一個n階圖中,如果存在vi到自身存在一條簡單回路, 則從vi到自身存在長度

12、小于等于n的初級回路.,,,,,2.頂點之間的連通關系,在無向圖G中,若頂點vi到vj有通路,則稱vi與vj連通.規(guī)定頂點與自身連通.頂點之間的連通關系是等價關系.在有向圖G中,若頂點vi到vj有通路,則稱vi可達vj.規(guī)定任何頂點與自身可達.,3.短程線與距離,若vi與vj連通(有向圖,若vi可達vj),則稱vi到vj長度最短的通路為vi到vj的短程線,短程線的長度稱為vi到vj的距離,用d(vi,vj)表示.(對于有向圖,用d

13、表示).說明:若vi與vj不連通(對于有向圖,若vi不可達vj), 則規(guī)定d(vi,vj)=∞(d=∞). 其他情況滿足距離公式.,,,4.無向圖的連通性,若無向圖G中任何兩頂點都連通,則稱G是連通圖.對于任意的無向圖G.設V1,V2,…,Vk是頂點之間連通關系的等價類,則稱他們的導出子圖為G的連通分支.用p(G)表示G的連通分支數(shù).,,5.有向圖的連通性,若略去有向圖D中各邊的鍵頭,所得無向圖是無向連通圖,則稱

14、D是弱連通圖(或稱D是連通圖).若D中任何兩頂點至少一個可達另一個,則稱D是單向連通圖若D中任何兩頂點都是相互可達的,則稱D是強連通圖.注)D是強連通圖?D是單向連通圖?D是弱連通圖.,,二.點割集與邊割集,1.點割集與割點,若無向圖G=中,存在V’?V,使得p(G-V’)>p(G),而任意的V”?V’,均有p(G-V”)=p(G),則稱V’為G的點割集.若V’={v},稱v為G的割點.,2.邊割集及橋,若無向圖G=中,存在

15、E’?E,使得p(G-E’)>p(G),而任意的E”?E’,均有p(G-E”)=p(G),則稱E’為G的邊割集或割集.若E’={e},稱e為G的割邊或橋.,{v3,v5},{v2},{v6}為點割集.,{e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9}等邊割集,e9是橋.,,,7.3 圖的矩陣表示,1.無向圖的關聯(lián)矩陣,設無向圖G=,V={v1,v2,…,vn},E={e1,e2,…,em}令m

16、ij為頂點vi與ej的關聯(lián)次數(shù),則稱(mij)n×m為G的關聯(lián)矩陣.記為M(G),性質:,,2.有向圖的關聯(lián)矩陣,設有向圖D=,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi為ej的始點令mij= 0, vi與ej不關聯(lián) -1, vi為ej的終點則稱(mij)n×m為D的關聯(lián)矩陣.記為M(D).,,性質:,3.有向圖的鄰接矩陣,設有向圖D=

17、,V={v1,v2,…,vn},|E|=m令a(1)ij為vi鄰接到vj的邊的條數(shù),則稱 為D的鄰接矩陣,記為A(D).,,D中長度為l≥2的通路數(shù)和回路數(shù)為:,為頂點vi到vj長度為l的通路數(shù), 為vi到自身長度為l的回路數(shù).,Al中所有元素之和 為D中長度為l的通路數(shù).Al對角線上元素之和 為D中始于(終于)各頂點的長度為l的回路數(shù).,例如:,定理:設A為有向圖D的鄰接矩陣,

18、 V={v1,v2,…,vn}, 則Al(l≥1)中元素a(l)ij為vi到vj長度為l的通路數(shù). 為D中長度為l的通路總數(shù).其中 為D長度為l的回路數(shù).,推論:設Br=A+A2+…+Ar (r?1), 則Br中元素b(r)ij為D中vi到vj長度小于等于r的通路數(shù) 為D中長度小于等于r的通路總數(shù),其中 為D中長度小于等于r的回路總數(shù).

19、,,,由于a(2)13=3,a(3)13=4,a(4)13=6知,D中v1到v3長度為2的通路有3條;長度為3的通路有4條;長度為4的通路有6條.由于a(2)11=1,a(3)11=1,a(4)11=1知,D中v1到自身長度為2,3,4的回路各有1條.由于∑a(2)ij=10知長度為2的通路總數(shù)為10.,4.有向圖的可達矩陣,設有向圖D=,V={v1,v2,…,vn}, 1, vi可達vj.令pij=

20、 i≠j, pii=1,i=1,2,…,n 0,否則則稱(pij)n×n為D的可達矩陣,記為p(D),簡記p,,7.4 最短路徑及關鍵路徑,一.帶權圖,對于圖的每條邊e=(vi,vj)(e=),附加上一個實數(shù)w(e)(或記為wij)稱w(e)(wij)為邊e上的權.若G各邊均有權,則稱G為帶權圖.并稱G中各邊帶權之和為G的權.記為W(G).,二.最短路徑,Dijkstra(迪杰斯特拉

21、)標號法的基本思想:把圖中所有的頂點分成兩組,第一組包括已確定最短路徑的頂點,第二組包括尚未確定最短路徑的頂點,按最短路徑長度遞增的順序逐個把第二組的頂點加到第一組中去,直到從v1出發(fā)可以到達的所有頂點都包括在第一組中.,具體算法:,開始r=0;v1獲p標號,l(0)1=0,p0={v1},T0=V-{v1},Vj(j≠1)的t標號;l(0)j=w1j.（臨時性標號）①求下一個p標號頂點: 設l(r)*i=min{l(r-1)

22、j} r≥1 將標在相應頂點vi處,表明vi獲得p標號,修改通過集和未通過集Pr=Pr-1∪{vi},Tr=Tr-1-{vi}查Tr;若Tr=φ,則算法結束;否則轉②②修改Tr中頂點的t標號: l(r)j=min{l(r-1)j,l(r)*i+wij},l(r)*i是剛剛獲得p標號頂點的p標號,令r=r+1轉①,,例7.3求圖7.13所示圖中頂點v0與v5的最短路徑.,V0到v5的最短路徑為Γ=v0v1v2v4v3v5,W(Γ)=

23、9從而可知v0到其它頂點的最短路徑:Γ=v0v1,W(Γ)=1;Γ=v0v1v2,W(Γ)=3;Γ=v0v1v2v4v3W(Γ)=7;Γ=v0v1v2v4,W(Γ)=4,三.關鍵路徑,實施一個工程計劃時,若將整個工程分成若干工序,有些工序可以同時實施,有些工序必須在完成另一些工序之后才能實施.問題是求計劃完成整個工程的最短時間和每個工序的最早完成時間及最晚完成時間.根據(jù)工序的最早和最晚完成時間確定關鍵路徑.,1.PERT圖(計劃評

24、審技術圖),設D=是n階有向帶權圖,滿足1)D是簡單圖.2)D中無回路.3)有一個頂點入度為0,稱此頂點為發(fā)點, 有一個頂點出度為0,稱此頂點為收點.4)記邊帶的權為wij,它常表示時間.則稱D為PERT圖.,,2.工序的最早完成時間,TE(v1)=0TE(vi)=max{TE(vj)+wij} (vj為vi的前驅,i=2,3,…,n.)TE(vn)就是從v1到vn的最長路徑的權,記為計劃完成該工程所需的最短時間.,

25、3.工序的最晚完成時間,TL(vn)=TE(vn)TL(vi)=min{TL(vj)-wij} (vj為vi的后繼,i=n-1,n-2,…,1),4.工序的緩沖時間,TS(vi)=TL(vi)-TE(vi) (i=1,2,…,n)緩沖時間TS(vi)=0的工序為關鍵工序,它所經(jīng)過的各頂點的路徑稱為關鍵路徑.,,,,例7.4求圖7.14所示PERT圖中各頂點的最早,最晚和緩沖時間以及關鍵路徑.,解:(1)各頂點的最早完成時間

26、 TE(v1)=0 TE(v2)=max{0+1}=1 TE(v3)=max{0+2,1+0}=2,TE(v4)=max{0+3,2+2}=4TE(v5)=max{1+3,4+4}=8TE(v6)=max{2+4,8+1}=9TE(v7)=max{1+4,2+4}=6TE(v8)=max{9+1,6+6}=12該工程所需最短時間為12,(2)各頂點的最晚完成時間TL(v8)=12TL(v7)=m

27、in{12-6}=6TL(v6)=min{12-1}=11TL(v5)=min{11-1}=10TL(v4)=min{10-4}=6TL(v3)=min{6-2,11-4,6-4}=2TL(v2)=min{2-0,10-3,6-4}=2TL(v1)=min{2-1,2-2,6-3}=0,(3)各頂點的緩沖時間TS(v1)=TL(v1)-TE(v1)=0-0=0TS(v2)= =TL(v2)-TE(v2)=2-1=1TS