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

1、第十一章 圖與網(wǎng)絡(luò)模型 一、圖與網(wǎng)絡(luò)模型介紹二、最短路問題三、最小生成樹問題四、最大流問題第1頁(yè)，共51頁(yè)。一、圖與網(wǎng)絡(luò)模型介紹 1、引例一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識(shí)、與孫也相互認(rèn)識(shí)；錢與孫相互認(rèn)識(shí)、孫與李相互認(rèn)識(shí)。他們與周都不認(rèn)識(shí)。如何清晰的表示這些人之間的關(guān)系呢？當(dāng)人數(shù)更多、人們間相互關(guān)系更復(fù)雜時(shí)，該怎樣描述人們間的關(guān)系？第2頁(yè)，共51頁(yè)。一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識(shí)、與孫也相互認(rèn)識(shí)；錢與孫相互認(rèn)識(shí)、孫與李相互認(rèn)識(shí)。他們與周都不認(rèn)識(shí)。趙錢孫李周第3頁(yè)，共51頁(yè)。趙錢孫李周吳陳如果我們將上面的例子中人們之間的關(guān)系由“相互認(rèn)識(shí)”改

2、變成“認(rèn)識(shí)”，如趙和周之間的關(guān)系是，周認(rèn)識(shí)趙而趙不認(rèn)識(shí)周，這時(shí)我們?nèi)绾伪磉_(dá)人們之間的這種關(guān)系呢？第4頁(yè)，共51頁(yè)。用帶箭頭的線來表示人們之間的關(guān)系：趙孫周吳陳錢李第5頁(yè)，共51頁(yè)。一、圖與網(wǎng)絡(luò)模型介紹2、相關(guān)概念（1）點(diǎn)、邊、?。?）無向圖、有向圖（3）鏈、圈、連通圖（4）路、回路（5）權(quán)、網(wǎng)絡(luò)第6頁(yè)，共51頁(yè)。點(diǎn)、邊、弧點(diǎn)用于表示各種事物，一般用V表示 一個(gè)圖中往往有多個(gè)點(diǎn)，一般用v1、v2、表示。一個(gè)圖中所有的n個(gè)點(diǎn)構(gòu)成點(diǎn)集V=v1、v2、vn邊用于描述事物間關(guān)系的線，一般用E表示。一個(gè)圖中往往有多個(gè)邊，一般用e1、e2、表示。一個(gè)圖中所有的n條邊構(gòu)成邊集E=e1、e2、en弧帶有箭頭的線

3、，一般用A表示。一個(gè)圖中的n條弧，一般用a1、a2、表示。一個(gè)圖中所有的n條邊構(gòu)成邊集A=a1、a2、an第7頁(yè)，共51頁(yè)。無向圖、有向圖無向圖：由點(diǎn)和邊構(gòu)成的圖，簡(jiǎn)稱“圖”，一般用G表示。G=（V，E），V是圖G的點(diǎn)集，E是圖G的邊集。有向圖：由點(diǎn)和弧構(gòu)成的圖，一般用D表示。D=（V，A），V是圖D的點(diǎn)集，A是圖D的弧集。第8頁(yè)，共51頁(yè)。鏈、圈、連通圖鏈：對(duì)于無向圖G來說，如果存在一個(gè)點(diǎn)、邊交錯(cuò)序列（v1、e1、v2、e2、vn）,其中邊ei的起點(diǎn)是vi，終點(diǎn)是vi+1，即ei=（vi，vi+1），則稱這條點(diǎn)、邊交錯(cuò)序列為聯(lián)結(jié)v1，vn的鏈。圈：如果一條鏈（v1、e1、v2、e2、vn）中

4、， v1=vn，則稱之為圈連通圖：對(duì)一個(gè)無向圖G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則稱G為連通圖第9頁(yè)，共51頁(yè)。路、回路路：在有向圖D中，如果存在一個(gè)點(diǎn)、弧交錯(cuò)序列： （v1、a1、v2、a2、vn）,其中邊ai的起點(diǎn)是vi，終點(diǎn)是vi+1，即ai=（vi，vi+1），則稱這條點(diǎn)、弧交錯(cuò)序列為聯(lián)結(jié)v1，vn的一條路?；芈罚喝绻返牡谝粋€(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則稱這條路為回路。第10頁(yè)，共51頁(yè)。權(quán)、網(wǎng)絡(luò)權(quán)：當(dāng)無向圖G的每一條邊（vi，vj） ，或有向圖D的每一條弧（vi，vj）上都相應(yīng)地有一個(gè)數(shù)來進(jìn)一步說明點(diǎn)與點(diǎn)之間的關(guān)系，那么這樣的數(shù)我們可以稱之為權(quán)，記為wij。給無向圖G或有向圖D

5、添加權(quán)的過程，通常稱為賦權(quán)。網(wǎng)絡(luò)：我們稱賦了權(quán)的有向圖D為網(wǎng)絡(luò)。第11頁(yè)，共51頁(yè)。二、最短路問題最短路問題是對(duì)一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)vs到vt找到一條從vs到vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱為從vs到vt的最短路，這條路上所有弧的權(quán)數(shù)的總和被稱之為從vs到vt的距離。如下圖，找出從v1到v4的最短路v1v2v3v442159v2第12頁(yè)，共51頁(yè)。對(duì)下圖，找出從vs到vt的最短路161617171822222323303031414159vsv1v2v3v4vt第13頁(yè)，共51頁(yè)。例1 求下圖中v1到v6的最短路有向圖D=（V，A），V=v1，v2，v6A

