運(yùn)籌學(xué)錢老師課件or

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

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

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

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

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

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

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

8、的D（Dijkstra）氏標(biāo)號(hào)法2472010/03-第6章 圖與網(wǎng)絡(luò)分析-17-SABCDET25241431755702447891413594 最短路線：S AB E D T最短距離：Lmin=132010/03-第6章 圖與網(wǎng)絡(luò)分析-18-2求任意兩點(diǎn)間最短距離的矩陣算法 構(gòu)造任意兩點(diǎn)間直接到達(dá)的最短距離矩陣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）= 構(gòu)造任意兩點(diǎn)間直接到達(dá)、或者最多經(jīng)過(guò)1個(gè)中間點(diǎn)到達(dá)的最短距離矩陣D

9、（1）= dij（1）2010/03-第6章 圖與網(wǎng)絡(luò)分析-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)絡(luò)分析-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 構(gòu)造任意兩點(diǎn)間最多可經(jīng)過(guò)3個(gè)中間點(diǎn)到達(dá)的最短距離矩陣 D（2）= dij（2）2010/03-第6章 圖與網(wǎng)絡(luò)分析-

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 構(gòu)造任意兩點(diǎn)間最多可經(jīng)過(guò)7個(gè)中間點(diǎn)到達(dá)的最短距離矩陣 D（3）= dij（3）2010/03-第6章 圖與網(wǎng)絡(luò)分析-22-說(shuō)明：一般，對(duì)于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1

12、） ，k=0，1，2，3， 最多可經(jīng)過(guò)2k-1個(gè)中間點(diǎn)： 其數(shù)列為 0，1，3，7，15，31， 2k-1， 收斂條件：當(dāng) D（k+1）= D（k）時(shí)，計(jì)算結(jié)束；設(shè)網(wǎng)絡(luò)中有p個(gè)點(diǎn)，即有p-2個(gè)中間點(diǎn)，則 2k-1-1 p-2 2k-1 k-1log2 (p-1) k Klog2(p-1)+1，計(jì)算到 k=lg(p-1)/lg2 +1時(shí)，收斂，計(jì)算結(jié)束。2010/03-第6章 圖與網(wǎng)絡(luò)分析-23- 例：有7個(gè)村鎮(zhèn)要聯(lián)合建立一所小學(xué)，已知各村鎮(zhèn)小學(xué)生的人數(shù)大致為S30人， A40人，B20人，C15人，D35人，E25人， T50人。問(wèn)：學(xué)校應(yīng)建在那一個(gè)地點(diǎn)，可使學(xué)生總行程最少？ 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)絡(luò)分析-24-6.4 中國(guó)郵路問(wèn)題問(wèn)題：一名郵遞員從郵局出發(fā)，試選擇一條最短的投遞路線？v1v2v3v4v5v6v8v7v9v10v11v12v13郵局444551241254474222010/03-第6章 圖與網(wǎng)絡(luò)分析-25-2

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

15、：弧上通過(guò)負(fù)載的最大能力，簡(jiǎn)稱容量。以cij表示。 流：加在網(wǎng)絡(luò)每條弧上的一組負(fù)載量，以fij表示。 可行流：能夠通過(guò)網(wǎng)絡(luò)的負(fù)載量，通常應(yīng)滿足兩個(gè)條件： 容量限制條件：對(duì)所有的弧，0 fijcij 中間點(diǎn)平衡條件：對(duì)任何一個(gè)中間點(diǎn)，流入量=流出量 發(fā)點(diǎn)、收點(diǎn)、中間點(diǎn)：流的起源點(diǎn)稱發(fā)點(diǎn)，終到點(diǎn)稱收點(diǎn)，其余的點(diǎn)稱中間點(diǎn)。 最大流；能夠通過(guò)網(wǎng)絡(luò)的最大流量。 割集：一組弧的集合，割斷這些弧，能使流中斷。簡(jiǎn)稱割。2010/03-第6章 圖與網(wǎng)絡(luò)分析-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)絡(luò)分析-30- 割的容量：割集中各弧的容量之和。 最小割：所有割集中容量之和為最小的一個(gè)割集。 前向弧+：一條發(fā)點(diǎn)到收點(diǎn)鏈中，由發(fā)點(diǎn)指向收點(diǎn)的弧，又稱正向弧。 后向弧-：一條發(fā)點(diǎn)到收點(diǎn)鏈中，由收點(diǎn)指向發(fā)點(diǎn)的弧，又稱逆向弧。 增廣鏈：由發(fā)點(diǎn)到收點(diǎn)之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij0，則稱這樣的鏈為增廣鏈。定理：網(wǎng)絡(luò)的最大流量等于它的最小割集的容量。定理：當(dāng)網(wǎng)絡(luò)中不存在任何增廣鏈時(shí)，則網(wǎng)絡(luò)達(dá)到最大流狀態(tài)。二、兩個(gè)定理2010/03-第6章 圖與網(wǎng)絡(luò)分析-31-st6(4)5(3)4(4)8(7)設(shè)有如下增廣鏈：f=1

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

18、號(hào)，至收點(diǎn)得到標(biāo)號(hào)，轉(zhuǎn)。2010/03-第6章 圖與網(wǎng)絡(luò)分析-33-當(dāng)收點(diǎn)得到標(biāo)號(hào)，則沿標(biāo)號(hào)得到的增廣鏈進(jìn)行流量調(diào)整： 對(duì)+，fij = fij + (t) 對(duì)-，fij = fij - (t) 其余弧上的流量不變。 重復(fù)上述過(guò)程。 最小割集：已標(biāo)號(hào)點(diǎn)集合與未標(biāo)號(hào)點(diǎn)集合相連接的弧中， 流量=容量的弧。2010/03-第6章 圖與網(wǎng)絡(luò)分析-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)絡(luò)分析-35-6.6 網(wǎng)絡(luò)模型的實(shí)