運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析ppt課件

1、圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis)圖與網(wǎng)絡(luò)的根本知識(shí)圖與網(wǎng)絡(luò)的根本知識(shí)最短路問題最短路問題樹及最小樹問題樹及最小樹問題最大流問題最大流問題哥尼斯堡七橋問題哥尼斯堡七橋問題哥尼斯堡現(xiàn)名加里寧格勒是歐洲一個(gè)城哥尼斯堡現(xiàn)名加里寧格勒是歐洲一個(gè)城市，市，PregeiPregei河把該城分成兩部分，河中有兩個(gè)小河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問題：有沒有方法從某處當(dāng)時(shí)人們提出這樣的問題：有沒有方法從某處如如A A出發(fā)，經(jīng)過各橋一次且僅一次

2、最后回到出發(fā)，經(jīng)過各橋一次且僅一次最后回到原地呢？原地呢？BDACABCD哥尼斯堡七空橋哥尼斯堡七空橋一筆畫問題一筆畫問題引論引論 圖的用途圖的用途 某公司的 組織機(jī)構(gòu)設(shè)置圖總公司總公司分公司分公司工廠或工廠或辦事處辦事處一、一、 圖與網(wǎng)絡(luò)的根本知識(shí)圖與網(wǎng)絡(luò)的根本知識(shí)一、圖與網(wǎng)絡(luò)的根本概念一、圖與網(wǎng)絡(luò)的根本概念 EADCB 1、一個(gè)圖是由點(diǎn)和連線組成。連線可帶箭頭，也可、一個(gè)圖是由點(diǎn)和連線組成。連線可帶箭頭，也可不帶，前者叫弧，后者叫邊不帶，前者叫弧，后者叫邊v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例 654321,vvvvvvV ,10987654321eeeee

3、eeeeeE， ,211vve ,212vve ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve 圖圖1一個(gè)圖是由點(diǎn)集一個(gè)圖是由點(diǎn)集 和和 中元素的無序?qū)Φ囊粋€(gè)中元素的無序?qū)Φ囊粋€(gè)集合集合 構(gòu)成的二元組，記為構(gòu)成的二元組，記為G =(VG =(V，E )E )，其中，其中V V中的中的元素元素 叫做頂點(diǎn)，叫做頂點(diǎn)，V V表示圖表示圖G G 的點(diǎn)集合；的點(diǎn)集合；E E中的元素中的元素 叫做叫做邊，邊，E E 表示圖表示圖G G的邊集合。的邊集合。keE jvkeV jvV 2 2、不帶箭頭的連線叫做邊。假設(shè)一個(gè)圖是由

4、點(diǎn)和邊所構(gòu)成的，、不帶箭頭的連線叫做邊。假設(shè)一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，那么稱其為無向圖，記作那么稱其為無向圖，記作G = (VG = (V，E)E)，銜接點(diǎn)的邊記作，銜接點(diǎn)的邊記作vi , vjvi , vj，或者或者vj , vivj , vi。 3 3、假設(shè)點(diǎn)與點(diǎn)之間的連線有方向，稱為弧。假設(shè)一個(gè)圖是由、假設(shè)點(diǎn)與點(diǎn)之間的連線有方向，稱為弧。假設(shè)一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V, A)D=(V, A)，其中，其中V V 表示表示有向圖有向圖D D 的點(diǎn)集合，的點(diǎn)集合，A A 表示有向圖表示有向圖D D 的弧集合。一條方向從的弧集合

5、。一條方向從vivi指向指向vj vj 的弧，記作的弧，記作(vi , vj)(vi , vj)。v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 圖圖2 4 4、一條邊的兩個(gè)端點(diǎn)是一樣的、一條邊的兩個(gè)端點(diǎn)是一樣的, ,那么稱這條邊是環(huán)。那么稱這條邊是環(huán)。 5 5、假設(shè)兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱它們?yōu)?、假設(shè)兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱它

