第七章 圖的基本概念.

1、第第7章章 圖的基本概念圖的基本概念 圖論圖論（graphic theory）的起源可追溯到18世紀(jì)，數(shù)學(xué)家歐拉1736年發(fā)表了關(guān)于圖論的第一篇論文，解決了著名的哥尼斯堡七橋問題。但直到20世紀(jì)中后期，尤其是計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展，圖的理論研究和應(yīng)用研究才得到廣泛的重視，圖論作為一個(gè)重要的數(shù)學(xué)分支，才真正確立了自己的地位。 圖論的內(nèi)容十分豐富,是一門交叉性很強(qiáng)、應(yīng)用很廣泛的學(xué)科。計(jì)算機(jī)科學(xué)、網(wǎng)絡(luò)理論、信息論、運(yùn)籌學(xué)、語言學(xué)、物理、化學(xué)等都以圖作為工具, 來解決理論問題和實(shí)際問題。 離散數(shù)學(xué)研究的圖是不同于幾何圖形、機(jī)械圖形的另一種數(shù)學(xué)結(jié)構(gòu),不關(guān)心圖中頂點(diǎn)的位置、邊的長(zhǎng)短和形狀, 只關(guān)心頂點(diǎn)與邊

2、的聯(lián)結(jié)關(guān)系。目 錄7.1 無向圖及有向圖7.2 通路、回路、圖的連通性7.3 圖的矩陣表示7.4 最短路徑問題及關(guān)鍵路徑 7.1 無向圖及有向圖無向圖及有向圖設(shè)A,B為兩集合,稱 a,baAbB為A與B的無序積,記作AB將無序?qū),b記作(a,b).J定義7.1 一個(gè)無向圖G是一個(gè)二元組,即 G,其中, (1)V是一個(gè)非空的集合,稱為G的頂點(diǎn)集,V中元素稱為頂點(diǎn)或結(jié)點(diǎn)； (2)E是無序積VV的一個(gè)多重子集,稱E為G的邊集,E中元素稱為無向邊或簡(jiǎn)稱邊.無向圖元素可重復(fù)出現(xiàn)的集合為元素可重復(fù)出現(xiàn)的集合為多重集多重集例如： G=,V=v1, v2, v3, v4, v5, E= (v1, v2),(

3、v2, v2),(v2, v3),(v1, v3), (v1, v3),(v1, v4)G的圖形為：e5v5v4v3v2v1e4e3e2e1e6有向圖有向圖J定義7.2 一個(gè)有向圖D是一個(gè)二元組,即 D,其中, (1)V同無向圖中的頂點(diǎn)集； (2)E是卡氏積的多重子集,其元素稱為有向邊,也簡(jiǎn)稱邊.有時(shí)用V(D),E(D)分別表示圖D的頂點(diǎn)集和邊集。例如： D=,V=v1, v2, v3, v4, v5, E= , ,G的圖形為：e5v5v4v3v2v1e4e3e2e1e6e7e8 設(shè)G為一無向圖或有向圖 (1)若V,E都是有窮集合,則稱G是有限圖. (2)若Vn,則稱G為n階圖 (3)若E,則

