圖和網(wǎng)絡(luò)模型基本概念

1、1圖與網(wǎng)絡(luò)的根本概念 圖論中圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 例如：在一個人群中，對相互認識這個關(guān)系我們可以用圖來表示，圖11-1就是一個表示這種關(guān)系的圖。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5圖11-11 1圖與網(wǎng)絡(luò)的根本概念 當然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況以下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙等七人的相互認識關(guān)系我們也可以用圖11-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。(v1)趙(v2)錢孫(v3)李(v4)周

2、(v5)吳(v6)陳(v7)e2e1e3e4e5圖11-221圖與網(wǎng)絡(luò)的根本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳圖11-3 如果我們把上面例子中的“相互認識關(guān)系改為“認識 的關(guān)系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。圖11-3就是一個反映這七人“認識關(guān)系的圖。相互認識用兩條反向的弧表示。3 1圖與網(wǎng)絡(luò)的根本概念無向圖： 由點和邊構(gòu)成的圖，記作G=V，E。有向圖： 由點和弧構(gòu)成的圖，記作D=V，A。連通圖： 對無向圖G，假設(shè)任何兩個不同

3、的點之間，至少存在一條鏈，那么G為連通圖?；芈罚?假設(shè)路的第一個點和最后一個點相同，那么該路為回路。賦權(quán)圖： 對一個無向圖G的每一條邊(vi,vj)，相應(yīng)地有一個數(shù)wij，那么稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。網(wǎng)絡(luò)： 在賦權(quán)的有向圖D中指定一點，稱為發(fā)點，指定另一點稱為收點，其它點稱為中間點，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就稱為網(wǎng)絡(luò)。42最短路問題最短路問題：對一個賦權(quán)的有向圖D中的指定的兩個點Vs和Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。一、求

4、解最短路的Dijkstra算法(雙標號法步驟：1.給出點V1以標號(0,s)2.找出已標號的點的集合I，沒標號的點的集合J以及弧的集合3. 如果上述弧的集合是空集，那么計算結(jié)束。如果vt已標號lt,kt，那么 vs到vt的距離為lt，而從 vs到vt的最短路徑，那么可以從kt 反向追蹤到起點vs 而得到。如果vt 未標號，那么可以斷言不存在從 vs到vt的有向路。如果上述的弧的集合不是空集，那么轉(zhuǎn)下一步。4. 對上述弧的集合中的每一條弧，計算 sij=li+cij 。在所有的 sij中，找到其值為最小的弧。不妨設(shè)此弧為Vc,Vd，那么給此弧的終點以雙標號scd,c,返回步驟2。52最短路問題

5、例1 求以下圖中v1到v6的最短路解：采用Dijkstra算法，可解得最短路徑為v1 v3 v4 v6 各點的標號圖如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v462最短路問題 例2 電信公司準備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？以下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度單位：公里。 解：這是一個求無向圖的最短路的問題。可以把無向圖的每一邊vi,vj都用方向相反的兩條弧vi,vj和vj,vi代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無

6、向圖中用Dijkstra算法來求解。只要在算法中把從已標號的點到未標號的點的弧的集合改成已標號的點到未標號的點的邊的集合即可。 V1 （甲地）15176244431065v2V7 （乙地）v3v4v5v672最短路問題例2最終解得：最短路徑v1 v3 v5 v6 v7，每點的標號見以下圖0,s V1 甲地1517624431065(13,3) v2 (22,6)V7 乙地V5(14,3)V6(16,5) V3(10,1) V4(18,5)82最短路問題 例3 設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購置新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費，當然新

7、設(shè)備的維修費用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費，但維修費用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的方案，使得五年內(nèi)購置費用和維修費用總的支付費用最小。 ：設(shè)備每年年初的價格表 設(shè)備維修費如下表年份12345年初價格1111121213使用年數(shù)0-11-22-33-44-5每年維修費用568111892最短路問題例3的解： 將問題轉(zhuǎn)化為最短路問題，如以下圖： 用vi表示“第i年年初購進一臺新設(shè)備,弧vi,vj表示第i年年初購進的設(shè)備一直使用到第j年年初。把所有弧的權(quán)數(shù)計算如下表：v1v2v3v4v5v612345611622304159216223041317233141723518610

8、2最短路問題 (繼上頁) 把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。 最終得到以下圖，可知，v1到v6的距離是53，最短路徑有兩條： v1 v3 v6和 v1 v4 v6v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)113最小生成樹問題樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。 圖11-11中，(a)就是一個樹，而(b)因為圖中有圈所以就不是樹， (c)因為不連通所以也不是樹