6、=(v1,v2) ，(v1,v4)，(v1,v3),(v2,v6), (v4,v2), (v4,v6), (v3,v5),(v3,v5), (v5,v4), (v5,v6) cij表示vi到vj的權(quán)v1v2v3v4v5v63252153571第14頁(yè)，共51頁(yè)。例1 求下圖中v1到v6的最短路v1到vt的最短路步驟：1、給起點(diǎn)v1標(biāo)號(hào)（0，s）2、確定已標(biāo)號(hào)點(diǎn)集I，未標(biāo)號(hào)點(diǎn)集J，找出弧集A=（vi,vj）|vi I，vj J3、如果弧集A=空集，那么如果vt已標(biāo)號(hào)，則結(jié)束，如果vt未標(biāo)號(hào)則說明不存在從v1到vt的路。否則，如果弧集A空集，轉(zhuǎn)44、對(duì)A中的弧，計(jì)算sij=li+cij,從中找出值

7、最小的弧，給此弧標(biāo)號(hào)為（sij，i）v1v2v3v4v5v63252153571雙標(biāo)號(hào)（sij，i）中sij表示由vi到vj的最短路長(zhǎng)， i表示vi到vj的最短路上，此點(diǎn)前一個(gè)點(diǎn)的下角標(biāo)。第15頁(yè)，共51頁(yè)。例2 電線公司準(zhǔn)備在甲乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短。兩地交通圖如下：v1v2v3v4v5v61510326245176v7（甲）（乙）第16頁(yè)，共51頁(yè)。1、 永久標(biāo)號(hào)：v1（0，s）K=12、I=v1，J=v2,v3,v4,v5,v6,v7，A=(v1, v2)，(v1, v3)3、A4、s12=l1+c12=0+15=15 s13=l1+c13=0+10=10M

8、insij=s13,永久標(biāo)號(hào)：v3=（sij,i）=（10，1）v1v2v3v4v5v61510326245176v7（0，s）（10，1）第17頁(yè)，共51頁(yè)。s12=l1+c12=0+15=15K=22、I=v1,v3，J=v2, v4,v5,v6,v7，A=(v1, v2)，(v3, v2)，(v3, v5)3、A4、s32=l3+c32=10+3=13 s35=l3+c35=10+5=15Minsij=s32,永久標(biāo)號(hào)：v2=（sij,i）=（13，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）第18頁(yè)，共51頁(yè)。s35=l3+c35=10+

9、5=15K=32、I=v1, v2, v3，J=v4,v5,v6,v7，A=(v2, v7)，(v2, v4)，(v3, v5)3、A4、s27=l2+c27=13+17=30 s24=l2+c24=13+6=19Minsij=s35,永久標(biāo)號(hào)：v5=（sij,i）=（15，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）第19頁(yè)，共51頁(yè)。s27=l2+c27=13+17=30s24=l2+c24=13+ 6=19K=42、I=v1, v2, v3,v5，J=v4,v6,v7，A=(v2, v7)，(v2, v4)，(v5, v4),

10、(v5, v6)3、A4、s54=l5+c54=15+4=19 s56=l5+c56=15+2=17Minsij=s56,永久標(biāo)號(hào)：v6=（sij,i）=（17，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）第20頁(yè)，共51頁(yè)。s27=30 s24=19 s54=19K=52、I=v1, v2, v3,v5,v6，J=v4,v7，A=(v2, v7)，(v2, v4)，(v5, v4), (v6, v7)3、A4、s67=l6+c67=17+6=23Minsij=s24=s54, 永久標(biāo)號(hào)：v4=（sij,i）=（19，2）