4、稱G為零圖特別是,若此時(shí)又有V1,則稱G為平凡圖.5階圖階圖零圖零圖平凡圖平凡圖J定義7.3 設(shè)ek(vi,vj)為無向圖G中的一條邊,稱vi,vj為ek的端點(diǎn), ek與vi(或vj)是彼此關(guān)聯(lián)的. 無邊關(guān)聯(lián)的頂點(diǎn)稱為孤立點(diǎn).若一條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)重合,則稱此邊為環(huán).e5v5v4v3v2v1e4e3e2e1e6ek與vi(或vj)的關(guān)聯(lián)次數(shù)1vi(vj)是ek的端點(diǎn)且vivj,2vi(vj)是ek的端點(diǎn)且vivj,0vi(vj)不是ek的端點(diǎn)e5v5v4v3v2v1e4e3e2e1e6J定義7.4 設(shè)無向圖G=,vi, vjV, ek,elE.(1)若存在一條邊e以vi、vj為端點(diǎn),即e=(

5、vi, vj),則稱vi, vj是彼此相鄰的,簡(jiǎn)稱相鄰的(2)若ek, el至少有一個(gè)公共端點(diǎn),則稱ek, el是彼此相鄰的,簡(jiǎn)稱相鄰的e5v5v4v3v2v1e4e3e2e1e6 對(duì)有向圖若ekvi,vj,除稱vi, vj是ek的端點(diǎn)外,還稱vi是ek的始點(diǎn), vj是ek的終點(diǎn),vi鄰接到vj,vj鄰接于vi.e5v5v4v3v2v1e4e3e2e1e6e7e8J定義7.5 設(shè)G為一無向圖,viV,稱vi作為邊的端點(diǎn)的次數(shù)之和為vi的度數(shù),簡(jiǎn)稱度,記作d(vi). 稱度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn),它所對(duì)應(yīng)的邊為懸掛邊.v1v2v5v4v3d(vi)= ?設(shè)D為一有向圖,vjV, 稱vj作為邊的始

6、點(diǎn)的次數(shù)之和,為vj的出度,記作d+(vj)； 稱vj作為邊的終點(diǎn)的次數(shù)之和,為vj的入度,記作d-(vj)； 稱vj作為邊的端點(diǎn)的次數(shù)之和,為vj的度數(shù),簡(jiǎn)稱度,記作d(vj). 顯然d(vj)d+(vj)d-(vj). d(v1)3，d+(v1)2，d-(v1)1； d(v2)3，d+(v2)2，d-(v2)1； d(v3)5，d+(v3)2，d-(v3)3； d(v4)d+(v4)d-(v4)0； d(v5)1，d+(v5)0，d-(v5)1； 其中，v5是懸掛結(jié)點(diǎn)，為懸掛邊。?例v5v1v2v3v4對(duì)于圖G,記(G)maxd(v)vV, (G)mind(v)vV,分別稱為G的最大度和最

7、小度.v1v2v5v4v34， 0。.| )(min)(;| )(min)(;| )(max)(;| )(max)(VvvdDVvvdDVvvdDVvvdD若DV,E是有向圖,除了(D),(D)外,還有最大出度、最大入度、最小出度、最小入度,分別定義為v5v4v3v2v1. 0; 1; 3; 3J定理7.1（握手定理） 設(shè)圖G為無向圖或有向圖,Vv1,v2,.,vn,|E|=m(m為邊數(shù)),則J推論 任何圖(無向的或有向的)中,度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù).mvdnii2)(1J定理7.2設(shè)有向圖D,Vv1,v2,.,vn,Em,則 設(shè)Vv1,v2,.,vn為圖G的頂點(diǎn)集,稱(d(v1),d(v2

8、),.,d(vn)為G的度數(shù)序列.mddniinii11)V()V(?例v1v2v5v4v3度數(shù)序列（4，4，3，1，0）度數(shù)序列（3，4，3，4，2）v5v4v3v2v1 (1) (3,3,2,3),(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？ 答：不能，由握手定理易知。 (2) 已知圖G中有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)的度數(shù)均小于等于2.問G中至少有多少個(gè)頂點(diǎn)？為什么？ 答：至少有8個(gè)頂點(diǎn)。?例J定義7.6 在無向圖中,關(guān)聯(lián)一對(duì)頂點(diǎn)的無向邊如果多于1條,稱這些邊為平行邊.平行邊的條數(shù)稱為重?cái)?shù). 在有向圖中,關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于1條,且它們的始點(diǎn)與終點(diǎn)相同,則稱這些邊為有

