13-圖與網(wǎng)絡(luò)規(guī)劃

1、第十章 圖與網(wǎng)絡(luò)優(yōu)化主要內(nèi)容: 圖論的基本概念最小支撐樹問題最短路問題最大流問題最小費用最大流問題1例：七橋問題AB CD問題：一個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點。 能否從某一點開始不重復(fù)地一筆畫出這個圖形，最后回到原點。第十章 圖與網(wǎng)絡(luò)2例：有甲、乙、丙、丁、戊五個球隊，各隊之間比賽 情況如表：v1甲v2乙v3丙v4丁v5戊3點：研究對象（陸地、球隊）；點之間的連線：對象之間的特定關(guān)系（陸地間的橋、球隊 之間的比賽及結(jié)果）。對稱關(guān)系：甲與乙有某種關(guān)系，同時乙與甲也有這種關(guān)系。 用不帶箭頭的連線表示，稱為邊。例如：橋。非對稱關(guān)系：甲與乙有某種關(guān)系，但并不意味著乙與甲也

2、 有這種關(guān)系。用帶箭頭的連線表示， 稱為弧。 例如：球隊間的勝負(fù)關(guān)系。圖是由點和點與點之間的連線組成的。第一節(jié) 圖的基本概念4一、圖的定義定義1：一個圖，是由非空點集V 和邊集E（或弧集A） 所構(gòu)成的二元組。 vi表示點 ， V= vi 稱為點集； ek表示邊 ， E=ek稱為邊集； ak表示弧 ， A=ak稱為弧集； 在一般情況下，圖中點的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要。 因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。圖無向圖有向圖5無向圖G：由點及邊所構(gòu)成的圖，簡記為：G=(V，E)有向圖D：由點及弧所構(gòu)成的圖，簡記為：D=(V，A)圖G

3、或D中點的個數(shù)，記為p ，邊的條數(shù)記為q。連接點vi，vj的邊ek記作ek=vi，vj連接點vi，vj的弧ak記作ak=（vi，vj）6二、圖論中常用術(shù)語1、相鄰與關(guān)聯(lián) 若邊e=u，vE，則稱點u，v是e的端點，也稱u，v是相鄰的。稱e是點u，v的關(guān)聯(lián)邊。 若兩條邊有一個公共的端點，則稱這兩條邊相鄰。uveu，v相鄰 e 與u，v關(guān)聯(lián)點點邊邊點邊vie1e1 與e2相鄰vjvke2.72、簡單圖與多重圖某條邊兩個端點相同，稱這條邊為環(huán)。若兩點之間有多于一條的邊，稱這些邊為多重邊。無環(huán)、無多重邊的圖稱為簡單圖。多重圖：無環(huán)、但允許有多重邊。v1e1e2e3v2v3e5e4v483、鏈與圈 給定一

4、個無向圖G=（V，E），G中的一個點、邊交錯序列（v1，e1，v2，e2，vk-1，ek-1，vk），如果滿足et=vt，vt+1（t=1，2，k-1），則稱其為一條聯(lián)接v1和vk的鏈，記為=（v1，v2，vk）。初等鏈：鏈中點都不同。v1v2v3v4v5v6e1e2e3e4e5e6e8e9例：1=（v2，v1，v3，v6，v4，v3，v5）例：2=（v2，v1，v3，v5）9v7v8e7例：C1=（v1，v2，v4，v3，v5，v6，v3 ，v1 ）初等圈：C2=（v1，v2，v4，v6，v5，v3 ，v1 ）有向圖D中，當(dāng)鏈(圈)上弧的方向一致時，稱為路(回路)。v1v2v3v4v5v6e

5、1e2e3e4e5e6e8e9 任意兩點之間至少有一條鏈的圖稱為連通圖，否則為不連通圖。 鏈（v1，v2，vk）中，若v1=vk ，稱之為一個圈，記為C= （v1，v2，vk-1， vk ） 。10（G）4、支撐子圖定義2 給定圖G=（V，E），若圖G=（V，E），其 中EE，則稱G是G的一個支撐子圖。（G）支撐子圖11 定義2 設(shè)圖T=V，E是圖G=（V，E）的支撐子圖，如果T又是一個樹，則稱T是圖G的一個支撐樹。v3v1v2v4v5v6（G）v3v1v2v4v5v6（T）（T）是（G）的一個支撐樹。一、樹與圖的支撐樹定義1： 無圈的連通圖稱為樹。樹一般用T表示。第二節(jié) 最小樹問題12（一）

6、破圈法13（二）避圈法基本思想：在圖中任取一條邊e1，找一條與e1不構(gòu) 成圈的邊e2，再找一條與e1和e2不構(gòu)成 圈的邊e3。一般設(shè)已有e1，e2， ek，找一條與e1, e2 , ek中任何一條 邊都不構(gòu)成圈的邊ek+1，重復(fù)這個過 程，直到不能進行為止。14v3v1v2v4v5v6v3v1v2v3v1v2v5v3v1v2v5v4v3v1v2v5v4v615二、最小支撐樹問題定義3 設(shè)有連通圖G=（V，E），G的任一邊ek=vi，vj 有一個非負(fù)權(quán)w（ek）=wij（wij0）,T=（V，E） 是G的一個支撐樹，稱為樹T的權(quán)。定義4 如果支撐樹T*是圖G的所有支撐樹中權(quán)最小的， 則稱T*是G