6、們?yōu)槎嘀剡?。多重邊?6 6、不含環(huán)和多重邊的圖稱為簡(jiǎn)單圖；有多重邊的圖稱、不含環(huán)和多重邊的圖稱為簡(jiǎn)單圖；有多重邊的圖稱為多重圖。為多重圖。 7、每一對(duì)頂點(diǎn)間都有邊相連的無向簡(jiǎn)單圖稱為完全圖。、每一對(duì)頂點(diǎn)間都有邊相連的無向簡(jiǎn)單圖稱為完全圖。 有向完全圖那么是指恣意兩個(gè)頂點(diǎn)之間有且僅有一條有向完全圖那么是指恣意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡(jiǎn)單圖。有向邊的簡(jiǎn)單圖。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 次為零的點(diǎn)稱為弧立點(diǎn)，次為次為零的點(diǎn)稱為弧立點(diǎn)，次為1 1的點(diǎn)稱為懸掛點(diǎn)。懸掛的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶點(diǎn)的關(guān)聯(lián)邊稱為懸掛

7、邊。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。數(shù)的點(diǎn)稱為偶點(diǎn)。 8 8、以點(diǎn)、以點(diǎn)v v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v v 的次，記作的次，記作 。)(vd圖中圖中 d(v1)= 4 d(v1)= 4，d(v6)= 4d(v6)= 4環(huán)計(jì)兩次環(huán)計(jì)兩次 定理定理1 1 一切頂點(diǎn)次數(shù)之和等于一切邊數(shù)的一切頂點(diǎn)次數(shù)之和等于一切邊數(shù)的2 2倍。倍。 定理定理2 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 一切頂點(diǎn)的入次之和等于一切頂點(diǎn)的出次之和。一切頂點(diǎn)的入次之和等于一切頂點(diǎn)的出次之和。 有向圖中，以有向圖中，以 vi vi 為始點(diǎn)的邊數(shù)稱為點(diǎn)為始點(diǎn)的邊數(shù)稱

8、為點(diǎn)vivi的出次，用的出次，用 表示表示 ；以；以 vi vi 為終點(diǎn)的邊數(shù)稱為點(diǎn)為終點(diǎn)的邊數(shù)稱為點(diǎn)vi vi 的入次，的入次，用用 表示；表示；vi vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次。點(diǎn)的出次和入次之和就是該點(diǎn)的次。)(ivd )(ivd v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖支撐子圖在實(shí)踐運(yùn)用中，給定圖中每條邊在實(shí)踐運(yùn)用中，給定圖中每條邊 ，對(duì)應(yīng)，對(duì)應(yīng)一個(gè)數(shù)一個(gè)數(shù) ，稱之為，稱之為 “權(quán)。通常把這種賦權(quán)的圖稱權(quán)。通常把

9、這種賦權(quán)的圖稱為網(wǎng)絡(luò)。為網(wǎng)絡(luò)。 ),(jivvjiw 10 10、由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列、由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。稱為鏈。 如如:v0 :v0 ，e1e1，v1v1，e2e2，v2v2，e3 e3 ，v3 ,vn-1 ,en v3 ,vn-1 ,en ，vnvn， e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10 11 11、圖中恣意兩點(diǎn)之間均至少有一條鏈相連，那么稱、圖中恣意兩點(diǎn)之間均至少有一條鏈相連，那么稱此圖為連通圖。此圖為連通圖。 其鏈長(zhǎng)為其鏈長(zhǎng)為 n n ，其中，其中 v0 v0 ，vn vn 分別稱為鏈的起點(diǎn)和終分別稱

10、為鏈的起點(diǎn)和終點(diǎn)點(diǎn) 。所含的點(diǎn)、邊均不一樣的鏈稱為初等鏈。起點(diǎn)和終。所含的點(diǎn)、邊均不一樣的鏈稱為初等鏈。起點(diǎn)和終點(diǎn)是同一個(gè)點(diǎn)的鏈稱為圈。點(diǎn)是同一個(gè)點(diǎn)的鏈稱為圈。二、二、 圖的矩陣表示圖的矩陣表示對(duì)于網(wǎng)絡(luò)賦權(quán)圖對(duì)于網(wǎng)絡(luò)賦權(quán)圖G=G=V V，E E，其中邊，其中邊有權(quán)有權(quán) ，構(gòu)造矩陣，構(gòu)造矩陣 ，其中：，其中：稱矩陣稱矩陣A A為網(wǎng)絡(luò)為網(wǎng)絡(luò)G G的權(quán)矩陣。的權(quán)矩陣。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(nnjiaA )( EvvEvvajijiji),(0),(1 設(shè)圖設(shè)圖G=G=V V，E E中頂點(diǎn)的個(gè)數(shù)為中頂點(diǎn)的個(gè)數(shù)為n n，構(gòu)造一個(gè)，構(gòu)造一個(gè)矩

11、陣矩陣 ，其中：，其中： 稱矩陣稱矩陣A A為網(wǎng)絡(luò)為網(wǎng)絡(luò)G G的鄰接矩陣。的鄰接矩陣。 654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例權(quán)矩陣為：權(quán)矩陣為：鄰接矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437654321654321 030303302004020576305020007204346040vvvvvvvvvvvvA 二、二、 樹及最小樹問題樹及最小樹問題 知有六個(gè)城市，它們之間知有六個(gè)城市，它們之間 要架設(shè)線，要求恣意兩個(gè)城要架設(shè)線，要求恣意兩個(gè)城市均可以相互通話，并且線的總長(zhǎng)度最

12、短。市均可以相互通話，并且線的總長(zhǎng)度最短。 v1v2v3v4v5v6 1 1、一個(gè)連通的無圈的無向圖叫做樹。、一個(gè)連通的無圈的無向圖叫做樹。 樹中次為樹中次為1 1的點(diǎn)稱為樹葉，次大于的點(diǎn)稱為樹葉，次大于1 1的點(diǎn)稱為分支點(diǎn)。的點(diǎn)稱為分支點(diǎn)。 樹樹 的性質(zhì)：的性質(zhì)： 1 1數(shù)必連通，但無回路圈。數(shù)必連通，但無回路圈。 2 2n n 個(gè)頂點(diǎn)的樹必有個(gè)頂點(diǎn)的樹必有n-1 n-1 條邊。條邊。 3 3樹樹 中恣意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈初中恣意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈初等鏈。等鏈。 4 4樹樹 連通，但去掉任一條邊，連通，但去掉任一條邊， 必變?yōu)椴贿B通。必變?yōu)椴贿B通。 5 5樹樹 無回路

