運籌學錢老師課件or

1、2010/03-第6章 圖與網(wǎng)絡分析-1-第六章 圖與網(wǎng)絡分析圖是一種模型，如公路、鐵路交通圖， 通訊網(wǎng)絡圖等。圖示對現(xiàn)實的抽象，以點和線段的連接組合表示。2010/03-第6章 圖與網(wǎng)絡分析-2-6.1 圖的基本概念和模型一、概念（1）圖：點V和邊E的集合，用以表示對某種現(xiàn)實事物的抽象。記作 G=V,E,V=v1,v2,vn, E=e1,e2,em點：表示所研究的事物對象； 邊：表示事物之間的聯(lián)系。v1v2v3v4v0e1e2e3e4e5e6e7e0（2）若邊e的兩個端點重合，則稱e為環(huán)。（3）多重邊：若某兩端點之間多于一條邊，則稱為多重邊。2010/03-第6章 圖與網(wǎng)絡分析-3-（4）簡

2、單圖：無環(huán)、無多重邊的圖稱為簡單圖。（5）鏈：點和邊的交替序列，其中點可重復，但邊不能重復。（6）路：點和邊的交替序列，但點和邊均不能重復。（7）圈：始點和終點重合的鏈。（8）回路：始點和終點重合的路。（9）連通圖：若一個圖中，任意兩點之間至少存在一條鏈，稱這樣的圖為連通圖。（10）子圖，部分圖：設圖G1=V1,E1, G2=V2,E2, 如果有V1V2，E1E2，則稱G1是G2的一個子圖；若V1=V2，E1E2，則稱G1是G2的一個部分圖。（11）次：某點的關聯(lián)邊的個數(shù)稱為該點的次，以d(vi)表示。2010/03-第6章 圖與網(wǎng)絡分析-4-二、圖的模型 例：有甲、乙、丙、丁、戊、己六名運動

3、員報名參加A、B、C、D、E、F六個項目的比賽。如表中所示，打“”的項目是各運動員報名參加比賽的項目。問：六個項目的比賽順序應如何安排，才能做到使每名運動員不連續(xù)地參加兩項比賽？甲 乙 丙 丁 戊 己項目人A B C D E F 2010/03-第6章 圖與網(wǎng)絡分析-5-建立模型：解：項目作為研究對象，排序。設 點：表示運動項目。邊：若兩個項目之間無同一名運動員參加。ABCDEFACDEFBAFEDCBACBFEDAFBCDE順序：2010/03-第6章 圖與網(wǎng)絡分析-6-6.2 樹圖和圖的最小部分樹（1）樹圖： 無圈的連通圖稱為樹圖，簡稱為樹。記為T（V，E）一、樹圖的概念2010/03-第

4、6章 圖與網(wǎng)絡分析-7-（2）樹圖的性質(zhì)反證法：若各點次均不為1，因樹中不存在孤立點，則必對所有節(jié)點的次， 均有d(vi)2， 即d(v1)2 d(v2)2 d(v3)2而點數(shù)有限，故必推至前述某一點vi ，從而形成圈結構，與樹圖定義矛盾。性質(zhì)1：任何樹中必存在次為1的點。2010/03-第6章 圖與網(wǎng)絡分析-8-（2）樹圖的性質(zhì)歸納法：n=2時，1條邊； n=3時，2條邊，性質(zhì)成立。 設 n= k 時，有k-1條邊成立， 則可新增1個點、一條邊后仍可為樹圖，故性質(zhì)成立。性質(zhì)2：具有n個頂點的樹的邊數(shù)恰好為n-1條。2010/03-第6章 圖與網(wǎng)絡分析-9-（3）樹圖的性質(zhì)反證法：若有n個點、

5、n-1條邊的連通圖不為樹圖，則必形成圈。不妨從圖中減掉多余的邊（不減點）而使之形成樹圖，則所形成的樹圖有少于n-1條邊，與性質(zhì)2矛盾。性質(zhì)3：任何具有n個點、n-1條邊的連通圖必為樹圖。2010/03-第6章 圖與網(wǎng)絡分析-10-（3）樹的特性： 樹是邊數(shù)最多的無圈連通圖。在樹中任加一條邊，就會形成圈。 樹是邊數(shù)最少的連通圖。在樹中任減一條邊，則不連通。二、圖的最小部分樹：1圖的部分樹：若G1是G2的一個部分圖，且為樹圖，則稱G1是G2的一個部分樹。G2：ABCD547365576G1：ACBD2010/03-第6章 圖與網(wǎng)絡分析-11-2圖的最小部分樹：樹枝總長為最短的部分樹稱為圖的最小部分

