第七章 圖的基本概念.

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

2、的聯(lián)結關系。目 錄7.1 無向圖及有向圖7.2 通路、回路、圖的連通性7.3 圖的矩陣表示7.4 最短路徑問題及關鍵路徑 7.1 無向圖及有向圖無向圖及有向圖設A,B為兩集合,稱 a,baAbB為A與B的無序積,記作AB將無序對a,b記作(a,b).J定義7.1 一個無向圖G是一個二元組,即 G,其中, (1)V是一個非空的集合,稱為G的頂點集,V中元素稱為頂點或結點； (2)E是無序積VV的一個多重子集,稱E為G的邊集,E中元素稱為無向邊或簡稱邊.無向圖元素可重復出現(xiàn)的集合為元素可重復出現(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 一個有向圖D是一個二元組,即 D,其中, (1)V同無向圖中的頂點集； (2)E是卡氏積的多重子集,其元素稱為有向邊,也簡稱邊.有時用V(D),E(D)分別表示圖D的頂點集和邊集。例如： D=,V=v1, v2, v3, v4, v5, E= , ,G的圖形為：e5v5v4v3v2v1e4e3e2e1e6e7e8 設G為一無向圖或有向圖 (1)若V,E都是有窮集合,則稱G是有限圖. (2)若Vn,則稱G為n階圖 (3)若E,則

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

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

6、點的次數之和,為vj的出度,記作d+(vj)； 稱vj作為邊的終點的次數之和,為vj的入度,記作d-(vj)； 稱vj作為邊的端點的次數之和,為vj的度數,簡稱度,記作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是懸掛結點，為懸掛邊。?例v5v1v2v3v4對于圖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（握手定理） 設圖G為無向圖或有向圖,Vv1,v2,.,vn,|E|=m(m為邊數),則J推論 任何圖(無向的或有向的)中,度為奇數的頂點個數為偶數.mvdnii2)(1J定理7.2設有向圖D,Vv1,v2,.,vn,Em,則 設Vv1,v2,.,vn為圖G的頂點集,稱(d(v1),d(v2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、l( )*ril1( )*(1)minjrrrijvTll(0)jl 修改Tr中各頂點的t標號: 是剛剛獲得標號頂點的p標號.令rr+1,轉.( )(1)( )*( )*min,rrrrjjiijilllwl 求圖中頂點v0與v5的最短路徑. ?例解 :可以將計算過程用一張表表示出來(見下頁表)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設D=為一個有向圖,vV,稱為v的后繼元集;為v的先驅元集.2.關鍵路徑問題,|)(ExvVxxvD,|)(EvxVxxvD（1）PERT圖（計劃評審技術圖）設D=是n階有向帶權圖,滿足:1)D是簡單圖;2)D中無回路;3)有一個頂點入度為0,稱此頂點為發(fā)點; 有一個頂點出度為0,稱此頂點為收點;4)記邊帶的權為wij;它常表示時間;則稱D為PERT圖.通常把計劃、施工過程、生產流程、程序流程的都當成一個工程。除了很小的工程外、一般都把工程分為若干個叫做“活動”的

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

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

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