13、圈，但不相鄰的兩個(gè)點(diǎn)之間加一條無回路圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路圈。邊，恰得到一個(gè)回路圈。v1v2v3v4v5v6 2 2、 假設(shè)圖假設(shè)圖G=(V , E )G=(V , E )的生成子圖是一個(gè)樹的生成子圖是一個(gè)樹, ,那么稱那么稱該樹該樹 是是G G 的一個(gè)生成樹支撐樹，或簡(jiǎn)稱為圖的一個(gè)生成樹支撐樹，或簡(jiǎn)稱為圖G G 的樹。的樹。圖圖G G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。弦。一個(gè)圖一個(gè)圖G G 有生成樹的充要條件是有生成樹的充要條件是G G 是連通圖。是連通圖。 v1v2v3v4v5v1v2v3v4v5一破圈

14、法：在圖中任選一個(gè)圈，從這個(gè)圈中去一破圈法：在圖中任選一個(gè)圈，從這個(gè)圈中去掉一條邊。在余下的圖中反復(fù)這個(gè)步驟，直到得到掉一條邊。在余下的圖中反復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。一不含圈的圖為止。用破圈法求出以下圖的一個(gè)生成樹。用破圈法求出以下圖的一個(gè)生成樹。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8二避圈法：開場(chǎng)選一條邊，以后每一步中，總從二避圈法：開場(chǎng)選一條邊，以后每一步中，總從未被選取的邊中選出一條與已選邊不構(gòu)成圈的邊，反未被選取的邊中選出一條與已選邊不構(gòu)成圈的邊，反復(fù)這個(gè)過程，直到不能