9、向平行邊,簡(jiǎn)稱平行邊.含平行邊的圖稱為多重圖.既不含平行邊,也不含環(huán)的圖稱為簡(jiǎn)單圖.e5v5v4v3v2v1e4e3e2e1e6 e4與e5是平行邊 e3與e4是平行邊 e7與e8不是平行邊e5v5v4v3v2v1e4e3e2e1e6e7e8J定義7.7 設(shè)G=是n階無向簡(jiǎn)單圖,若G中任何頂點(diǎn)都與其余的n-1個(gè)頂點(diǎn)相鄰,則稱G為n階無向完全圖,記作Kn. 設(shè)D=為n階有向簡(jiǎn)單圖,若對(duì)于任意的頂點(diǎn)u,vV(uv),既有有向邊,又有,則稱D是n階有向完全圖.注：Kn均指無向完全圖.圖(1)中所示為K4,(2)所示為K5,(3)所示為3階有向完全圖.?例(1)(2)(3)J定義7.8 設(shè)G=, G=

10、是兩個(gè)圖.若VV,且EE,則稱G是G的子圖, G是G的母圖,記做G G.若G G且GG(即VV或E E),則G是G的真子圖.若GG且V=V則稱G是G的生成子圖.設(shè)V1V ,且V1,以V1為頂點(diǎn)集,以兩端點(diǎn)均在V1中的全體邊為邊集的G的子圖,稱為V1導(dǎo)出的導(dǎo)出子圖. 設(shè)E1 E,且E1 ,以E1為邊集,以E1中關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的G的子圖稱為E1導(dǎo)出的導(dǎo)出子圖. ?例 下圖給出了圖G以及它的真子圖G和生成子圖G。G是結(jié)點(diǎn)集v1,v2,v4,v5,v6的導(dǎo)出子圖。v1v2v3v4e4e5e1e2e3v1v2v3v4e4e1e3v1v2e4e5v1 v2v3e4e1e2e3v1 v2v3e1e

11、3v1v2e1?例(1)(2)(3)(6)(5)(4)J定義7.9 設(shè)G=是n階無向簡(jiǎn)單圖.以V為頂點(diǎn)集,以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對(duì)于完全圖Kn的補(bǔ)圖,簡(jiǎn)稱G的補(bǔ)圖,記作G . 有向簡(jiǎn)單圖的補(bǔ)圖可類似定義.?例互補(bǔ)互補(bǔ)互補(bǔ)互補(bǔ)觀察下列圖有何特點(diǎn)？J圖(a)、圖(b)、圖(c)和圖(d)所表示的圖形實(shí)際上都是一樣的。bdcdcbadcbadcbaa圖(a) 圖(b) 圖(c) 圖(d)J定義7.10 設(shè)兩個(gè)無向圖G1=,G2=,如果存在雙射函數(shù)：V1V2,使得對(duì)于任意的e=(vi,vj)E1當(dāng)且僅當(dāng)e=( (vi), (vj)E2,并且e與e的重?cái)?shù)相同,則

12、稱G1與G2是同構(gòu)的,記作G1 G2.(1) (2),頂點(diǎn)之間的對(duì)應(yīng)關(guān)系為av1,bv2,cv3,dv4,ev5.abedc1v2v3v4v5v) 1 ()2(a) (b) (c) (a)所示圖稱為彼德森圖.(a) (b) (c)1、頂點(diǎn)個(gè)數(shù)相同2、邊的條數(shù)相同3、度數(shù)相同的結(jié)點(diǎn)數(shù)相同兩圖同構(gòu)?例(1)畫出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無向簡(jiǎn)單圖； (1)(2)(3)(2)畫出3個(gè)頂點(diǎn)2條邊的所有可能非同構(gòu)的有向簡(jiǎn)單圖.(1)(2)(3)(4)7.2 通路、回路、圖的連通性通路、回路、圖的連通性J定義7.11 給定圖G.設(shè)G中頂點(diǎn)和邊的交替序列為v0e1v1e2elvl,若滿足如下條件: v

