第七圖的基本概念演示文稿

第七圖的基本概念演示文稿當(dāng)前1頁，總共102頁。優(yōu)選第七圖的基本概念當(dāng)前2頁，總共102頁。圖論的內(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)的位置、邊的長短和形狀,只關(guān)心頂點(diǎn)與邊的聯(lián)結(jié)關(guān)系。當(dāng)前3頁，總共102頁。目錄7.1無向圖及有向圖7.2通路、回路、圖的連通性7.3圖的矩陣表示7.4最短路徑問題及關(guān)鍵路徑

當(dāng)前4頁，總共102頁。7.1無向圖及有向圖設(shè)A,B為兩集合,稱

{{a,b}｜a∈A∧b∈B}為A與B的無序積,記作A＆B．將無序?qū)a,b}記作(a,b).當(dāng)前5頁，總共102頁。定義7.1

一個(gè)無向圖G是一個(gè)二元組<V,E>,即G＝<V,E>,其中,(1)V是一個(gè)非空的集合,稱為G的頂點(diǎn)集,V中元素稱為頂點(diǎn)或結(jié)點(diǎn)；

(2)E是無序積V＆V的一個(gè)多重子集,稱E為G的邊集,E中元素稱為無向邊或簡稱邊.無向圖元素可重復(fù)出現(xiàn)的集合為多重集當(dāng)前6頁，總共102頁。例如：G=<V,E>,V={v1,v2,v3,v4,v5},E={(v1,v2),(v2,v2),(v2,v3),(v1,v3),(v1,v3),(v1,v4)}G的圖形為：e5v5v4v3v2v1e4e3e2e1e6當(dāng)前7頁，總共102頁。有向圖定義7.2一個(gè)有向圖D是一個(gè)二元組<V,E>,即D＝<V,E>,其中,(1)V同無向圖中的頂點(diǎn)集；

(2)E是卡氏積的多重子集,其元素稱為有向邊,也簡稱邊.有時(shí)用V(D),E(D)分別表示圖D的頂點(diǎn)集和邊集。當(dāng)前8頁，總共102頁。例如：D=<V,E>,V={v1,v2,v3,v4,v5},E={<v1,v1>,<v3,v2>,<v3,v2>,<v3,v4>,<v2,v4>,<v4,v5>,<v5,v4>,<v1,v2>}G的圖形為：e5v5v4v3v2v1e4e3e2e1e6e7e8當(dāng)前9頁，總共102頁。設(shè)G＝<V,E>為一無向圖或有向圖

(1)若V,E都是有窮集合,則稱G是有限圖.(2)若｜V｜＝n,則稱G為n階圖．