9、。圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)123最小生成樹問題 給了一個無向圖G=(V,E)，我們保存G的所有點，而刪掉局部G的邊或者說保存一局部G的邊，所獲得的圖G，稱之為G的生成子圖。在圖11-12中，(b)和(c)都是(a)的生成子圖。 如果圖G的一個生成子圖還是一個樹，那么稱這個生成子圖為生成樹，在圖11-12中，(c)就是(a)的生成樹。 最小生成樹問題就是指在一個賦權(quán)的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小。圖11-12(a)(b)(c)133最小生成樹問

10、題一、求解最小生成樹的破圈算法算法的步驟：1、在給定的賦權(quán)的連通圖上任找一個圈。2、在所找的圈中去掉一個權(quán)數(shù)最大的邊如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，那么任意去掉其中一條。3、如果所余下的圖已不包含圈，那么計算結(jié)束，所余下的圖即為最小生成樹，否那么返回第1步。143最小生成樹問題例4 用破圈算法求圖a中的一個最小生成樹v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31

11、(a)(b)(c)(d)(e)(f)圖11-13153最小生成樹問題 例5、某大學(xué)準備對其所屬的7個學(xué)院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途徑如以下圖，圖中v1,v7 表示7個學(xué)院辦公室，請設(shè)計一個網(wǎng)絡(luò)能聯(lián)通7個學(xué)院辦公室，并使總的線路長度為最短。 解：此問題實際上是求圖11-14的最小生成樹，這在例4中已經(jīng)求得，也即按照圖11-13的(f)設(shè)計，可使此網(wǎng)絡(luò)的總的線路長度為最短，為19百米。 “管理運籌學(xué)軟件有專門的子程序可以解決最小生成樹問題。v1331728541034v7v6v5v4v2v3圖11-14164最大流問題最大流問題：給一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超

12、過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。一、最大流的數(shù)學(xué)模型 例6 某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這個網(wǎng)絡(luò)的一局部如以下圖所示。由于管道的直徑的變化，它的各段管道vi,vj的流量cij容量也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地 v7運送石油，問每小時能運送多少加侖石油？v563522241263v1v2v7v4v3v6圖11-26174最大流問題 我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，那么有：184最大流問題 在這個線性規(guī)劃模型中，其約束條

13、件中的前6個方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點的流出量必須等于收點的總流入量；其余的點稱之為中間點，它的總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 fij稱之為可行流，即線性規(guī)劃的可行解，可行流中一組流量最大也即發(fā)出點總流出量最大的稱之為最大流即線性規(guī)劃的最優(yōu)解。 我們把例6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌學(xué)軟件，馬上得到以下的結(jié)果：f12=5，f14=5，f23=2，f25=3，f43=2，f4

14、6=1，f47=2，f35=2，f36=2，f57=5，f67=3。最優(yōu)值最大流量=10。19 4最大流問題二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進。為省去弧的方向，如以下圖: (a)和(b)、(c)和(d)的意義相同。 用以上方法對例6的圖的容量標號作改進，得以下圖vivjvivjcij0ab cijcijvivjcjicvivj cij cjid63522241263v1v2v5v7v4v3v60000000000020 4最大流問題 求最大流的根本算法1找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，那么已經(jīng)求得最大流。2找出這

15、條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。3在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的逆流容量pf，返回步驟1。 用此方法對例6求解： 第一次迭代：選擇路為v1 v4 v7 ?；?v4 , v7 的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如以下圖：63522241263v1v2v5v7v4v3v6000000000004202214最大流問題 第二次迭代：選擇路為v1 v2 v5 v7 。弧 v2 , v5 的順流容量為3，決定了pf=3，改進的網(wǎng)絡(luò)流量圖如以下圖： 第三次迭代：選擇路為v1 v4 v6 v7 ?；?v4 , v6 的順流容量為1，