6、樹。三、最小部分樹的求法樹枝：樹圖中的邊稱為樹枝。定理1：圖中任一個點i，若j是與i相鄰點中距離最近的點，則邊i，j一定在其最小部分樹內(nèi)。反證法：2010/03-第6章 圖與網(wǎng)絡分析-12-例：要在下圖所示的各個位置之間建立起通信網(wǎng)絡，試確定使總距離最佳的方案。推論：將圖中所有的點分成V和V兩個集合，則兩個集合之間連線最短的一個邊一定包含在最小部分樹內(nèi)。2010/03-第6章 圖與網(wǎng)絡分析-13-SABCDET252414317557最小部分樹長Lmin=142010/03-第6章 圖與網(wǎng)絡分析-14-1. 避圈法：將圖中所有的點分V為V兩部分，V最小部分樹內(nèi)點的集合V非最小部分樹內(nèi)點的集合

7、任取一點vi加粗，令viV， 取V中與V相連的邊中一條最短的邊(vi,vj)， 加粗(vi,vj)，令vjV 重復 ，至所有的點均在V之內(nèi)。2. 破圈法： 任取一圈，去掉其中一條最長的邊， 重復，至圖中不存在任何的圈為止。2010/03-第6章 圖與網(wǎng)絡分析-15-SABCDET252414317557最小部分樹長Lmin=142010/03-第6章 圖與網(wǎng)絡分析-16-6.3 最短路問題 在圖示的網(wǎng)絡圖中，從給定的點S出發(fā)，要到達目的地T。問：選擇怎樣的行走路線，可使總行程最短？方法：Dijkstra（D氏）標號法按離出發(fā)點的距離由近至遠逐漸標出最短距離和最佳行進路線。S1求某兩點間最短距離

8、的D（Dijkstra）氏標號法2472010/03-第6章 圖與網(wǎng)絡分析-17-SABCDET25241431755702447891413594 最短路線：S AB E D T最短距離：Lmin=132010/03-第6章 圖與網(wǎng)絡分析-18-2求任意兩點間最短距離的矩陣算法 構造任意兩點間直接到達的最短距離矩陣D（0）= dij（0） S A B C D E T S 0 2 5 4 A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0D（0）= 構造任意兩點間直接到達、或者最多經(jīng)過1個中間點到達的最短距離矩陣D

9、（1）= dij（1）2010/03-第6章 圖與網(wǎng)絡分析-19-其中 dij（1）= min dir（0）+ drj（0） ， S A B C D E T S 0 2 4 4 9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8 5 3 4 1 0 6 T 12 10 11 5 7 0D（1）=irjdir（0）drj（0）rdSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0）, dSD（0）+ dDE（0）

10、, dSE（0）+ dEE（0）, dST（0）+ dTE（0） =8例如2010/03-第6章 圖與網(wǎng)絡分析-20-其中 dij（2）= min dir（1）+ drj（1） S A B C D E T S 0 2 4 4 8 7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0D（2）=irjdir（1）drj（1）r 構造任意兩點間最多可經(jīng)過3個中間點到達的最短距離矩陣 D（2）= dij（2）2010/03-第6章 圖與網(wǎng)絡分析-

11、21-其中 dij（3）= min dir（2）+ drj（2） S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0D（3）=irjdir（2）drj（2）r 構造任意兩點間最多可經(jīng)過7個中間點到達的最短距離矩陣 D（3）= dij（3）2010/03-第6章 圖與網(wǎng)絡分析-22-說明：一般，對于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1

12、） ，k=0，1，2，3， 最多可經(jīng)過2k-1個中間點： 其數(shù)列為 0，1，3，7，15，31， 2k-1， 收斂條件：當 D（k+1）= D（k）時，計算結束；設網(wǎng)絡中有p個點，即有p-2個中間點，則 2k-1-1 p-2 2k-1 k-1log2 (p-1) k Klog2(p-1)+1，計算到 k=lg(p-1)/lg2 +1時，收斂，計算結束。2010/03-第6章 圖與網(wǎng)絡分析-23- 例：有7個村鎮(zhèn)要聯(lián)合建立一所小學，已知各村鎮(zhèn)小學生的人數(shù)大致為S30人， A40人，B20人，C15人，D35人，E25人， T50人。問：學校應建在那一個地點，可使學生總行程最少？ S A B C