15、進(jìn)展為止。復(fù)這個(gè)過程，直到不能進(jìn)展為止。v1v2v3v4v5v6 v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5根據(jù)破圈法和避圈法兩種方式得到了根據(jù)破圈法和避圈法兩種方式得到了圖的兩個(gè)不同的生成樹，由此可以看到連圖的兩個(gè)不同的生成樹，由此可以看到連通圖的生成樹不是獨(dú)一的。通圖的生成樹不是獨(dú)一的。3 3、最小生成樹問題、最小生成樹問題 一棵生成樹一切樹枝上權(quán)的總和為這個(gè)生成樹一棵生成樹一切樹枝上權(quán)的總和為這個(gè)生成樹的權(quán)。具有最小權(quán)的生成樹，稱為最小生成樹。的權(quán)。具有最小權(quán)的生成樹，稱為最小生成樹。求賦權(quán)圖求賦權(quán)圖G G的最小支撐樹的方法也有兩種，的最小支撐樹的方

16、法也有兩種，“破破圈法和圈法和“避圈法。避圈法。 破圈法：在原圖中，破圈法：在原圖中，任選一個(gè)圈，從圈中任選一個(gè)圈，從圈中去掉權(quán)最大的一條邊。去掉權(quán)最大的一條邊。在余下的圖中反復(fù)這在余下的圖中反復(fù)這個(gè)步驟，直到得到一個(gè)步驟，直到得到一不含圈的圖為止。不含圈的圖為止。655172344v1v2v3v4v5v6總造價(jià)總造價(jià)=1+4+9+3+17+23=57=1+4+9+3+17+23=57v1v2v3v4v514231352 避圈法：開場(chǎng)選一條權(quán)最小的邊，以后每一避圈法：開場(chǎng)選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)盡能夠小，步中，總從未被選取的邊中選一條權(quán)盡能夠小，且與已選邊不構(gòu)