7、的最小支撐樹（簡稱最小樹）。16最小支撐樹問題，就是求網(wǎng)絡(luò)G的最小支撐樹。（一）避圈法（Kruskal）思想：在圖中取一條權(quán)最小的邊，以后每一步中，總 從未被選取的邊中選一條權(quán)盡可能小的邊，并 使之與已選取的邊不構(gòu)成圈（每一步中，如果 有兩條或兩條以上的邊都符合要求，則從中任 選一條），直到不能進行為止。17Kruskal算法步驟：第1步：圖G =（V，E） ，p=n ，q=m，把G的邊按權(quán)由 小到大排好，w（e1） w （e2） w （em）令i=1 ，j=0 ， E0= ，取的邊數(shù)最小樹的邊集第2步：按順序檢查ei,如果（V，Ei-1ei）含圈，Ei=Ei-1，不要這條邊 令i=i+1，繼

8、續(xù)檢查ei，如果（V，Ei-1ei）不含圈， 令Ei=Ei-1ei，j=j+1。第3步：重復(fù)第2步，直到取的邊數(shù)j=n-1，結(jié)束， （V，Ei）就是所求最小樹，取定這條邊檢查過的邊數(shù)18例： 某工廠內(nèi)聯(lián)結(jié)六個車間的道路如圖示。已知每 條道路的長，要求沿道路架設(shè)聯(lián)結(jié)六個車間的 電話線網(wǎng)，使電話線的總長最短。2345674v3v1v2v4v5v65119解：將各邊按權(quán)從小到大排為：w23 w24 w45 w 56 = w 46 w12= w35 w13 w25j=0 ，E0= ，n=6， n-1=51、取權(quán)重最小的邊v2,v3，權(quán)為1，j=1 5,2、在剩余各邊中取權(quán)重最小且不與上述已取各邊不形成

9、圈的邊v2,v4，其權(quán)重為2， j=2 5,3、同上，取邊v4,v5，其權(quán)重為3， j=3 5,4、同上，取邊v5,v6，其權(quán)重為4， j=4 5,5、同上，取邊v1,v2，其權(quán)重為5， j=5,結(jié)束。 電話線總長最小方案如圖，總長15單位。2314v3v1v2v4v5v6520v32345674v1v2v4v5v615（二）破圈法任取一個圈，從中去掉權(quán)重最大的一條邊，（如果有多條權(quán)重最大的邊，任意去掉一條）重復(fù)這個步驟，直到得到一個不含圈的圖為止。21一、最短路問題例 下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條 線的長度?，F(xiàn)在某人要從v1出發(fā)，通過這個交 通網(wǎng)到v8去，他有不同的走法。v2

10、v523464v3v1v4121061210v8v9v72363v66+1+6=133+2+10+2+4=21第三節(jié) 最短路問題問題：如何找一條最短的路線。22 給定有向圖D=（V，A），對每一條弧 ，有權(quán) , 給定D中的兩個頂點vs（發(fā)點），vt（收點）。設(shè)P是圖中從vs到vt的一條路，定義路P的權(quán)（不妨表示長度）是P中所有弧的權(quán)之和，記為w（P）。 最短路問題就是要在所有從vs到vt的路中，求一條路P0 ，使最短路問題 稱P0是從vs到vt的最短路。23二、Dijkstra算法 當(dāng)所有 時，本算法是用來求給定點vs到任一個點vj最短路的公認(rèn)的最好方法?；舅枷耄?從vs出發(fā)，對每個點進行標(biāo)

11、號（P標(biāo)號或T標(biāo)號)，然后逐步外探，將某個具有T標(biāo)號的點改為P標(biāo)號點，當(dāng)終點vt得到P標(biāo)號時，就求出了從vs到各個點的最短路。P（permanent）標(biāo)號:表示從vs到該點的最短路的長度；T（tentative）標(biāo)號:表示從vs到該點的最短路長度的上界。24符號含義 Si： 表示第i步時具有P標(biāo)號的點的集合； P(vi):表示vi 點的P標(biāo)號，即vs到vi的最短路長度； T(vj):表示vj點的T標(biāo)號，即vs到vj的最短路長度的上界； (vi) ：前點標(biāo)號，表示點vs到v i的最短路上v i的前一點。如 （vi） =m，表示vs到v i的最短路上vi前一點是vm；如 （v） =0，表示v=vs

12、；如 （v） =M，表示從vs到v 沒有路。25例 用Dijkstra算法求前面例子中從v1到v8的最短路。i=0 給發(fā)點v1以P標(biāo)號，令S0=v1，P(v1)=0，(v1)=0， 其余各點均給T標(biāo)號，T(vi)=+ ，(vi)=M，(i=2,3,9)從v1出發(fā),考察以v1為出發(fā)點且與其相鄰的所有具有T標(biāo)號的點v2，v3，v4v2v523464v3v1v4121061210v8v9v72363v6261,6圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, M, 1,1M, M, M, 1,3271,6圖上標(biāo)號法:v5v223464v3v1v41