(3)若E＝,則稱G為零圖．特別是,若此時(shí)又有｜V｜＝1,則稱G為平凡圖.5階圖零圖平凡圖當(dāng)前10頁，總共102頁。定義7.3設(shè)ek＝(vi,vj)為無向圖G＝<V,E>中的一條邊,稱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).e5v5v4v3v2v1e4e3e2e1e6當(dāng)前11頁，總共102頁。ek與vi(或vj)的關(guān)聯(lián)次數(shù)1vi(vj)是ek的端點(diǎn)且vi≠vj,2vi(vj)是ek的端點(diǎn)且vi＝vj,0vi(vj)不是ek的端點(diǎn)e5v5v4v3v2v1e4e3e2e1e6當(dāng)前12頁，總共102頁。定義7.4設(shè)無向圖G=<V,E>,vi,vj∈V,ek,el∈E.(1)若存在一條邊e以vi、vj為端點(diǎn),即e=(vi,vj),則稱vi,vj是彼此相鄰的,簡稱相鄰的．(2)若ek,el至少有一個(gè)公共端點(diǎn),則稱ek,el是彼此相鄰的,簡稱相鄰的．e5v5v4v3v2v1e4e3e2e1e6當(dāng)前13頁，總共102頁。對有向圖若ek＝〈vi,vj〉,除稱vi,vj是ek的端點(diǎn)外,還稱vi是ek的始點(diǎn),vj是ek的終點(diǎn),vi鄰接到vj,vj鄰接于vi.e5v5v4v3v2v1e4e3e2e1e6e7e8當(dāng)前14頁，總共102頁。定義7.5設(shè)G＝<V,E>為一無向圖,vi∈V,稱vi作為邊的端點(diǎn)的次數(shù)之和為vi的度數(shù),簡稱度,記作d(vi).稱度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn),它所對應(yīng)的邊為懸掛邊.v1v2v5v4v3d(vi)=?當(dāng)前15頁，總共102頁。設(shè)D＝<V,E>為一有向圖,vj∈V,稱vj作為邊的始點(diǎn)的次數(shù)之和,為vj的出度,記作d+(vj)；稱vj作為邊的終點(diǎn)的次數(shù)之和,為vj的入度,記作d-(vj)；稱vj作為邊的端點(diǎn)的次數(shù)之和,為vj的度數(shù),簡稱度,記作d(vj).顯然d(vj)＝d+(vj)＋d-(vj).當(dāng)前16頁，總共102頁。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)，<v1,v5>為懸掛邊。例v5v1v2v3v4當(dāng)前17頁，總共102頁。對于圖G＝<V,E>,記Δ(G)＝max{d(v)｜v∈V},(G)＝min{d(v)｜v∈V},分別稱為G的最大度和最小度.v1v2v5v4v3Δ＝4，＝0。當(dāng)前18頁，總共102頁。若D＝〈V,E〉是有向圖,除了Δ(D),(D)外,還有最大出度、最大入度、最小出度、最小入度,分別定義為v5v4v3v2v1當(dāng)前19頁，總共102頁。定理7.1（握手定理）設(shè)圖G＝<V,E>為無向圖或有向圖,V＝{v1,v2,...,vn},|E|=m(m為邊數(shù)),則推論任何圖(無向的或有向的)中,度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù).當(dāng)前20頁，總共102頁。定理7.2設(shè)有向圖D＝<V,E>,V＝{v1,v2,...,vn},｜E｜＝m,則設(shè)V＝{v1,v2,...,vn}為圖G的頂點(diǎn)集,稱(d(v1),d(v2),...,d(vn))為G的度數(shù)序列.當(dāng)前21頁，總共102頁。例v1v2v5v4v3度數(shù)序列（4，4，3，1，0）度數(shù)序列（3，4，3，4，2）v5v4v3v2v1當(dāng)前22頁，總共102頁。

(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)。例當(dāng)前23頁，總共102頁。定義7.6在無向圖中,關(guān)聯(lián)一對頂點(diǎn)的無向邊如果多于1條,稱這些邊為平行邊.平行邊的條數(shù)稱為重?cái)?shù).在有向圖中,關(guān)聯(lián)一對頂點(diǎn)的有向邊如果多于1條,且它們的始點(diǎn)與終點(diǎn)相同,則稱這些邊為有向平行邊,簡稱平行邊.含平行邊的圖稱為多重圖.既不含平行邊,也不含環(huán)的圖稱為簡單圖.當(dāng)前24頁，總共102頁。e5v5v4v3v2v1e4e3e2e1e6

e4與e5是平行邊

e3與e4是平行邊

e7與e8不是平行邊e5v5v4v3v2v1e4e3e2e1e6e7e8當(dāng)前25頁，總共102頁。定義7.7設(shè)G=<V,E>是n階無向簡單圖,若G中任何頂點(diǎn)都與其余的n-1個(gè)頂點(diǎn)相鄰,則稱G為n階無向完全圖,記作Kn.