17、成圈的邊。且與已選邊不構(gòu)成圈的邊。 某六個(gè)城市之間的道路網(wǎng)如圖某六個(gè)城市之間的道路網(wǎng)如圖 所示，要求沿著知長(zhǎng)所示，要求沿著知長(zhǎng)度的道路結(jié)合六個(gè)城市的線網(wǎng)，使線的總長(zhǎng)度最短。度的道路結(jié)合六個(gè)城市的線網(wǎng)，使線的總長(zhǎng)度最短。 v1v2v3v4v5v66515723445v1v2v3v4v5v61234最短路的普通提法為：設(shè)最短路的普通提法為：設(shè) 為連通圖，為連通圖，圖中各邊圖中各邊 有權(quán)有權(quán) 表示表示 之間沒之間沒有邊，有邊， 為圖中恣意兩點(diǎn)，求一條路為圖中恣意兩點(diǎn)，求一條路 ，使它，使它從從 到到 的一切路中總權(quán)最短。即：的一切路中總權(quán)最短。即： 最最小。小。),(EVG j il jiltsvv

18、 , sv),(jivvjivv ,tv ),()(jivvjilL( (一一) )、狄克斯徹、狄克斯徹(Dijkstra)(Dijkstra)算法算法適用于適用于wij0wij0，給出了從，給出了從vsvs到恣意一個(gè)點(diǎn)到恣意一個(gè)點(diǎn)vjvj的最短的最短路。路。三三 、最短路問題、最短路問題算法步驟：算法步驟：1.1.給始點(diǎn)給始點(diǎn)vsvs以以P P標(biāo)號(hào)標(biāo)號(hào) ，這表示從，這表示從vsvs到到vsvs的的最短間隔為最短間隔為0 0，其他節(jié)點(diǎn)均給，其他節(jié)點(diǎn)均給T T標(biāo)號(hào)，標(biāo)號(hào)， 。2.2.設(shè)節(jié)點(diǎn)設(shè)節(jié)點(diǎn)vivi為剛得到為剛得到P P標(biāo)號(hào)的點(diǎn)，思索點(diǎn)標(biāo)號(hào)的點(diǎn)，思索點(diǎn)vjvj，其中，其中 ，且，且vjvj為

19、為T T標(biāo)號(hào)。對(duì)標(biāo)號(hào)。對(duì)vjvj的的T T標(biāo)號(hào)進(jìn)展如下修標(biāo)號(hào)進(jìn)展如下修正：正：3.3.比較一切具有比較一切具有T T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為P P標(biāo)標(biāo)號(hào)，即：號(hào)，即：當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P P標(biāo)號(hào)。假標(biāo)號(hào)。假設(shè)全部節(jié)點(diǎn)均為設(shè)全部節(jié)點(diǎn)均為P P標(biāo)號(hào)那么停頓，否那么用標(biāo)號(hào)那么停頓，否那么用 替代替代vivi，前往步驟，前往步驟2 2。0)( svP )(ivTEvvji ),()(, )(min)(ijijjlvPvTvT )(min)(iivTvP iv例一：用例一：用DijkstraDijkstra算法求以下圖從算法求以下

20、圖從v1v1到到v6v6的最短的最短路。路。 v1v2v3v4v6v5352242421 解：解：1首先給首先給v1以以P標(biāo)號(hào)，給其他一切點(diǎn)標(biāo)號(hào)，給其他一切點(diǎn)T標(biāo)號(hào)。標(biāo)號(hào)。0)(1 vP)6,3,2()( ivTi2 23 3330,min)(, )(min)(12122 lvPvTvT550,min)(, )(min)(13133 lvPvTvT3)(2 vP4 4413,5min)(, )(min)(23233 lvPvTvT523,min)(, )(min)(24244 lvPvTvT523,min)(, )(min)(25255 lvPvTvT4)(3 vP5 56 6544,5min

21、)(, )(min)(35355lvPvTvT5)(4 vP5)(5 vP945,min)(, )(min)(46466 lvPvTvT725,min)(, )(min)(56566 lvPvTvT7)(6 vP7 78 89 91010反向追蹤得反向追蹤得v1v1到到v6v6的最短路為：的最短路為：6521vvvvv1v2v3v4v6v5352242421二、逐次逼近法二、逐次逼近法首先設(shè)任一點(diǎn)首先設(shè)任一點(diǎn)vivi到任一點(diǎn)到任一點(diǎn)vjvj都有一條弧。都有一條弧。顯然，從顯然，從v1v1到到vjvj的最短路是從的最短路是從v1v1出發(fā)，沿著這條路到出發(fā)，沿著這條路到某個(gè)點(diǎn)某個(gè)點(diǎn)vivi再沿弧再

22、沿弧(vi,vj)(vi,vj)到到vjvj。那么。那么v1v1到到vivi的這條路的這條路必然也是必然也是v1v1到到vivi的一切路中的最短路。設(shè)的一切路中的最短路。設(shè)P1jP1j表示從表示從v1v1到到vjvj的最短路長(zhǎng)，的最短路長(zhǎng)，P1iP1i表示從表示從v1v1到到vivi的最短路長(zhǎng)，的最短路長(zhǎng)，那么有以下方程：那么有以下方程： 開場(chǎng)時(shí)，令開場(chǎng)時(shí)，令 即用即用v1v1到到vjvj的直接間隔做初始解。的直接間隔做初始解。min11jiiijlPP ),2,1(1)1(1njlPjj 從第二步起，運(yùn)用遞推公式：求 ，當(dāng)進(jìn)展到第t步，假設(shè)出現(xiàn)那么停頓計(jì)算， 即為v1到各點(diǎn)的最短路長(zhǎng)。）（n

23、klPPjikiikj,3,2min)1(1)(1 )(1kjP）（njPPtjtj,2,1)1(1)(1 ）（njPtj,2,1)(1 例二、例二、 18v1v2v3v4v52635135211211v6v7v83766 0-5 -3 v8-5-55 0 -1 v7-1-1-1 7101 v6-3-31 0 -1 v5-7-7-73 2 0 8v4-2-2-2-2 1 -50-3 v3-5-5-5-1 2 06v20000 3-2-10v1P(4)P(3)P(2)P(1)v8v7v6v5v4v3v2v1求圖中求圖中v1v1到到各點(diǎn)的最短路各點(diǎn)的最短路 18v1v2v3v4v526351352

24、11211v6v7v8370，0 v3 ，-5 v1 ，-2 v3 ，-7 v2 ，-3 v4 ，-5 v3 ，-1 v6 ，6例、求：例、求：5 5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5 5年內(nèi)的總費(fèi)用最年內(nèi)的總費(fèi)用最小。小。 第第i i年度年度 1 2 3 4 1 2 3 4 5 5購(gòu)置費(fèi)購(gòu)置費(fèi) 11 11 12 12 13設(shè)備役齡設(shè)備役齡0-1 1-2 2-3 3-4 4-5維修費(fèi)用維修費(fèi)用 5 6 8 11 5 6 8 11 1818解：解：1分析：可行的購(gòu)置方案更新方案是分析：可行的購(gòu)置方案更新方案是很多的，很多的， 如：如： 1 每年購(gòu)置一臺(tái)新的，那么對(duì)應(yīng)的費(fèi)用

25、為：每年購(gòu)置一臺(tái)新的，那么對(duì)應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購(gòu)置新的，不斷用到第五年年底，第一年購(gòu)置新的，不斷用到第五年年底，那么總費(fèi)用為：那么總費(fèi)用為： 11+5+6+8+11+18 = 59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。 2 2方法：將此問題用一個(gè)賦權(quán)有向圖來描畫，然后求方法：將此問題用一個(gè)賦權(quán)有向圖來描畫，然后求這個(gè)賦權(quán)有向圖的最短路。這個(gè)賦權(quán)有向圖的最短路。 求解步驟：求解步驟： 1 1畫賦權(quán)有向圖：畫賦權(quán)有向圖： 設(shè)設(shè) Vi Vi 表示第表示第i i年初，年初，(Vi ,Vj )(Vi ,Vj )

26、表示第表示第i i 年初購(gòu)買年初購(gòu)買新設(shè)備用到第新設(shè)備用到第j j年初年初j-1j-1年底，而年底，而Wi j Wi j 表示相應(yīng)費(fèi)表示相應(yīng)費(fèi)用，那么用，那么5 5年的一個(gè)更新方案相當(dāng)于從年的一個(gè)更新方案相當(dāng)于從V1 V1 到到V6V6的一條路。的一條路。 2 2求解求解 標(biāo)號(hào)法標(biāo)號(hào)法 W12 =11+5=16W13 =11+5+6=22W14 =11+5+6+8=30W15 =11+5+6+8+11=41W16 =11+5+6+8+11+18=59 W23 =11+5=16 W24 =11+5+6=22W 2 5 = 1 1 + 5 + 6 + 8 = 3 0 W 2 6 =11+5+6+8

27、+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31 四、四、 最大流問題最大流問題一一 根本概念根本概念1、設(shè)一個(gè)賦權(quán)有向圖、設(shè)一個(gè)賦權(quán)有向圖G=V, E,在在V中指定一中指定一個(gè)發(fā)點(diǎn)個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)和一個(gè)收點(diǎn)vt ,其它的點(diǎn)叫做中間點(diǎn)。對(duì)其它的點(diǎn)叫做中間點(diǎn)。對(duì)于于D中的每一個(gè)弧中的每一個(gè)弧vi , vjE ,都有一個(gè)非負(fù)數(shù)都有一個(gè)非負(fù)數(shù)cij,叫做弧的容量。我們把這樣的圖叫做弧的容量。我們把這樣的圖G叫做容量網(wǎng)叫做容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)，記做絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)，記做G=V