13、210 6 1210v8v9v72363v60,0M, M, 1,1M, M, M, 1,3281,6圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, 4,111,1M, M, M, 1,3291,5圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, 4,111,1M, M, M, 1,31,6301,5圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, 4,111,1M, M, M, 1,33,5313,5圖上標(biāo)號法:v5v223464v3v1v4

14、1210 6 1210v8v9v72363v60,0M, 4,111,1M, M, 1,3M, 323,5圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,1M, 2,6M, 1,3M,333,5圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,1M, 2,6M, 1,3M,343,5圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,1M, 2,65,121,35,9353,5圖上標(biāo)號法:v5v223464v3v1v41210

15、6 1210v8v9v72363v60,05,101,1M, 2,65,121,35,9362,5圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1M, 2,65,121,35,95,10372,5圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1M, 2,65,121,35,95,1038例 用Dijkstra算法求前面例子中從v1到v8的最短路。i=0 給發(fā)點v1以P標(biāo)號，令S0=v1，P(v1)=0，(v1)=0， 其余各點均給T標(biāo)號，T(vi)=+ ，(vi)=M，(i=2,3,9)從v

16、1出發(fā),考察以v1為出發(fā)點且與其相鄰的所有具有T標(biāo)號的點v2，v3，v4v2v523464v3v1v4121061210v8v9v72363v639對v2,有T(v2)=minT(v2), P(v1)+w12=min+ ,0+6=6同時修改(v2)=1同理有， T(v3)=3， (v3)=1 ； T(v4)=1， (v4)=1；比較所有T標(biāo)號， T(v4)=1最小， P(v4)=1，S1=v1，v4v2v523464v3v1v4121061210v8v9v72363v640v2v523464v3v1v4121061210v8v9v72363v6i=1 從剛得到P標(biāo)號的點v4出發(fā),考察以v4為出

17、發(fā)點且與 其相鄰的所有具有T標(biāo)號的點v6， T(v6)=minT(v6), P(v4)+w46=min+ ,1+10=11， 同時修改(v6)=4比較所有T標(biāo)號， T(v3)=3最小， P(v3)=3， S2=v1，v4，v341v2v523464v3v1v4121061210v8v9v72363v6i=2 從剛得到P標(biāo)號的點v3出發(fā),考察以v3為出發(fā)點且與 其相鄰的所有具有T標(biāo)號的點v2， T(v2)=minT(v2), P(v3)+w32=min6 ，3+2=5， 同時修改(v2)=3比較所有T標(biāo)號， T(v2)=5最小， P(v2)=5， S3=v1，v4，v3，v242v2v52346

18、4v3v1v4121061210v8v9v72363v6i=3 從剛得到P標(biāo)號的點v2出發(fā),考察以v2為出發(fā)點且與 其相鄰的所有具有T標(biāo)號的點v5， T(v5)=minT(v5), P(v2)+w25=min+ ，5+1=6， 同時修改(v5)=2比較所有T標(biāo)號， T(v5)=6最小， P(v5)=6， S4=v1，v4，v3，v2，v543v2v523464v3v1v4121061210v8v9v72363v6i=4 從剛得到P標(biāo)號的點v5出發(fā),考察以v5為出發(fā)點且與 其相鄰的所有具有T標(biāo)號的點v6，v7，v8，可得到 T(v6)=minT(v6), P(v5)+w56=min+ ，6+4=

19、10， 同時修改(v6)=5同理可得： T(v7)=9； T(v8)=12，修改(v7)=5 ;(v8)=5比較所有T標(biāo)號， T(v7)=9最小， P(v7)=9， S5=v1，v4，v3，v2，v5，v744v2v523464v3v1v4121061210v8v9v72363v6i=5 從剛得到P標(biāo)號的點v7出發(fā),考察以v7為出發(fā)點且與 其相鄰的所有具有T標(biāo)號的點v8，可得到 T(v8)=minT(v8)，P(v7)+w78=min12 ，9+4=12， T(v8)沒變， (v8)=5不變比較所有T標(biāo)號， T(v6)=10最小， P(v6)=10， S6=v1，v4，v3，v2，v5，v7，

20、v645v2v523464v3v1v4121061210v8v9v72363v6i=6 從剛得到P標(biāo)號的點v6出發(fā),考察以v6為出發(fā)點且與 其相鄰的所有具有T標(biāo)號的點， 沒有符合要求的點， 直接進行下一步比較所有T標(biāo)號， T(v8)=12最小， P(v8)=12， S6=v1，v4，v3，v2，v5，v7，v6，v846i=7 從剛得到P標(biāo)號的點v8出發(fā),考察以v8為出發(fā)點且與 其相鄰的所有具有T標(biāo)號的點， 沒有符合要求的點， 直接進行下一步。比較所有T標(biāo)號， 此時只有T(v9)= + ，且不能修改， 表明從發(fā)點v1到v9沒有路，算法終止。計算結(jié)果： S7=v1，v4，v3，v2，v5，v7，v6，v8 P(v