設(shè)D=<V,E>為n階有向簡單圖,若對于任意的頂點(diǎn)u,v∈V(u≠v),既有有向邊<u,v>,又有<v,u>,則稱D是n階有向完全圖.注：Kn均指無向完全圖.當(dāng)前26頁，總共102頁。圖(1)中所示為K4,(2)所示為K5,(3)所示為3階有向完全圖.例(1)(2)(3)當(dāng)前27頁，總共102頁。定義7.8設(shè)G=<V,E>,G'=<V',E'>是兩個(gè)圖.若V'V,且E'E,則稱G'是G的子圖,G是G'的母圖,記做G'G.若G'G且G'≠G(即V'V或E'E),則G'是G的真子圖.當(dāng)前28頁，總共102頁。若G'G且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)出子圖.當(dāng)前29頁，總共102頁。例下圖給出了圖G以及它的真子圖G'和生成子圖G''。G'是結(jié)點(diǎn)集{v1,v2,v4,v5,v6}的導(dǎo)出子圖。當(dāng)前30頁，總共102頁。v1v2v3v4e4e5e1e2e3v1v2v3v4e4e1e3v1v2e4e5v1

v2v3e4e1e2e3v1

v2v3e1e3v1v2e1例(1)(2)(3)(6)(5)(4)當(dāng)前31頁，總共102頁。定義7.9設(shè)G=<V,E>是n階無向簡單圖.以V為頂點(diǎn)集,以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對于完全圖Kn的補(bǔ)圖,簡稱G的補(bǔ)圖,記作G.

有向簡單圖的補(bǔ)圖可類似定義.當(dāng)前32頁，總共102頁。例互補(bǔ)互補(bǔ)當(dāng)前33頁，總共102頁。觀察下列圖有何特點(diǎn)？圖(a)、圖(b)、圖(c)和圖(d)所表示的圖形實(shí)際上都是一樣的。bdcdcbadcbadcbaa圖(a)圖(b)圖(c)圖(d)當(dāng)前34頁，總共102頁。定義7.10設(shè)兩個(gè)無向圖G1=<V1,E1>,G2=<V2,E2>,如果存在雙射函數(shù)：V1→V2,使得對于任意的e=(vi,vj)∈E1當(dāng)且僅當(dāng)e'=((vi),(vj))∈E2,并且e與e'的重?cái)?shù)相同,則稱G1與G2是同構(gòu)的,記作G1≌G2.當(dāng)前35頁，總共102頁。(1)≌(2),頂點(diǎn)之間的對應(yīng)關(guān)系為av1,bv2,cv3,dv4,ev5.當(dāng)前36頁，總共102頁。(a)≌(b)≌(c)(a)所示圖稱為彼德森圖.(a)(b)(c)1、頂點(diǎn)個(gè)數(shù)相同2、邊的條數(shù)相同3、度數(shù)相同的結(jié)點(diǎn)數(shù)相同兩圖同構(gòu)當(dāng)前37頁，總共102頁。例(1)畫出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無向簡單圖；

(1)(2)(3)當(dāng)前38頁，總共102頁。(2)畫出3個(gè)頂點(diǎn)2條邊的所有可能非同構(gòu)的有向簡單圖.(1)(2)(3)(4)當(dāng)前39頁，總共102頁。7.2通路、回路、圖的連通性定義7.11給定圖G＝<V,E>.設(shè)G中頂點(diǎn)和邊的交替序列為Γ＝v0e1v1e2…elvl,若Γ滿足如下條件:vi-1和vi是ei的端點(diǎn)(在G是有向圖時(shí),要求vi-1是ei的始點(diǎn),vi是ei的終點(diǎn)),i＝1,2,…,l,則稱Γ為頂點(diǎn)v0到vl的通路.v0和vl分別稱為此通路的起點(diǎn)和終點(diǎn),Γ中邊的數(shù)目l稱為Γ的長度.

