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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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