13、i-1和vi是ei的端點(diǎn)(在G是有向圖時(shí),要求vi-1是ei的始點(diǎn),vi是ei的終點(diǎn)),i1,2,l,則稱為頂點(diǎn)v0到vl的通路. v0和vl分別稱為此通路的起點(diǎn)和終點(diǎn),中邊的數(shù)目l稱為的長(zhǎng)度. 當(dāng)v0vl時(shí),此通路稱為回路. 若中的所有邊e1,e2,el互不相同,則稱為簡(jiǎn)單通路或一條跡.若回路中的所有邊互不相同,稱此回路為簡(jiǎn)單回路或一條閉跡.若通路的所有頂點(diǎn)v0,v1,vl互不相同(從而所有邊互不相同),則稱此通路為初級(jí)通路或一條路徑.若回路中,除v0vl外,其余頂點(diǎn)各不相同,所有邊也各不相同,則稱此回路為初級(jí)回路或圈. 有邊重復(fù)出現(xiàn)的通路稱為復(fù)雜通路,有邊重復(fù)出現(xiàn)的回路稱為復(fù)雜回路.由定義

14、可知,初級(jí)通路(回路)是簡(jiǎn)單通路(回路),但反之不真.注：上述定義既適合無向圖，也適合有向圖。?例v1v0v4v2v3v5v8v6v7v1v0v4v2v3v1v0v4v2v3v1v0v4v2v3v5v8v6v7(1)為v0到v4的長(zhǎng)為4的初級(jí)通路(2)為v0到v4的長(zhǎng)為4的初級(jí)通路(3)為v0到v8的長(zhǎng)為8的簡(jiǎn)單通路(4)為v0到v8的長(zhǎng)為8的簡(jiǎn)單通路J定理7.3 在一個(gè)n階圖中,若從頂點(diǎn)vi到vj(vivj)存在通路,則從vi到vj存在長(zhǎng)度小于等于n-1的通路.推論 在一個(gè)n階圖中,若從頂點(diǎn)vi到vj(vivj)存在通路,則從vi到vj存在長(zhǎng)度小于等于n-1的初級(jí)通路. J定理7.4 在一個(gè)

15、n階圖中,如果存在vi到自身的回路,則從vi到自身存在長(zhǎng)度小于等于n的回路.推論 在一個(gè)n階圖中,如果vi到自身存在一條簡(jiǎn)單回路,則從vi到自身存在長(zhǎng)度小于等于n的初級(jí)回路.J定義7.12在一個(gè)無向圖G中,若從頂點(diǎn)vi到vj存在通路(當(dāng)然從vj到vi也存在通路),則稱vi與vj是連通的.規(guī)定vi到自身總是連通的. 在一個(gè)有向圖D中,若從頂點(diǎn)vi到vj存在通路,則稱vi可達(dá)vj.規(guī)定vi到自身總是可達(dá)的.短程線(無向圖) 設(shè)vi,vj為無向圖G中的任意兩點(diǎn),若vi與vj是連通的,則稱vi與vj之間長(zhǎng)度最短的通路為vi與vj之間的短程線,短程線的長(zhǎng)度稱為vi與vj之間的距離,記作d(vi,vj).

16、短程線(有向圖) 設(shè)vi,vj為有向圖D中任意兩點(diǎn),若vi可達(dá)vj,則稱從vi到vj長(zhǎng)度最短的通路為vi到vj的短程線,短程線的長(zhǎng)度稱為vi到vj的距離,記作d.性質(zhì)u若vi不可達(dá)vj,規(guī)定d. d具有下面性質(zhì):(1) d 0,當(dāng)vivj時(shí),等號(hào)成立.(2)滿足三角不等式,即 d+d d.在無向圖中,還有對(duì)稱性,即 d(vi,vj)d(vj,vi).連通圖(無向圖)J定義7.13 若無向圖G是平凡圖,或G中任意兩頂點(diǎn)都是連通的,則稱G是連通圖;否則,稱G是非連通圖.無向圖中,頂點(diǎn)之間的連通關(guān)系是等價(jià)關(guān)系.設(shè)G為一個(gè)無向圖,R是G中頂點(diǎn)之間的連通關(guān)系,按著R可將V(G)劃分成k(k1)個(gè)等價(jià)類,