當(dāng)v0＝vl時(shí),此通路稱為回路.當(dāng)前40頁，總共102頁。若Γ中的所有邊e1,e2,···,el互不相同,則稱Γ為簡單通路或一條跡.若回路中的所有邊互不相同,稱此回路為簡單回路或一條閉跡.若通路的所有頂點(diǎn)v0,v1···,vl互不相同(從而所有邊互不相同),則稱此通路為初級通路或一條路徑.若回路中,除v0＝vl外,其余頂點(diǎn)各不相同,所有邊也各不相同,則稱此回路為初級回路或圈.當(dāng)前41頁，總共102頁。有邊重復(fù)出現(xiàn)的通路稱為復(fù)雜通路,有邊重復(fù)出現(xiàn)的回路稱為復(fù)雜回路.由定義可知,初級通路(回路)是簡單通路(回路),但反之不真.注：上述定義既適合無向圖，也適合有向圖。當(dāng)前42頁，總共102頁。例v1v0v4v2v3v5v8v6v7v1v0v4v2v3v1v0v4v2v3v1v0v4v2v3v5v8v6v7(1)為v0到v4的長為4的初級通路(2)為v0到v4的長為4的初級通路(3)為v0到v8的長為8的簡單通路(4)為v0到v8的長為8的簡單通路當(dāng)前43頁，總共102頁。定理7.3在一個(gè)n階圖中,若從頂點(diǎn)vi到vj(vi≠vj)存在通路,則從vi到vj存在長度小于等于n-1的通路.推論在一個(gè)n階圖中,若從頂點(diǎn)vi到vj(vi≠vj)存在通路,則從vi到vj存在長度小于等于n-1的初級通路.當(dāng)前44頁，總共102頁。定理7.4在一個(gè)n階圖中,如果存在vi到自身的回路,則從vi到自身存在長度小于等于n的回路.推論在一個(gè)n階圖中,如果vi到自身存在一條簡單回路,則從vi到自身存在長度小于等于n的初級回路.當(dāng)前45頁，總共102頁。定義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á)的.當(dāng)前46頁，總共102頁。短程線(無向圖)設(shè)vi,vj為無向圖G中的任意兩點(diǎn),若vi與vj是連通的,則稱vi與vj之間長度最短的通路為vi與vj之間的短程線,短程線的長度稱為vi與vj之間的距離,記作d(vi,vj).短程線(有向圖)設(shè)vi,vj為有向圖D中任意兩點(diǎn),若vi可達(dá)vj,則稱從vi到vj長度最短的通路為vi到vj的短程線,短程線的長度稱為vi到vj的距離,記作d<vi,vj>.當(dāng)前47頁，總共102頁。性質(zhì)若vi不可達(dá)vj,規(guī)定d<vi,vj>＝∞.d<vi,vj>具有下面性質(zhì):(1)d<vi,vj>

≥0,當(dāng)vi＝vj時(shí),等號成立.(2)滿足三角不等式,即

d<vi,vj>+d<vj,vk>≥d<vi,vk>.在無向圖中,還有對稱性,即

d(vi,vj)＝d(vj,vi).當(dāng)前48頁，總共102頁。連通圖(無向圖)定義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(k≥1)個(gè)等價(jià)類,記成V1,V2,···,Vk,由它們導(dǎo)出的導(dǎo)出子圖G[V1],G[V2],…,G[Vk]稱為G的連通分支,其個(gè)數(shù)記為p(G).當(dāng)前49頁，總共102頁。G1是連通圖，p(G1)＝1；G2是非連通圖，且p(G2)＝3。G1G2例當(dāng)前50頁，總共102頁。連通圖(有向圖)定義7.14設(shè)D是一個(gè)有向圖,如果略去D中各有向邊的方向后所得無向圖G是連通圖,則稱D是連通圖,或稱D是弱連通圖.若D中任意兩頂點(diǎn)至少一個(gè)可達(dá)另一個(gè),則稱D是單向連通圖.若D中任何一對頂點(diǎn)都是相互可達(dá)的,則稱D是強(qiáng)連通圖．當(dāng)前51頁，總共102頁。例圖a為弱連通圖；圖b為單向連通圖；圖c為強(qiáng)連通圖。圖a圖b圖c當(dāng)前52頁，總共102頁。定義7.15設(shè)無向圖G＝<V,E>,若存在頂點(diǎn)子集V'V,使G刪除V'將V'中頂點(diǎn)及其關(guān)聯(lián)的邊都刪除)后,所得子圖G－V'的連通分支數(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).當(dāng)前53頁，總共102頁。若存在邊集子集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為割邊或橋.當(dāng)前54頁，總共102頁。{v2,v7}，{v3}，{v4}為點(diǎn)割集，{v3}，{v4}為割點(diǎn){e1,e2}，{e1,e3,e4}，{e6}，{e7,e8}，{e2,e3,e4}等都是割集，其中e6是橋。v5e8v6v7v1v4v2v3e1e2e3e4e5e6e7e9例當(dāng)前55頁，總共102頁。本節(jié)概念:無向圖、有向圖、n階圖、零圖、平凡圖、彼此關(guān)聯(lián)、相鄰、度d(vi)、出度d+(vj)、入度d-(vj)、握手定理及其推論、度數(shù)序列、簡單圖、n階無向完全圖、子圖、母圖、生成子圖、導(dǎo)出子圖、補(bǔ)圖、同構(gòu)、通路、回路、連通圖、點(diǎn)割集、邊割集當(dāng)前56頁，總共102頁。7.3圖的矩陣表示

