《數(shù)據(jù)模型與決策(第二版)》第七章圖及網(wǎng)絡(luò)概述

1、第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 了解如何用圖論的觀點(diǎn)去分析解決簡(jiǎn)單的實(shí)際問題。 要求掌握?qǐng)D的基本概念；掌握用標(biāo)號(hào)法求有向圖與無(wú)向圖中從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的最短路；掌握可行流、可行流的流量、最大流及增廣鏈的概念，了解求最大流的Ford-Fulkerson標(biāo)號(hào)法。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 7.1 圖的基本概念 7.2 最短路問題 7.3 網(wǎng)絡(luò)最大流問題 7.4 最小費(fèi)用網(wǎng)絡(luò)最大流問題第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 下圖表示6個(gè)球隊(duì)之間賽事關(guān)系。其中點(diǎn)a,b,c,d,e,f分別表示6個(gè)球隊(duì)，兩點(diǎn)的連結(jié)表示兩球隊(duì)之間的賽事關(guān)系。因此，從圖中可反

2、映出a球隊(duì)分別與b,c,d球隊(duì)有賽事；b球隊(duì)還與c,e球隊(duì)，d球隊(duì)還與e球隊(duì)有賽事，而f均不與球隊(duì)a,b,c,d,e有賽事。綜上，這6個(gè)球隊(duì)之間的關(guān)系可用圖(a)來(lái)表示，也可用圖(b)來(lái)反映。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 圖7-2是一張石油流向的管網(wǎng)示意圖，v1點(diǎn)表示石油開采地，v7點(diǎn)表示石油的匯集站，v2，v3，v4，v5，v6表示可供選擇的石油流動(dòng)加壓站(中間站)，箭頭表示石油流向，箭線旁的數(shù)字表示管線的長(zhǎng)度。現(xiàn)在要從v1地調(diào)運(yùn)石油到v7地，怎樣選擇管線可使路徑最短？第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)第七章

3、圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 無(wú)向圖： 一般地，設(shè)V(v1，v2,.vp)是p個(gè)點(diǎn)的集合，Ee1，e2，eq是q條邊的集合，其中 eivi，vjvj,vi， vi,vjV 把由V和E組成的圖形稱為無(wú)向圖，記為G(V，E)。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 有向圖： 如果一個(gè)圖是由點(diǎn)和弧所組成，則稱此圖為有向圖，記為D(V，A)。其中Vv1,v2,.,vp，Aa1,a2,.aq，aij=(vi,vj)(vj,vi)，vi,vjV，并稱aij是以vi為始點(diǎn)，vj為終點(diǎn)的弧， i, j 的順序是不能顛倒的，圖中弧的方向用箭頭標(biāo)識(shí)。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第