17、記成V1,V2,Vk,由它們導(dǎo)出的導(dǎo)出子圖GV1,GV2,GVk稱為G的連通分支,其個(gè)數(shù)記為p(G). G1是連通圖，p(G1)1； G2是非連通圖，且p(G2)3。G1G2?例連通圖(有向圖)J定義7.14設(shè)D是一個(gè)有向圖,如果略去D中各有向邊的方向后所得無向圖G是連通圖,則稱D是連通圖,或稱D是弱連通圖.若D中任意兩頂點(diǎn)至少一個(gè)可達(dá)另一個(gè),則稱D是單向連通圖.若D中任何一對(duì)頂點(diǎn)都是相互可達(dá)的,則稱D是強(qiáng)連通圖?例圖a為弱連通圖；圖b為單向連通圖；圖c為強(qiáng)連通圖。圖a 圖b 圖c J定義7.15 設(shè)無向圖G,若存在頂點(diǎn)子集VV,使G刪除V將V中頂點(diǎn)及其關(guān)聯(lián)的邊都刪除)后,所得子圖GV的連通分

18、支數(shù)與G的連通分支數(shù)滿足 p(G-V)p(G),而刪除V的任何真子集V后,p(G-V)p(G),則稱V為G的一個(gè)點(diǎn)割集.若點(diǎn)割集中只有一個(gè)頂點(diǎn)v,則稱v為割點(diǎn).若存在邊集子集E E,使G刪除E(將E中的邊從G中全刪除)后,所得子圖的連通分支數(shù)與G的連通分支數(shù)滿足p(G-E)p(G),而刪除E的任何真子集E后,p(G-E)p(G),則稱E是G的一個(gè)邊割集.若邊割集中只有一條邊e,則稱e為割邊或橋.v2, v7，v3，v4為點(diǎn)割集，v3，v4為割點(diǎn)e1, e2，e1, e3, e4，e6，e7, e8，e2, e3, e4等都是割集，其中e6是橋。v5e8v6v7v1v4v2v3e1e2e3e4e