無向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣有向圖的鄰接矩陣有向圖的可達(dá)矩陣

當(dāng)前57頁，總共102頁。無向圖的關(guān)聯(lián)矩陣設(shè)無向圖G＝<V,E>,V＝{v1,v2,···,vn},E＝{e1,e2,···,em},令mij為頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù),則稱(mij)n×m為G的關(guān)聯(lián)矩陣,記為M(G)mij0(vi與ej無關(guān)),1(vi與ej關(guān)聯(lián)1次),

(vi與ej關(guān)聯(lián)2次,

即ej是以vi為端點(diǎn)的環(huán))．當(dāng)前58頁，總共102頁。例e2v4v2v3v1e3e4e1e5當(dāng)前59頁，總共102頁。關(guān)聯(lián)矩陣M(G)的性質(zhì)當(dāng)前60頁，總共102頁。當(dāng)前61頁，總共102頁。有向圖的關(guān)聯(lián)矩陣要求有向圖D中無環(huán)存在.設(shè)D＝<V,E>,V＝{v1,v2,···,vn},E＝{e1,e2,···em},令則稱(mij)n×m為D的關(guān)聯(lián)矩陣，記作M(D).當(dāng)前62頁，總共102頁。v4v3v2v1e1e2e3e4e5例當(dāng)前63頁，總共102頁。關(guān)聯(lián)矩陣M(D)的性質(zhì)當(dāng)前64頁，總共102頁。有向圖的鄰接矩陣設(shè)有向圖D＝<V,E>.V={v1,v2,···,vn},|E|＝m.令aij

(1)

為vi鄰接到vj的邊的條數(shù),稱(aij

(1))m×n為D的鄰接矩陣,記作A(D).當(dāng)前65頁，總共102頁。v4v3v2v1例當(dāng)前66頁，總共102頁。鄰接矩陣A(D)的性質(zhì)當(dāng)前67頁，總共102頁。(3)為D中邊的總數(shù),也可看成D中長度為1的通路總數(shù),而為D中環(huán)的個(gè)數(shù),即D中長度為1的回路總數(shù).

當(dāng)前68頁，總共102頁?？紤]Al(D)(簡記Al),=

這里Al=()n×n(l≥2),則為頂點(diǎn)vi到vj長度為l的通路數(shù),為它到自身長度為l的回路數(shù).Al中所有元素之和為D中長度為l的通路數(shù),而Al中對角線上元素之和為D中始于(終于)各頂點(diǎn)的長度為l的回路數(shù).當(dāng)前69頁，總共102頁。在圖中,計(jì)算A2,A3,A4如下:v4v3v2v1當(dāng)前70頁，總共102頁。定理7.5設(shè)A為有向圖D的鄰接矩陣,V=｛v1,v2…,vn},則Al(l≥1)中元素為vi到vj長度為l的通路數(shù),為D中長度為l的通路總數(shù),其中為D中長度為l的回路數(shù).當(dāng)前71頁，總共102頁。推論設(shè)Br=A+A2+…+Ar(r≥1),則Br中元素為D中vi到vj長度小于等于r的通路數(shù),為D中長度小于等于r的通路總數(shù),其中為D中長度小于等于r的回路總數(shù).若再令矩陣