11、或（19，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2） /(19，5)第21頁(yè)，共51頁(yè)。s27=30 K=62、I=v1, v2, v3, v4,v5,v6，J=v7，A=(v2, v7) ，(v4, v7) ，(v6, v7)3、A4、s47=l4+c47=19+2=21s67=l6+c67=17+6=23Minsij=s47,永久標(biāo)號(hào)：v7=（sij,i）=（21，4）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2） /(19，5

12、)（21，4）第22頁(yè)，共51頁(yè)。V1到v7的最短路長(zhǎng)為21，最短路徑是v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2） /(19，5)（21，4）v7v4v2v7v4v5v3v1v3v1第23頁(yè)，共51頁(yè)。三、最小生成樹問題幾個(gè)概念：樹：無圈的連通圖生成子圖：給定一個(gè)無向圖G=(V,E)，保留G中的所有點(diǎn)，刪掉部分G的邊，所得的新圖G就是G的生成子圖。生成樹：如果圖G的生成子圖是一個(gè)樹，則稱這個(gè)生成子圖為生成樹。最小生成樹：在一個(gè)賦權(quán)的連通的無向圖中，找出一個(gè)生成樹，如果這個(gè)生成樹的所有邊的權(quán)數(shù)之和最小，那么這個(gè)樹就

13、叫做最小生成樹。第24頁(yè)，共51頁(yè)。最小生成樹求解方法一：破圈法算法步驟：1、在給定的賦權(quán)連通圖上任找一圈2、在找到的圈中刪掉一條權(quán)數(shù)最大的邊3、如果余下的圖不含圈，則它們構(gòu)成最小生成樹。第25頁(yè)，共51頁(yè)。例4 用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278第26頁(yè)，共51頁(yè)。例4 用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278第27頁(yè)，共51頁(yè)。例4 用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278最小生成樹如圖，總權(quán)數(shù)為19第28頁(yè)，共51頁(yè)。最小生成樹求解方法一：避圈法算法步

14、驟：1、另作一圖G，繪制原圖G的所有頂點(diǎn)2、依次選取權(quán)數(shù)最小的邊3、若在圖G中加入此邊后不會(huì)產(chǎn)生圈，則在圖G中加入此邊。否則在剩下的邊中繼續(xù)選取。第29頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3103345341278v1v2v6v7v5v4v3333127最小生成樹如圖，總權(quán)數(shù)為19第30頁(yè)，共51頁(yè)。四、最大流問題給了一個(gè)帶發(fā)點(diǎn)和收點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)表示容量。在不超過每條弧容量的前提下，求從發(fā)點(diǎn)到收點(diǎn)的最大流量。第31頁(yè)，共51頁(yè)。例6 根據(jù)石油公司的管道網(wǎng)絡(luò)，確定從v1到v7的最大流。v1v2v6v7v5v4v366321223254第32頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3

15、（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）第33頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2 （2，4）（2，0）第34頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2 （2，0）（2，4）+3（3，3）（3，0）（3，2）第35頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（0，2）（0，2）（0，4）

16、+2 （2，0）（2，4）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）第36頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（0，2）+2 （2，0）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）第37頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（0，3）（0，2）+2 （2，0）+3（3，0）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）第38頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3+2 （2，0）+3（

17、3，0）+1（1，0）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）第39頁(yè)，共51頁(yè)。五、最小費(fèi)用最大流問題最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條?。╲i，vj），除了給出了容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流F，并使得總費(fèi)送費(fèi)用最小。第40頁(yè)，共51頁(yè)。例7 由于輸油管道長(zhǎng)短不一，所以例6中的每段管道除了有不同流量cij的限制外，還有不同的單位流量的費(fèi)用bij，我們對(duì)每段管道（vi，vj）都用（cij，bij）。使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從v1向v7運(yùn)送石油，怎樣才能運(yùn)送最多的石油，并使得總的運(yùn)送費(fèi)最小？v1v2v

18、6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）第41頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）第42頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）第43頁(yè)，共51頁(yè)。v1

19、v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）從發(fā)點(diǎn)到收點(diǎn)的增廣路首選總的單位費(fèi)用最小的路單位費(fèi)用：101費(fèi)用：110（5，3）（1，-3）（0，3）（1，-3）（3，4）（1，-4）第44頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（5，3）（3，2）（2，3）（0，3）（2，8）（3，4）（2，4）（0，-6）（1，-3）（0，-4）（

20、0，-5）（0，-2）（1，-3）（0，-8）（0，-4）（0，-3）（0，-7）（1，-4）費(fèi)用：1101單位費(fèi)用：11+2+211（3，3）（3，-3）（0，8）（2，-8）第45頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（3，3）（3，2）（2，3）（0，3）（0，8）（3，4）（2，4）（0，-6）（3，-3）（0，-4）（0，-5）（0，-2）（1，-3）（2，-8）（0，-4）（0，-3）（0，-7）（1，-4）1+2費(fèi)用：110+ 211+2單位費(fèi)用：12+212（1，3）（5，-3）（1，2）（2，-2）（0，3）（2，-3）（1，4）（3，-4）第46頁(yè)，共51頁(yè)。v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（1，3）（1，2）（0，3）（0，3）（0，8）（1，4）（2，4）（0，-6）（5，-3）（0，-4）（0，-5）（2，-2）（1，-3）（2，-8）（0，-4）（2，-3）（0，-7）（3，-4）1+2+2費(fèi)用：110+ 211+212單位費(fèi)用：16+1+116（0，3）（6，-