19、5e6e7e9?例 本節(jié)概念:無向圖、有向圖、 n階圖、零圖、平凡圖 、彼此關(guān)聯(lián)、相鄰、度d(vi) 、出度d+(vj) 、入度d-(vj) 、握手定理及其推論 、度數(shù)序列、簡(jiǎn)單圖、 n階無向完全圖、子圖、母圖、生成子圖、導(dǎo)出子圖、補(bǔ)圖、同構(gòu)、通路、回路、連通圖、點(diǎn)割集、邊割集7.3 圖的矩陣表示無向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣有向圖的鄰接矩陣有向圖的可達(dá)矩陣無向圖的關(guān)聯(lián)矩陣 設(shè)無向圖G,Vv1,v2,vn,Ee1,e2,em,令mij為頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù),則稱(mij)nm為G的關(guān)聯(lián)矩陣,記為M(G)mij0 (v0 (vi i與與e ej j無關(guān)無關(guān)),),1 (v1 (vi i與

20、與e ej j關(guān)聯(lián)關(guān)聯(lián)1 1次次),), (v (vi i與與e ej j關(guān)聯(lián)關(guān)聯(lián)2 2次次, , 即即e ej j是以是以v vi i為端點(diǎn)的環(huán)為端點(diǎn)的環(huán)) )?例e2v4v2v3v1e3e4e1e500000210010111000111)(GM關(guān)聯(lián)矩陣M(G)的性質(zhì))(21的度數(shù)行元素之和為第）（iimjijvivdm 每條邊關(guān)聯(lián)兩個(gè)頂點(diǎn)。中，這說明）（)(),.,2 , 1(211GMmjmniij)( )(2311111握手定理）（niimjijniniijmjvdmmm為孤立點(diǎn)。，當(dāng)且僅當(dāng)）（imjijvm041為平行邊。與列相同，則說明列與第）若第（kjeekj5有向圖的關(guān)聯(lián)矩陣

21、 要求有向圖D中無環(huán)存在. 設(shè)D,Vv1,v2,vn, Ee1,e2,em,令 則稱(mij)nm為D的關(guān)聯(lián)矩陣，記作M(D).的終點(diǎn)為不關(guān)聯(lián)與的始點(diǎn)為jijijiijevevevm1 , 0, 1v4v3v2v1e1e2e3e4e5?例01110100001110100011)(DM.1)()(1).(1),(1211111111mjijniniiniimjijniimjijimjijmvdmvdmvdmvdm）（）（從而有）（）（）（. 0),.,2 , 1(01111niijmjniijmmjm，從而）（關(guān)聯(lián)矩陣M(D)的性質(zhì)有向圖的鄰接矩陣 設(shè)有向圖D. V=v1,v2,vn, |E|

22、m. 令aij (1) 為vi鄰接到鄰接到vj的邊的條數(shù),稱(aij (1) mn為D的鄰接矩陣,記作A(D).v4v3v2v1?例0100100001000121)(AD(1)(1)1111(2)( ),( )nnnnijjijjijiiad vad vm(1)(1)1111(1)( ),( )nnnnijiijijijiadvadvm鄰接矩陣A(D)的性質(zhì)(3) 為D中邊的總數(shù),也可看成D中長(zhǎng)度為1的通路總數(shù),而 為D中環(huán)的個(gè)數(shù),即D中長(zhǎng)度為1的回路總數(shù). (1)11nnijija (1)1niiia 考慮Al(D)(簡(jiǎn)記Al), = 這里Al=( )nn(l 2), 則 為頂點(diǎn)vi到vj

23、長(zhǎng)度為l的通路數(shù), 為它到自身長(zhǎng)度為l的回路數(shù).Al中所有元素之和 為D中長(zhǎng)度為l的通路數(shù),而Al中對(duì)角線上元素之和 為D中始于(終于)各頂點(diǎn)的長(zhǎng)度為l的回路數(shù).()lija( ) lija(1)(1).likkjkaa()lija()liia( ),liji ja( ) liiia 在圖中,計(jì)算A2,A3,A4如下:1000010010001321A21000010010004621A40100100001003421A3v4v3v2v10100100001000121)(ADJ定理7.5 設(shè)A為有向圖D的鄰接矩陣,V=v1,v2,vn,則Al(l1)中元素 為vi到vj長(zhǎng)度為l的通路數(shù),

24、為D中長(zhǎng)度為l的通路總數(shù),其中 為D中長(zhǎng)度為l的回路數(shù).()lija( ),liji ja( ) liiiaJ推論 設(shè)Br=A+A2+Ar(r1),則Br中元素 為D中vi到vj長(zhǎng)度小于等于r的通路數(shù), 為D中長(zhǎng)度小于等于r的通路總數(shù),其中 為D中長(zhǎng)度小于等于r的回路總數(shù).( )rijb( ),riji jb( )riiib若再令矩陣 B1=A, B2=A+A2, Br=A+A2+Ar,有向圖的可達(dá)矩陣 設(shè)D=為一有向, V=v1,v2,vn,令 pii=1,i=1,2,n. 稱(pij)nn為D的可達(dá)矩陣,記作P(D),簡(jiǎn)記P.jivvpjiij否則可達(dá)011111011101110011v

25、4v3v2v1P=?例 P中元素可如下確定: 于是由D的鄰接矩陣可求可達(dá)矩陣.jibpnijij否則，001)1(. 1ijp7.4 最短路徑及關(guān)鍵路徑 1.最短路徑問題 2.關(guān)鍵路徑問題權(quán)、帶權(quán)圖 對(duì)于有向圖或無向圖G的每條邊附加一個(gè)實(shí)數(shù)w(e)，則稱w(e)為邊e上的權(quán). G連同附加在各邊上的實(shí)數(shù)稱為帶權(quán)圖.常記帶權(quán)圖為G=.設(shè)G1是帶權(quán)圖G的子圖,稱 為G1的權(quán),記作W(G1).當(dāng)然,W(G)是G的權(quán).當(dāng)無向邊e=(vi,vj)或有向邊e=時(shí),w(e)也記為wij.(1)( )e E Gw eE(G1)最短路徑問題 設(shè)帶權(quán)圖G=. G中每條邊帶的權(quán)均大于等于0.u,v為G中任意兩個(gè)頂點(diǎn),

26、從u到v的所有通路中帶權(quán)最小的通路稱為u到v的最短路徑.n設(shè)G=是n階簡(jiǎn)單帶權(quán)圖,wij0.若頂點(diǎn)vi與vj不相鄰,令wij=.求G中頂點(diǎn)v1到其余各頂點(diǎn)的最短路徑. 路徑長(zhǎng)度的的具體含義取決于邊上權(quán)值所代表的意義。【例】交通網(wǎng)絡(luò)中的帶權(quán)圖求最短路徑的問題。（1）兩地之間是否有路相通?（2）在有多條通路的情況下，哪一條最短?其中，交通網(wǎng)絡(luò)可以用帶權(quán)圖表示：圖中頂點(diǎn)表示城鎮(zhèn)，邊表示兩個(gè)城鎮(zhèn)之間的道路，邊上的權(quán)值可表示兩城鎮(zhèn)間的距離，交通費(fèi)用或途中所需的時(shí)間等等。(1)設(shè) 為頂點(diǎn)v1到頂點(diǎn)vi最短路徑的權(quán),若頂點(diǎn)vi獲得了標(biāo)號(hào) ,稱vi在第r步獲得了p標(biāo)號(hào) (永久性標(biāo)號(hào)),其中,r0.(2)設(shè) 為

27、v1到vj的最短路徑權(quán)的上界,若vj獲得 ,在第r步獲得t標(biāo)號(hào) (臨時(shí)性標(biāo)號(hào)),r0.( )*ril( )*ril( )*ril( )rjl( )rjl( )rjl若干定義：(3)設(shè)Pr=v|v已獲得p標(biāo)號(hào)為第r步通過集,r0.(4)設(shè)Tr=V-Pr為第r步未通過集,r0.Dijkstra(標(biāo)號(hào)法）的算法： 開始,r0,v1獲p標(biāo)號(hào): =0,P0=v1,T0=V-v1.vj(j1)的t標(biāo)號(hào): =w1j. 求下一個(gè)p標(biāo)號(hào)頂點(diǎn). 設(shè) ,將 標(biāo)在相應(yīng)頂點(diǎn)vi處,表明vi獲得p標(biāo)號(hào).修改通過集和未通過集: Pr=Pr-1vi,Tr=Tr-1-vi. , 查Tr:若Tr=,則算法結(jié)束,否則轉(zhuǎn).(0)*1

28、l( )*ril1( )*(1)minjrrrijvTll(0)jl 修改Tr中各頂點(diǎn)的t標(biāo)號(hào): 是剛剛獲得標(biāo)號(hào)頂點(diǎn)的p標(biāo)號(hào).令rr+1,轉(zhuǎn).( )(1)( )*( )*min,rrrrjjiijilllwl 求圖中頂點(diǎn)v0與v5的最短路徑. ?例解 :可以將計(jì)算過程用一張表表示出來(見下頁表)31v5v3v2v154712v02v4631v5v3v2v154712v0 2v46 vi K v0v1v2v3v4v5012345011/v0433/v18877/v4644/v2 1099/v3013749 由表可知,v5與v3相鄰,v3與v4相鄰,v4與v2相鄰,v2與v1相鄰,v1與v0相鄰.

29、這樣從v5往前追蹤,得v0到v5的最短路徑為 =v0v1v2v4v3v5. W()=9. 31v5v3v2v154712v02v46設(shè)D=為一個(gè)有向圖,vV,稱為v的后繼元集;為v的先驅(qū)元集.2.關(guān)鍵路徑問題,|)(ExvVxxvD,|)(EvxVxxvD（1）PERT圖（計(jì)劃評(píng)審技術(shù)圖）設(shè)D=是n階有向帶權(quán)圖,滿足:1)D是簡(jiǎn)單圖;2)D中無回路;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圖.通常把計(jì)劃、施工過程、生產(chǎn)流程、程序流程的都當(dāng)成一個(gè)工程。除了很小的工程外、一般都把工程分為若干個(gè)叫做“活動(dòng)”的

30、子工程。完成了這些“活動(dòng)”的子工程，這個(gè)工程就可以完成了。 通常我們用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊 表示活動(dòng)vi必須先于活動(dòng)vj進(jìn)行。 這種的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱AOE（active on edges）網(wǎng)絡(luò)。 AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。他可以使人們了解： （1）：研究某個(gè)工程至少需要多少時(shí)間？ （2）：那些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？在AOE網(wǎng)絡(luò)中，有些活動(dòng)可以并行的進(jìn)行。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活動(dòng)都完成了，這個(gè)工程才算完成。因此，完成整個(gè)工程所需的時(shí)間取決于從發(fā)點(diǎn)到收點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即在這條路徑上所

31、有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度就叫做關(guān)鍵路徑（critical path）。 1956年，美國(guó)杜邦公司提出關(guān)鍵路徑法，并于1957年首先用于1000萬美圓化工廠建設(shè)，工期比原計(jì)劃縮短了4個(gè)月。杜邦公司在采用關(guān)鍵路徑法的一年中，節(jié)省了100萬美圓。案例 自發(fā)點(diǎn)(記為v1)開始沿最長(zhǎng)路徑到達(dá)vi所需要的時(shí)間,稱為vi的最早完成時(shí)間,記作 TE(vi),i=1,2,n. vi(i1)的最早完成時(shí)間可按如下公式計(jì)算: 收點(diǎn)vn的最早完成時(shí)間TE(vn)就是從v1到vn的最長(zhǎng)路徑的權(quán).（2）最早完成時(shí)間niwvTEvTEijjvviiDj,.,3 , 2,)(max)()( 在保證收點(diǎn)vn的最早完成

32、時(shí)間不增加的條件下,自v1最遲到達(dá)vi的時(shí)間稱為vi的最晚完成時(shí)間,記作TL(vi). TL(vn)=TE(vn).in時(shí),vi的最晚完成時(shí)間由下面公式計(jì)算: （3）最晚完成時(shí)間1,.,2 , 1,)(min)()(niwvTLvTLijjvviiDj 稱TL(vi)-TE(vi)為vi的緩沖時(shí)間,記作 ES(vi)=TL(vi)-TE(vi) i=1,2,n 在關(guān)鍵路徑上各頂點(diǎn)的緩沖時(shí)間均為0.（4）緩沖時(shí)間 求所示PERT圖中各頂點(diǎn)的最早、最晚和緩沖時(shí)間以及關(guān)鍵路徑.31v5v3v4v234416v12v60v8v71442?例解 (1)各頂點(diǎn)的最早完成時(shí)間: TE(v1)=0; TE(v

33、2)=max0+1=1; TE(v3)=max0+2,1+0=2; TE(v4)=max0+3,2+2=4; TE(v5)=max1+3,4+4=8; TE(v6)=max2+4,8+1=9; TE(v7)=max1+4,2+4=6; TE(v8)=max9+1,6+6=12.31v5v3v4v234416v12v60v8v71442(2)各頂點(diǎn)的最晚完成時(shí)間: TL(v8)=12; TL(v7)=min12-6=6; TL(v6)=min12-1=11; TL(v5)=min11-1=10; TL(v4)=min10-4=6; TL(v3)=min6-2,11-4,6-4=2; TL(v2)=min2-0,10-3,6-4=2; TL(v1)=min2-1,2-2,6-3=031v5v3v4v234416v12v60v8v714423)各頂點(diǎn)的緩沖時(shí)間:T