B1=A,B2=A+A2,……Br=A+A2+…+Ar,當(dāng)前72頁，總共102頁。有向圖的可達(dá)矩陣

設(shè)D=<V,E>為一有向,V={v1,v2,…,vn},令

pii=1,i=1,2,…,n.稱(pij)n×n為D的可達(dá)矩陣,記作P(D),簡記P.當(dāng)前73頁，總共102頁。v4v3v2v1P=例當(dāng)前74頁，總共102頁。P中元素可如下確定:

于是由D的鄰接矩陣可求可達(dá)矩陣.當(dāng)前75頁，總共102頁。7.4最短路徑及關(guān)鍵路徑

1.最短路徑問題

2.關(guān)鍵路徑問題當(dāng)前76頁，總共102頁。權(quán)、帶權(quán)圖對于有向圖或無向圖G的每條邊附加一個(gè)實(shí)數(shù)w(e)，則稱w(e)為邊e上的權(quán).G連同附加在各邊上的實(shí)數(shù)稱為帶權(quán)圖.常記帶權(quán)圖為G=<V,E,W>.當(dāng)前77頁，總共102頁。設(shè)G1是帶權(quán)圖G的子圖,稱為G1的權(quán),記作W(G1).當(dāng)然,W(G)是G的權(quán).當(dāng)無向邊e=(vi,vj)或有向邊e=<vi,vj>時(shí),w(e)也記為wij.E(G1)當(dāng)前78頁，總共102頁。最短路徑問題

設(shè)帶權(quán)圖G=<V,E,W>.G中每條邊帶的權(quán)均大于等于0.u,v為G中任意兩個(gè)頂點(diǎn),從u到v的所有通路中帶權(quán)最小的通路稱為u到v的最短路徑.設(shè)G=<V,E,W>是n階簡單帶權(quán)圖,wij≥0.若頂點(diǎn)vi與vj不相鄰,令wij=∞.求G中頂點(diǎn)v1到其余各頂點(diǎn)的最短路徑.當(dāng)前79頁，總共102頁。路徑長度的的具體含義取決于邊上權(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í)間等等。

當(dāng)前80頁，總共102頁。當(dāng)前81頁，總共102頁。(1)設(shè)為頂點(diǎn)v1到頂點(diǎn)vi最短路徑的權(quán),若頂點(diǎn)vi獲得了標(biāo)號,稱vi在第r步獲得了p標(biāo)號(永久性標(biāo)號),其中,r≥0.