4、二版) 連通圖：如果圖G中任何兩頂點(diǎn)間至少有一條鏈，則稱G是連通圖，否則為不連通。 賦權(quán)圖：無(wú)向圖G（或有向圖D）中，如果每條邊(弧)都被賦予一個(gè)權(quán)數(shù)ij，則稱G（或D）為賦權(quán)無(wú)向圖(有向圖)，記為G(V，E，W)(或D(V，A，W)。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 鏈：對(duì)于無(wú)向圖G(V，E)，稱某頂點(diǎn)和邊交替的序列vi1,ei1,vi2,ei2,.vi(t-1),ei(t-1),vit為連接vi1和vit的一條鏈，簡(jiǎn)記為vi1，vi2，vit.其中eik(eik，ei(k+1)，k1，2，t-1。 路：在有向圖D(V，A)中，稱鏈vi1，vi2，.，vit為一條以vi1為始

5、點(diǎn)，通向終點(diǎn)vit的路。如果vi1=vit，則稱之為回路。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 7.1 圖的基本概念 7.2 最短路問題 7.3 網(wǎng)絡(luò)最大流問題 7.4 最小費(fèi)用網(wǎng)絡(luò)最大流問題第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 7.2.1 問題的提出 7.2.2 Dijkstra算法（雙標(biāo)號(hào)法） 7.2.3 最短路問題的應(yīng)用 7.2.4 無(wú)向圖上的Dijkstra算法第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 設(shè)一個(gè)簡(jiǎn)單有向圖D=(V，A)，對(duì)其中指定的兩個(gè)點(diǎn)Vs和Vt找到一條從Vs到Vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最?。ɑ〉臋?quán)數(shù)根據(jù)具體問題的要求可以是

6、路程的長(zhǎng)度，成本的花費(fèi)等等），這條路被稱之為從Vs到Vt的最短路，這條路上所有弧的權(quán)數(shù)的總和被稱之為從Vs到Vt的距離。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 雙標(biāo)號(hào)：對(duì)圖中的點(diǎn)Vi賦予兩個(gè)標(biāo)號(hào)（P(Vi)，i）：第一個(gè)標(biāo)號(hào)P(Vi)表示從起點(diǎn)Vs到Vi的最短路的長(zhǎng)度，第二個(gè)標(biāo)號(hào)i表示在Vs到Vi的最短路上Vi前面一個(gè)鄰點(diǎn)的下標(biāo)，即用來(lái)標(biāo)識(shí)路徑，從而可對(duì)終點(diǎn)到始點(diǎn)進(jìn)行反向追蹤，找到Vs到Vt的最短路。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) Dijkstra算法步驟：給起點(diǎn)vs標(biāo)號(hào)（0，s），表示從v1到v1的距離為0，vs為起點(diǎn)。找出已標(biāo)號(hào)的點(diǎn)的集合I，沒標(biāo)號(hào)的點(diǎn)的集合J，

7、求出弧集A=（vi,vj）viI,vjJ，這個(gè)弧集是指所有從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的集合。若上述弧集A=，表明從所有已經(jīng)賦予標(biāo)號(hào)的頂點(diǎn)出發(fā)，不再有這樣的弧，它的另一頂點(diǎn)尚未標(biāo)號(hào)，則計(jì)算結(jié)束。對(duì)于已有標(biāo)號(hào)的頂點(diǎn)，可求得從v1到達(dá)這個(gè)頂點(diǎn)的最短路，對(duì)于沒有標(biāo)號(hào)的頂點(diǎn)，則不存在從v1到達(dá)這個(gè)頂點(diǎn)的路。若弧集A ，轉(zhuǎn)下一步。對(duì)弧集A中的每一條弧(vi,vj)，計(jì)算 Tij= P(Vi)+ij 在所有的Tij中，找到其值為最小的弧，假設(shè)為（vs,vt）。需要注意的是，若上述Tij值為最小的弧有多條，且這些弧的第二個(gè)頂點(diǎn)vj相同，則表明存在多條最優(yōu)路徑，因此，vj應(yīng)得到多個(gè)雙標(biāo)號(hào)。給?。╲s,vt）的終點(diǎn)

8、vt賦予雙標(biāo)號(hào)（P(Vt)，s）。返回步驟（2）。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 求v1到其余各點(diǎn)的最短路第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 如圖，v1點(diǎn)表示石油開采地，v7點(diǎn)表示石油的匯集站，箭線旁的數(shù)字表示管線的長(zhǎng)度，現(xiàn)在要從v1地調(diào)運(yùn)石油到v7地，怎樣選擇管線可使路徑最短？第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 設(shè)備更新問題。某公司在5年期內(nèi)都要用到某臺(tái)設(shè)備，要在今后5年的年初作出購(gòu)買新設(shè)備或繼續(xù)使用舊設(shè)備的決策。若購(gòu)新的，要支付購(gòu)置費(fèi)；若繼續(xù)用舊的，則要支付維修費(fèi)。這臺(tái)設(shè)備在5年期內(nèi)每年的購(gòu)價(jià)和維

