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

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

2、圖為有向圖.有時(shí)用D=表示有向圖.,2.有限圖與n階圖 若G=中V,E都是有窮集合,則稱G為有限圖. 若|V|=n,則稱G為n階圖.,,,,,,例如:圖7.1中(1)為無(wú)向圖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.關(guān)聯(lián)與相鄰 設(shè)圖G=, u,v∈V, (u,v)∈E(有向圖∈E) 常記e=(u,v)(或有向圖e=),稱u,v為e的端點(diǎn). (對(duì)有向圖中的有向邊來(lái)說(shuō),稱u為e的始點(diǎn),v為e的終點(diǎn)) 稱e與u或v是彼此相關(guān)聯(lián)的;無(wú)邊關(guān)聯(lián)的頂點(diǎn)稱為孤立點(diǎn). 若e關(guān)聯(lián)的兩個(gè)頂點(diǎn)重合,則稱e為環(huán); 若u≠v,則稱e與u(或v)的關(guān)聯(lián)次數(shù)為1; 若u=v

4、(即e為環(huán)),則稱e與u關(guān)聯(lián)的次數(shù)為2; 若頂點(diǎn)u,v之間有邊關(guān)聯(lián),則稱u與v相鄰; 若兩條邊至少有一個(gè)公共端點(diǎn),則稱這兩條邊相鄰.,,,5.頂點(diǎn)的度數(shù) 設(shè)v為無(wú)向圖G中的一個(gè)頂點(diǎn),稱v作為邊的端點(diǎn)的次數(shù)之和為v的度數(shù)或度,記作d(v). 若v為有向圖G中的一個(gè)頂點(diǎn),稱v作為邊的始點(diǎn)次數(shù)之和為v的出度,記作d+(v);v作為邊的終點(diǎn)的次數(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.簡(jiǎn)單圖 對(duì)于無(wú)向圖,若關(guān)聯(lián)一對(duì)頂點(diǎn)的邊多于1條,則稱這些邊為平行邊. 對(duì)于有向圖,關(guān)聯(lián)一對(duì)頂點(diǎn)的方向相同的邊,如果多于1條,則稱這些邊為平行邊. 既不含平行邊,也不含環(huán)的圖,稱為簡(jiǎn)單圖.,,7.完全圖 設(shè)G為n階(n個(gè)頂點(diǎn))無(wú)向簡(jiǎn)單圖,若G中任何兩個(gè)頂點(diǎn)均相鄰,則稱G為n階(無(wú)向)完全圖,記作

6、Kn.邊數(shù)n(n-1)/2 設(shè)D為n階(n個(gè)頂點(diǎn))有向簡(jiǎn)單圖,若G中任何兩個(gè)頂點(diǎn)之間均有兩條方向相反的邊,則稱G為n階有向完全圖.邊數(shù)n(n-1),,8.子圖 設(shè)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為頂點(diǎn)集,以兩個(gè)端點(diǎn)均在V1 中的邊為

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

8、點(diǎn)的個(gè)數(shù)為偶數(shù).說(shuō)明:圖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個(gè)3度頂點(diǎn),其余頂點(diǎn)的度數(shù)均小于等于2,問(wèn)G中至少有多少個(gè)頂點(diǎn)?為什么?,三.圖的同構(gòu),設(shè)G1=,G2=為兩個(gè)無(wú)向圖,若存在雙射函數(shù)f:V1->V2,使得對(duì)于任意的e=(v

9、1,v2)∈E1當(dāng)且僅當(dāng)e’=(f(v1),f(v2))∈E2,且e與e’的重?cái)?shù)相同,則稱G1與G2同構(gòu).記作G1≌G2.,例7.2(1)畫(huà)出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無(wú)向簡(jiǎn)單圖 (2)畫(huà)出3個(gè)頂點(diǎn)2條邊的所有可能非同構(gòu)的有向簡(jiǎn)單圖,7.2 通路、回路、圖的連通性,一.術(shù)語(yǔ),1.通路與回路,設(shè)Γ=v0e1v1e2…ekvk為圖G中的頂點(diǎn)與邊的交替序列,若Γ滿足:vi-1,vi為ei的端點(diǎn)(若G為有向圖,vi-1是ei的

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

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

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

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

14、D是弱連通圖(或稱D是連通圖).若D中任何兩頂點(diǎn)至少一個(gè)可達(dá)另一個(gè),則稱D是單向連通圖若D中任何兩頂點(diǎn)都是相互可達(dá)的,則稱D是強(qiáng)連通圖.注)D是強(qiáng)連通圖?D是單向連通圖?D是弱連通圖.,,二.點(diǎn)割集與邊割集,1.點(diǎn)割集與割點(diǎn),若無(wú)向圖G=中,存在V’?V,使得p(G-V’)>p(G),而任意的V”?V’,均有p(G-V”)=p(G),則稱V’為G的點(diǎn)割集.若V’={v},稱v為G的割點(diǎn).,2.邊割集及橋,若無(wú)向圖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}為點(diǎn)割集.,{e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9}等邊割集,e9是橋.,,,7.3 圖的矩陣表示,1.無(wú)向圖的關(guān)聯(lián)矩陣,設(shè)無(wú)向圖G=,V={v1,v2,…,vn},E={e1,e2,…,em}令m

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

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

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

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

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

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

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

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

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

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

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該工程所需最短時(shí)間為12,(2)各頂點(diǎn)的最晚完成時(shí)間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)各頂點(diǎn)的緩沖時(shí)間TS(v1)=TL(v1)-TE(v1)=0-0=0TS(v2)= =TL(v2)-TE(v2)=2-1=1TS