(2)設(shè)為v1到vj的最短路徑權(quán)的上界,若vj獲得,在第r步獲得t標(biāo)號(臨時(shí)性標(biāo)號),r≥0.若干定義：當(dāng)前82頁，總共102頁。(3)設(shè)Pr={v|v已獲得p標(biāo)號}為第r步通過集,r≥0.(4)設(shè)Tr=V-Pr為第r步未通過集,r≥0.當(dāng)前83頁，總共102頁。Dijkstra(標(biāo)號法）的算法：開始,r←0,v1獲p標(biāo)號:=0,P0={v1},T0=V-{v1}.vj(j≠1)的t標(biāo)號:=w1j.

①求下一個(gè)p標(biāo)號頂點(diǎn).

設(shè),將標(biāo)在相應(yīng)頂點(diǎn)vi處,表明vi獲得p標(biāo)號.修改通過集和未通過集:Pr=Pr-1∪{vi},Tr=Tr-1-{vi}.,

查Tr:若Tr=,則算法結(jié)束,否則轉(zhuǎn)②.當(dāng)前84頁，總共102頁。②修改Tr中各頂點(diǎn)的t標(biāo)號:

是剛剛獲得標(biāo)號頂點(diǎn)的p標(biāo)號.令r←r+1,轉(zhuǎn)①.當(dāng)前85頁，總共102頁。求圖中頂點(diǎn)v0與v5的最短路徑.

例解:可以將計(jì)算過程用一張表表示出來(見下頁表)31v5v3v2v154712v02v46當(dāng)前86頁，總共102頁。31v5v3v2v154712v0

2v46

vi

Kv0v1v2v3v4v5012345011/v0433/v1∞8877/v4∞644/v2∞∞

∞1099/v3013749當(dāng)前87頁，總共102頁。由表可知,v5與v3相鄰,v3與v4相鄰,v4與v2相鄰,v2與v1相鄰,v1與v0相鄰.這樣從v5往前追蹤,得v0到v5的最短路徑為

Γ=v0v1v2v4v3v5.W(Γ)=9.

31v5v3v2v154712v02v46當(dāng)前88頁，總共102頁。設(shè)D=<V,E>為一個(gè)有向圖,v∈V,稱為v的后繼元集;為v的先驅(qū)元集.2.關(guān)鍵路徑問題當(dāng)前89頁，總共102頁。（1）PERT圖（計(jì)劃評審技術(shù)圖）設(shè)D=<V,E>是n階有向帶權(quán)圖,滿足:1)D是簡單圖;2)D中無回路;3)有一個(gè)頂點(diǎn)入度為0,稱此頂點(diǎn)為發(fā)點(diǎn);有一個(gè)頂點(diǎn)出度為0,稱此頂點(diǎn)為收點(diǎn);4)記邊<vi,vj>帶的權(quán)為wij;它常表示時(shí)間;則稱D為PERT圖.當(dāng)前90頁，總共102頁。通常把計(jì)劃、施工過程、生產(chǎn)流程、程序流程的都當(dāng)成一個(gè)工程。除了很小的工程外、一般都把工程分為若干個(gè)叫做“活動”的子工程。完成了這些“活動”的子工程，這個(gè)工程就可以完成了。

通常我們用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動，用有向邊

<vi,vj>表示活動vi必須先于活動vj進(jìn)行。

這種的有向圖叫做用邊表示活動的網(wǎng)絡(luò)，簡稱AOE（activeonedges）網(wǎng)絡(luò)。

當(dāng)前91頁，總共102頁。AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。他可以使人們了解：

（1）：研究某個(gè)工程至少需要多少時(shí)間？

（2）：那些活動是影響工程進(jìn)度的關(guān)鍵？

在AOE網(wǎng)絡(luò)中，有些活動可以并行的進(jìn)行。完成不同路徑的活動所需的時(shí)間雖然不同，但只有各條路徑上所有活動都完成了，這個(gè)工程才算完成。因此，完成整個(gè)工程所需的時(shí)間取決于從發(fā)點(diǎn)到收點(diǎn)的最長路徑長度，即在這條路徑上所有活動的持續(xù)時(shí)間之和。這條路徑長度就叫做關(guān)鍵路徑（criticalpath）。當(dāng)前92頁，總共102頁。

1956年，美國杜邦公司提出關(guān)鍵路徑法，并于1957年首先用于1000萬美圓化工廠建設(shè)，工期比原計(jì)劃縮短了4個(gè)月。杜邦公司在采用關(guān)鍵路徑法的一年中，節(jié)省了100萬美圓。

案例當(dāng)前93頁，總共102頁。自發(fā)點(diǎn)(記為v1)開始沿最長路徑到達(dá)vi所需要的時(shí)間,稱為vi的最早完成時(shí)間,記作

TE(vi),i=1,2,…,n.vi(i≠1)的最早完成時(shí)間可按如下公式計(jì)算:

收點(diǎn)vn的最早完成時(shí)間TE(vn)就是從v1到vn的最長路徑的權(quán).（2）最早完成時(shí)間當(dāng)前94頁，總共102頁。在保證收點(diǎn)vn的最早完成時(shí)間不增加的條件下,自v1最遲到達(dá)vi的時(shí)間稱為vi的最晚完成時(shí)間,記作TL(vi).TL(vn)=TE(vn).i≠n時(shí),vi的最晚完成時(shí)間由下面公式計(jì)算:

（3）最晚完成時(shí)間當(dāng)前95頁，總共102頁。稱TL(vi)-TE(vi)為vi的緩沖時(shí)間,記作

ES(vi)=