9、修費(fèi)用估計(jì)如表7-1所示。試制訂一個(gè)5年之內(nèi)的更新設(shè)備計(jì)劃，使得5年內(nèi)購(gòu)置費(fèi)和維修費(fèi)總的支付費(fèi)用最小。年份年份1 12 23 34 45 5年初購(gòu)年初購(gòu)價(jià)，萬(wàn)價(jià)，萬(wàn)元元1011111212維修費(fèi)，維修費(fèi)，萬(wàn)元萬(wàn)元345811第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)用點(diǎn)vi表示“第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備”，我們加v6點(diǎn)表示第5年年底，從v1,v2,v6之間各畫一條弧，弧（vi,vj）表示在第i年年初購(gòu)進(jìn)的設(shè)備一直使用到第j年年初，即第j-1年年底。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 我們將圖中的每條弧賦予權(quán)數(shù)。對(duì)于?。╲i,vj），它的權(quán)數(shù)為從第i年年初購(gòu)進(jìn)設(shè)備至第j-1年

10、年底更新設(shè)備所花費(fèi)的購(gòu)置費(fèi)及維修費(fèi)的總和，用cij來(lái)表示，第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 無(wú)向圖中的任一條邊vi,vj均可用方向相反的兩條弧（vi,vj）和（vj,vi）來(lái)代替。把原來(lái)的無(wú)向圖變?yōu)橛邢驁D后，即可用上述的Dijkstra算法求解。 也可以直接在原來(lái)的無(wú)向圖上用Dijkstra算法求解。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 7.1 圖的基本概念 7.2 最短路問題 7.3 網(wǎng)絡(luò)最大流問題 7.4 最小費(fèi)用網(wǎng)絡(luò)最大流問題第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 7.3.1 網(wǎng)絡(luò)最大流問題的概述 7.

11、3.2 尋找網(wǎng)絡(luò)最大流的FordFulkerson標(biāo)號(hào)法第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 在圖7-8所示網(wǎng)絡(luò)中，每條弧旁的數(shù)字即為該弧的容量cij，弧的方向就是允許流的方向。現(xiàn)在，要把一批貨物從起點(diǎn)v1運(yùn)到終點(diǎn)v7去，每條弧上通過的貨物總量不能超過這條弧的容量。問：如何安排運(yùn)輸，使得從起點(diǎn)v1運(yùn)到終點(diǎn)v6的總運(yùn)量達(dá)到最大？第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 網(wǎng)絡(luò)：一般地，對(duì)于一個(gè)容量網(wǎng)絡(luò)D，如果點(diǎn)集V中有一發(fā)點(diǎn)記為vs，還有一收點(diǎn)記為vt，其余均為中間點(diǎn)，且對(duì)弧集A的每條弧均賦權(quán)cij 0，則稱這樣的容量網(wǎng)絡(luò)D為帶收

12、發(fā)點(diǎn)的容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 把通過弧(vi,vj)的物運(yùn)量fij稱為通過弧(vi,vj)的流量，所有弧上流量的集F=fij稱為該網(wǎng)絡(luò)D的一個(gè)流。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)兩個(gè)約束條件： 容量約束 節(jié)點(diǎn)流量平衡條件第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 平衡條件表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，對(duì)收發(fā)點(diǎn)來(lái)說：發(fā)點(diǎn)的總流出量=收點(diǎn)的總流入量：對(duì)中間點(diǎn)v1、v2、v3、v4來(lái)說：中間點(diǎn)的總流入量=總流出量。 對(duì)一個(gè)給定的容量網(wǎng)絡(luò)，凡是滿足以上兩個(gè)條件的網(wǎng)絡(luò)流fij都稱為可行流。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第