13、D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0L=30 40 20 15 35 25 50人數(shù)= 1035 910 865 1485T解：2010/03-第6章 圖與網(wǎng)絡分析-24-6.4 中國郵路問題問題：一名郵遞員從郵局出發(fā)，試選擇一條最短的投遞路線？v1v2v3v4v5v6v8v7v9v10v11v12v13郵局444551241254474222010/03-第6章 圖與網(wǎng)絡分析-25-2

14、010/03-第6章 圖與網(wǎng)絡分析-26-奇點：圖中次為奇數(shù)的點稱為奇點。偶點：圖中次為偶數(shù)的點稱為偶點。結論：最短投遞路線應具有下述特征： 若圖中所有的點均為偶點，則可不重復走遍所有街道； 重復走的路線長度應不超過所在回路總長度的一半。2010/03-第6章 圖與網(wǎng)絡分析-27-v1v2v3v4v5v6v8v7v9v10v11v12v13郵局44455124125447422投遞距離：L=60+18=782010/03-第6章 圖與網(wǎng)絡分析-28-6.5 網(wǎng)絡最大流問題一、網(wǎng)絡最大流中有關概念 有向圖：含有以箭頭指示方向的邊的網(wǎng)絡圖。 ?。河邢驁D上的邊稱為弧。用（vi,vj）表示。 弧的容量

15、：弧上通過負載的最大能力，簡稱容量。以cij表示。 流：加在網(wǎng)絡每條弧上的一組負載量，以fij表示。 可行流：能夠通過網(wǎng)絡的負載量，通常應滿足兩個條件： 容量限制條件：對所有的弧，0 fijcij 中間點平衡條件：對任何一個中間點，流入量=流出量 發(fā)點、收點、中間點：流的起源點稱發(fā)點，終到點稱收點，其余的點稱中間點。 最大流；能夠通過網(wǎng)絡的最大流量。 割集：一組弧的集合，割斷這些弧，能使流中斷。簡稱割。2010/03-第6章 圖與網(wǎng)絡分析-29-8(8)v1vsv2v3v4vt7(5)9(4)9(9)2(0)6(1)5(5)10(8)(0,+)(vs,2)(v2,2)(v1,2)(v3,1)(

16、v4,1)5(4)cijfij2010/03-第6章 圖與網(wǎng)絡分析-30- 割的容量：割集中各弧的容量之和。 最小割：所有割集中容量之和為最小的一個割集。 前向弧+：一條發(fā)點到收點鏈中，由發(fā)點指向收點的弧，又稱正向弧。 后向弧-：一條發(fā)點到收點鏈中，由收點指向發(fā)點的弧，又稱逆向弧。 增廣鏈：由發(fā)點到收點之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij0，則稱這樣的鏈為增廣鏈。定理：網(wǎng)絡的最大流量等于它的最小割集的容量。定理：當網(wǎng)絡中不存在任何增廣鏈時，則網(wǎng)絡達到最大流狀態(tài)。二、兩個定理2010/03-第6章 圖與網(wǎng)絡分析-31-st6(4)5(3)4(4)8(7)設有如下增廣鏈：f=1

17、該網(wǎng)絡沒有達到最大流狀態(tài)。2010/03-第6章 圖與網(wǎng)絡分析-32-三、網(wǎng)絡最大流的標號算法(Ford-Fulkerson標號算法)基本思想：尋找增廣鏈，改善流量分布；再重復，直到不 存在任何增廣鏈為止。步驟： 給始點標號：（0，+）從已標號點i出發(fā)，看與其相關聯(lián)的未標號點j上的弧，對+，若有0fijcij，則可對j點標號，記（i, (j)）， 其中 (j)=min (i) ，cij - fij對-，若有0 fji cij，也可對j點標號，記（ i, (j)）， 其中 (j)=min (i) ，fji （注：若有多個可標號點，可任選其中之一。）若標號中斷，則得到最大流狀態(tài)，否則，重復，繼續(xù)標

18、號，至收點得到標號，轉(zhuǎn)。2010/03-第6章 圖與網(wǎng)絡分析-33-當收點得到標號，則沿標號得到的增廣鏈進行流量調(diào)整： 對+，fij = fij + (t) 對-，fij = fij - (t) 其余弧上的流量不變。 重復上述過程。 最小割集：已標號點集合與未標號點集合相連接的弧中， 流量=容量的弧。2010/03-第6章 圖與網(wǎng)絡分析-34-8(8)v1vsv2v3v4vt7(6)9(5)9(9)2(0)6(0)5(5)10(9)5(3)(0,+)(vs,1)(v2,1)(v1,1)最大流量：fmax=14最小割集：(v3, vt), (v2, v4)2010/03-第6章 圖與網(wǎng)絡分析-35-6.6 網(wǎng)絡模型的實