運(yùn)籌學(xué),趙明霞 山西大學(xué)經(jīng)濟(jì)與管理學(xué)院,1,第八章 圖與網(wǎng)絡(luò)分析,圖與網(wǎng)絡(luò)的基本概念 樹 最短路問題 最大流問題 最小費(fèi)用最大流問題,2,柯尼斯堡七橋問題,歐拉回路：經(jīng)過每邊且僅一次 厄尼斯堡七橋問題、郵路問題 哈密爾頓回路：經(jīng)過每點(diǎn)且僅一次 貨郎擔(dān)問題、快遞送貨問題,3,第一節(jié) 圖與網(wǎng)絡(luò)的基本概念,圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 例如：在一個(gè)人群中，對相互認(rèn)識這個(gè)關(guān)系我們可以用圖來表示，圖8.1就是一個(gè)表示這種關(guān)系的圖。,4,描述對象之間關(guān)系， 研究特定關(guān)系之間的內(nèi)在規(guī)律， 圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。,5,如果我們把上面例子中的“相互認(rèn)識”關(guān)系改為“認(rèn)識” 的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。,6,無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G =（V，E）。 有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D =（V，A）。 無向圖是有向圖的基礎(chǔ)圖G(D) 有限圖 無限圖,7,G=(V,E) 關(guān)聯(lián)邊(m)：ei 端（頂）點(diǎn)(n)：vi, vj 點(diǎn)相鄰(同一條邊)： v1, v3 邊相鄰(同一個(gè)端點(diǎn))：e2, e3 環(huán)：e1 多重邊： e4, e5,8,簡單圖：無環(huán)無多重邊 多重圖：多重邊,完全圖：每一對頂點(diǎn)間都有邊（?。┫噙B的簡單圖,9,次（d）：結(jié)點(diǎn)的關(guān)聯(lián)邊數(shù)目 d(v3)=4，偶點(diǎn) d(v2)=3，奇點(diǎn) d(v1)=4 d(v4)=1，懸掛點(diǎn) e6, 懸掛邊 d(v5)=0，孤立點(diǎn),出次：d+(vi) 入次：d-(vi) d (vi) = d+(vi) + d-(vi),定理1 頂點(diǎn)次數(shù)總和等于邊數(shù)的兩倍。 定理2 次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。,10,若 ,則G是G的子圖，G是G的母圖 若 ,則G是G的真子圖， 若 ,則G是G的支撐（生成）圖。,11,鏈：點(diǎn)邊交替序列 閉鏈：v1 v2 v3 v4 v1 開鏈：v1 v2 v3 邊不同，簡單鏈：v3 v4 v5v1v6v5 邊不同且結(jié)點(diǎn)不同，初等鏈：v1 v2 v3 v4 v5v6 圈：閉鏈，且至少有3個(gè)不同結(jié)點(diǎn)，v2 v3 v4 v2 初等圈：初等閉鏈，v1 v2 v3 v4 v1,12,路：有向圖：弧的方向與鏈的方向一致 開路:v1v2v4v5 回路：第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同。v1v2v4v5v1,13,連通圖：若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖。 賦權(quán)圖：對一個(gè)圖的每一條邊（弧）(vi,vj)，相應(yīng)地有一個(gè)數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。 網(wǎng)絡(luò)：賦權(quán)連通圖 無向圖：開鏈即開路，閉鏈即回路 有向圖：弧的方向與鏈的方向一致。,14,柯尼斯堡七橋問題,歐拉回路：經(jīng)過每邊且僅一次 厄尼斯堡七橋問題、郵路問題 充要條件：無向圖中無奇點(diǎn)，有向圖每個(gè)頂點(diǎn)出次等于入次,15,16,第二節(jié) 樹,樹是圖論中的重要概念，所謂樹就是一個(gè)無圈的連通圖。,圖8-4中，(a)就是一個(gè)樹，而(b)因?yàn)閳D中有圈所以就不是樹， (c)因?yàn)椴贿B通所以也不是樹。,16,樹的基本性質(zhì) 任意兩點(diǎn)間有且僅有一條鏈 不相鄰兩點(diǎn)間添加一條邊，有且僅有一個(gè)圈 任意去掉一條邊，得不連通圖. 存在懸掛點(diǎn) m=n-1,17,18,生成（支撐）樹,若 ,則G是G的支撐（生成）樹。,18,19,1、破圈算法 步驟： （1）在給定的賦權(quán)的連通圖上任找一個(gè)圈。 （2）在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。 （3）如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小樹，否則返回第1步。,最小生成樹問題就是指在一個(gè)賦權(quán)的連通的無向圖G中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。,19,20,例8.1,20,2、避圈算法 步驟： （1）任找一個(gè)點(diǎn)S，其余各點(diǎn)就是 。 （2）在連接S與 的所有邊中，選擇權(quán)數(shù)最小的邊(i, k)； （3）將最小邊(i, k)的另一個(gè)端點(diǎn)移入S； （4）若 則停止，否則返回（2）。,21,22,例8.1,22,有向樹：不考慮方向時(shí)是樹 根樹（外向樹）：只有一個(gè)頂點(diǎn)入次為0，其余頂點(diǎn)入次為1 根：入次為0的頂點(diǎn) 葉：出次為0的頂點(diǎn) 分支點(diǎn) 層次：根到頂點(diǎn)的長度,23,m叉樹：每個(gè)頂點(diǎn)的出次小于等于m 完全m叉樹：每個(gè)頂點(diǎn)的出次等于m或0,24,霍夫曼樹：最優(yōu)二叉樹,25,第三節(jié) 最短路問題,最短路問題： 對一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)Vs(起點(diǎn))和Vt（終點(diǎn)）找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。,26,適用于：每條?。ㄟ叄┑馁x權(quán)數(shù)wij 0 優(yōu)點(diǎn)：能夠求出某點(diǎn)至各點(diǎn)的最短路 基本思想： T(j) （tentative label）從始點(diǎn)s到j(luò)點(diǎn)的最短路長上界，稱為試探性標(biāo)號; P(j) （permanent label）從始點(diǎn)s到j(luò)點(diǎn)的最短路長，稱為永久性標(biāo)號.,一、狄氏標(biāo)號法（Dijkstra算法）,27,例8-9,基本步驟 標(biāo)號T(j)P(j),28,29,最長路問題 例8-10（7-9）設(shè)某臺新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表。試確定今后5年內(nèi)的更新策略，使總收益最大。,30,31,網(wǎng)絡(luò)中心（r點(diǎn)）,例8-11 某連鎖企業(yè)有6個(gè)銷售點(diǎn)，問倉庫應(yīng)建在哪個(gè)地點(diǎn)，可使各銷售點(diǎn)離倉庫較近？,32,33,各點(diǎn)間的最短距離,二、Floyd算法,34,例8-12 求任意兩點(diǎn)間的最短路,35,36,37,38,容量網(wǎng)絡(luò)(網(wǎng)絡(luò))：N=(V, A, c) 或 N=(V, A)，最大流量cij = c(i,j) 網(wǎng)絡(luò)流： 可行流：s發(fā)點(diǎn)，t收點(diǎn) 可行流流量：,第四節(jié) 最大流問題,39,割(截)集： S中各點(diǎn)聯(lián)通，S 中各點(diǎn)聯(lián)通 始點(diǎn)在S，終點(diǎn)在S 的集合，稱為一個(gè)分離發(fā)點(diǎn)s和收點(diǎn)t的割集，（S,S） 割集容量： 最小割：最小的割集容量,40,定理8-10：網(wǎng)絡(luò)任一可行流的流量恒不超過任一割集的容量。 定理8-11：最大流 = 最小割,41,增廣（容）鏈： 為從發(fā)點(diǎn)s到收點(diǎn)t的一條鏈，且前向弧均非飽和，后向弧均非零流。 最大流：流量最大的可行流。 可行流為最大流的充要條件：不存在從s到t的增廣鏈,42,（一）線性(整數(shù))規(guī)劃法,43,例8-13,44,（二）網(wǎng)絡(luò)分析法 增廣鏈調(diào)整法,45,FordFulkerson標(biāo)號法 基本思想：先確定一個(gè)初始可行流，再找增容鏈，調(diào)整流量，直到找不到增容鏈為止。雙標(biāo)號（i, b(j)），b(j)當(dāng)前最大可調(diào)容量 運(yùn)算步驟： 發(fā)點(diǎn)s標(biāo)號（0, ）； 給所有相鄰點(diǎn)標(biāo)號 正向弧且 ，則 j 標(biāo)號（i, b(j)） ，則 j 不標(biāo)號 逆向弧且 ，則 j 標(biāo)號（-i, b(j)） 檢查標(biāo)號 調(diào)整量,46,例8-13,（1）計(jì)算機(jī)編程,47,（2）手算,f*=11,48,49,50,最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)N=(V,A,c,d)，對每一條?。╥，j），除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用dij，要求一個(gè)最大流f，并使得總運(yùn)送費(fèi)用最小。,先求出此網(wǎng)絡(luò)圖中的最大流量f。 在最大流量f的所有解中，找出一個(gè)最小費(fèi)用的解,（一）線性(整數(shù))規(guī)劃法,第五節(jié) 最小費(fèi)用最大流問題,51,例8-15,第一步,第二步,52,對偶網(wǎng)絡(luò)法：N=(V,A)，N=(V,A,w) xij = 0, 0 xij cij, xij = cij，,（二）網(wǎng)絡(luò)分析法,53,定理8-7：對偶網(wǎng)絡(luò)中的最短路必是原網(wǎng)絡(luò)的最小費(fèi)用增容鏈。 定理8-8：在流量為f的最小費(fèi)用流上，按最小費(fèi)用增容鏈調(diào)整流量后，仍為新流量上的最小費(fèi)用流。 基本思想：找出對偶網(wǎng)絡(luò)的最短路，沿此路調(diào)整流量，直到最大流量。 運(yùn)算步驟,54,55,作 業(yè),8.1 8.6 8.8 8.10 8.17,56,