13、二版) 設(shè)網(wǎng)絡(luò)D(V，A，C)中，有一可行流f=fij，按每條弧上流量的多少，可將弧分為四種類型： 飽和弧fijcij 非飽和弧fijcij 零流弧fij=0 非零流弧fij0第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 設(shè)是網(wǎng)絡(luò)D中從vs到vt的一條鏈，沿此方向上的各弧可分為兩類，一類是與鏈的方向一致的弧稱為正向弧，正向弧的全體記為 ，另一類是與鏈的方向相反的弧，稱為反向弧，反向弧的全體記為 。 增廣鏈：對(duì)于可行流f，是一條從vs到vt的鏈，如果 中的每條弧均為非飽和弧，且 中的每條弧均為非零流弧，則稱鏈?zhǔn)顷P(guān)于f的增廣鏈。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 截集：截集就是研

14、究網(wǎng)絡(luò)流“瓶頸”的一種工具。 截量：截集中所有弧的容量之和稱為該截集的截量。 最小截量最大流定理：最小截量最大流定理：任一網(wǎng)絡(luò)D中，最大流的流量等于最小截集的截量。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版)判斷一個(gè)可行流是否最大流 一是能否找出Vs到Vt的增廣鏈，若能，則說明f不是最大流；否則f就是最大流。 二是看v(f)是否等于最小截量。若等，則f就是最大流，否則就不是最大流。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 標(biāo)號(hào)法的基本思想：從一個(gè)可行流f出發(fā)，由發(fā)點(diǎn)vs開始，對(duì)網(wǎng)絡(luò)D中的每個(gè)頂點(diǎn)進(jìn)行標(biāo)號(hào)，如vt得到標(biāo)號(hào)，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找出一條從s到t 的由標(biāo)號(hào)點(diǎn)及相應(yīng)的

15、弧連接而成的增廣鏈。若無(wú)，則f為所求的最大流；若有，則在增廣鏈上進(jìn)行調(diào)整，改變流量，得一新的可行流f，繼續(xù)尋找相應(yīng)于該可行流的增廣鏈。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 試用Ford-Fulkerson標(biāo)號(hào)法求圖7-11所示的網(wǎng)絡(luò)最大流。第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 7.1 圖的基本概念 7.2 最短路問題 7.3 網(wǎng)絡(luò)最大流問題 7.4 最小費(fèi)用網(wǎng)絡(luò)最大流問題第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 7.4.1 最小費(fèi)用最大流算法 7.4.2 應(yīng)用舉例第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 在給定網(wǎng)絡(luò)D(V，A，C)中，對(duì)每條?。╲i，vj

16、） A，除已給弧容量 外，還給出單位流量的費(fèi)用 。 是D中的可行流，其總費(fèi)用為 。因此，把求可行流量為 ，且使總費(fèi)用b(f)最小的問題稱為最小費(fèi)用流問題，其數(shù)學(xué)模型為： 求使b(f)為最小且流量v(f)為最大的問題稱為最小費(fèi)用最大流問題。ijc0ijbijff ijijfbfb)(vfv)(Avvijijjifbfb),(*min)(第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 基本思想：從零流（f0=0）的費(fèi)用有向圖D(f0)開始，用求最短路的方法求出由vs到vt的最小費(fèi)用鏈 ，并對(duì) 按上節(jié)中Ford-Fulkerson標(biāo)號(hào)法的調(diào)整辦法進(jìn)行流量的調(diào)整，所以，新的可行流f1必是最小費(fèi)用可行流。如果 ，則計(jì)算終止。否則，重新構(gòu)造關(guān)于f的費(fèi)用有向圖D(f1)，繼續(xù)在D(f1)上求出由vs到vt的最小費(fèi)用鏈 ，并在 上進(jìn)行流量的調(diào)整，如此下去，直到求出流量為v的可行流f為止。如果v是最大流的流量，則此最小費(fèi)用流就是最小費(fèi)用最大流。00vfv)(111第七章 圖及網(wǎng)絡(luò)概述數(shù)據(jù)、模型與決策 (第二版) 已知一交