16、決定了pf=1，改進的網(wǎng)絡(luò)流量圖如以下圖：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v60000004202203333301322 第四次迭代：選擇路為v1 v4 v3 v6 v7 。弧 v3 , v6 的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如以下圖： 第五次迭代：選擇路為v1 v2 v3 v5 v7 ?；?v2 , v3 的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如以下圖：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v6101

17、20203335012023131500202054最大流問題23 經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路上的每一條弧順流容量都大于零，運算停止。得到最大流量為10。 最大流量圖如以下圖：22v1v2v5v7v4v3v61235223554最大流問題 “管理運籌學(xué)軟件中還有專門的子程序用于解決最大流問題。245最小費用最大流問題 最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，對每一條弧vi,vj，除了給出容量cij外，還給出了這條弧的單位流量的費用bij，要求一個最大流F，并使得總運送費用最小。一、最小費用最大流的數(shù)學(xué)模型 例7 由于輸油管道的長短不一，所以在例6中每段管道 v

18、i,vj 除了有不同的流量限制cij外，還有不同的單位流量的費用bij ，cij的單位為萬加侖/小時， bij的單位為百元/萬加侖。如圖。從采地 v1向銷地 v7運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最?。壳蟪鲎畲罅髁亢妥钚≠M用。(6,6)(3,4)(5,7)(2,5)(2,4)2,3(4,4)(1,3)(2,8)3,2v1v2v5v7v4v3v6(6,3)255最小費用最大流問題 這個最小費用最大流問題也是一個線性規(guī)劃的問題。 解：我們用線性規(guī)劃來求解此題，可以分兩步走。 第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過管理運籌學(xué)軟件已經(jīng)獲得結(jié)果。

19、 第二步，在最大流量F的所有解中，找出一個最小費用的解，我們來建立第二步中的線性規(guī)劃模型如下： 仍然設(shè)弧vi,vj上的流量為fij，這時網(wǎng)絡(luò)中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標函數(shù)顯然是求其流量的最小費用 。 由此得到線性規(guī)劃模型如下：265最小費用最大流問題 275最小費用最大流問題 用管理運籌學(xué)軟件，可求得如下結(jié)果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最優(yōu)值(最小費用)=145。對照前面例6的結(jié)

20、果，可對最小費用最大流的概念有一個深刻的理解。 如果我們把例7的問題改為：每小時運送6萬加侖的石油從采地v1到銷地v7最小費用是多少？應(yīng)怎樣運送？這就變成了一個最小費用流的問題。一般來說，所謂最小費用流的問題就是：在給定了收點和發(fā)點并對每條弧(vi,vj)賦權(quán)以容量cij及單位費用bij的網(wǎng)絡(luò)中，求一個給定值f的流量的最小費用，這個給定值f的流量應(yīng)小于等于最大流量F，否那么無解。求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模型中的約束條件中的發(fā)點流量F改為f即可。在例6中只要把f12+f14=F改為f12+f14=f=6得到了最小費用流的線性規(guī)劃的模型了。285最小費用最大流問題二、

21、最小費用最大流的網(wǎng)絡(luò)圖論解法對網(wǎng)絡(luò)上弧vi,vj的cij,bij的表示作如下改動，用(b)來表示(a)。用上述方法對例7中的圖形進行改進，得圖如下頁：vivjvivjcij,bij 0,-bij abcij,bij cij,bij vivjcji,bji cij,bij vivjcji,bji 0,-bji)0,-bji)cd295最小費用最大流問題 求最小費用最大流的根本算法 在對弧的標號作了改進的網(wǎng)絡(luò)圖上求最小費用最大流的根本算法與求最大流的根本算法完全一樣，不同的只是在步驟1中要選擇一條總的單位費用最小的路，而不是包含邊數(shù)最小的路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2

22、,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖11-28305最小費用最大流問題用上述方法對例7求解： 第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后總流量為1，總費用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7

23、)(1,-4)（0,-3）圖11-29315最小費用最大流問題第二次迭代：找到最短路v1 v4 v7。第二次迭代后總流量為3，總費用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-30325最小費用最大流問題第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為5，總費用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）圖11-31335最小費用最大流問題第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后總流量為6，總費用72。(6,6)(3,4)(4,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v