28、，E，C。網(wǎng)絡(luò)網(wǎng)絡(luò)G上的流，是指定義在弧集合上的流，是指定義在弧集合E上的一個(gè)函上的一個(gè)函數(shù)數(shù)其中其中f(vi ,vj) =fij 叫做弧叫做弧(vi，vj)上的流量。上的流量。 ),(jijifvvff 2、稱滿足以下條件的流為可行流：、稱滿足以下條件的流為可行流：1容量條件：對(duì)于每一個(gè)弧容量條件：對(duì)于每一個(gè)弧vi ,vjE有有 0 fij cij 。 2平衡條件：平衡條件：對(duì)于發(fā)點(diǎn)對(duì)于發(fā)點(diǎn)vs，有，有對(duì)于收點(diǎn)對(duì)于收點(diǎn)vt ，有，有對(duì)于中間點(diǎn)，有對(duì)于中間點(diǎn)，有 EvvjsjsWf),(WfEvvt jtj ),( EvvEvvi jjijiijff),(),(可行流中可行流中 fijcij

29、的弧叫做飽和弧，的弧叫做飽和弧，fijcij的弧叫做非飽和弧。的弧叫做非飽和弧。vsv1v2v4v3vt374556378S),(2vvSs ),(431tvvvvS ),(),(, ),( , ),(),(4232211vvvvvvvvSSs 18567),(23241 lllSSCs 3、容量網(wǎng)絡(luò)G =V，E，C，vs為始點(diǎn)，vt為終點(diǎn)。假設(shè)把V分成兩個(gè)非空集合 使 ，那么一切一點(diǎn)屬于 ，而另一點(diǎn)屬于 的弧的集合，稱為由 決議的割集,記作 。割集 中一切始點(diǎn)在 ，終點(diǎn)在 的弧的容量之和，稱為這個(gè)割集的容量，記為 。 SS ,SvSvts,S),(SS),(SS),(SSCSSSS關(guān)于最大流

30、問題的定理：關(guān)于最大流問題的定理：最大流最小割定理：任一網(wǎng)絡(luò)中，最大流最小割定理：任一網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。最大流的流量等于最小割集的容量。 4、容量網(wǎng)絡(luò)、容量網(wǎng)絡(luò)G，假設(shè)，假設(shè) 為網(wǎng)絡(luò)中從為網(wǎng)絡(luò)中從vs到到vt的一條鏈，給的一條鏈，給 定向?yàn)閺亩ㄏ驗(yàn)閺膙s到到vt， 上的弧凡上的弧凡與與 方向一樣的稱為前向弧，凡與方向一樣的稱為前向弧，凡與 方向相反方向相反的稱為后向弧，其集合分別用的稱為后向弧，其集合分別用 和和 表示。表示。f 是一個(gè)可行流，假設(shè)滿足：是一個(gè)可行流，假設(shè)滿足： 那么稱那么稱 為從為從vs到到vt 的關(guān)于的關(guān)于f 的一條增廣的一條增廣鏈。鏈。 ),(0),(0jijijijijijivvcfvvcf 推論推論 可行流可行流f 是最大流的充分必要條件是不存是最大流的充分必要條件是不存在從在從vs到到vt 的關(guān)于的關(guān)于f 的一條可增廣鏈。的一條可增廣鏈。 2v1v3v4v5v6v7v 13 (5)9