運(yùn)籌學(xué)課件圖與網(wǎng)絡(luò)分析

1、圖與網(wǎng)絡(luò)模型Graph Theory引言引言 十八世紀(jì)的哥尼斯堡城中流過一條河（普雷十八世紀(jì)的哥尼斯堡城中流過一條河（普雷.格爾河），河上有格爾河），河上有 7 座橋連接著河的兩岸和河中的兩個(gè)小島。當(dāng)時(shí)那里的人們熱衷于這樣座橋連接著河的兩岸和河中的兩個(gè)小島。當(dāng)時(shí)那里的人們熱衷于這樣一個(gè)游戲：一個(gè)游者怎樣才能一次連續(xù)走過這一個(gè)游戲：一個(gè)游者怎樣才能一次連續(xù)走過這 7 座橋，回到原出發(fā)點(diǎn)，座橋，回到原出發(fā)點(diǎn)，而每座橋只允許走一次。沒有人想出走法，又無法說明走法不存在，而每座橋只允許走一次。沒有人想出走法，又無法說明走法不存在，這就是著名的這就是著名的“哥尼斯堡哥尼斯堡 7 橋橋”難題。難題。ABC

2、D圖與網(wǎng)絡(luò)模型Graph Theory引言引言 “哥尼斯堡哥尼斯堡 7 橋橋”難題最終在難題最終在 1736 年由數(shù)學(xué)家年由數(shù)學(xué)家 Euler 的一篇論文給的一篇論文給予了完滿的解決，這是圖論的第一篇論文。在后來的兩百年間圖論的予了完滿的解決，這是圖論的第一篇論文。在后來的兩百年間圖論的發(fā)展是緩慢的，直到發(fā)展是緩慢的，直到 1936 年匈牙利數(shù)學(xué)家年匈牙利數(shù)學(xué)家 O.Knig寫出了寫出了圖論的第一圖論的第一本專著本專著有限圖與無限圖的理論有限圖與無限圖的理論。 在圖論的發(fā)展過程中還有兩位著名科學(xué)家值得一提，他們是克希在圖論的發(fā)展過程中還有兩位著名科學(xué)家值得一提，他們是克?；舴蚝蛣P萊?？讼；舴蛟?/p>

3、研究電網(wǎng)絡(luò)時(shí)對(duì)圖的獨(dú)立回路理論作出了重霍夫和凱萊?？讼；舴蛟谘芯侩娋W(wǎng)絡(luò)時(shí)對(duì)圖的獨(dú)立回路理論作出了重要的貢獻(xiàn)，而化學(xué)家凱萊在對(duì)碳?xì)浠衔锏耐之悩?gòu)體的數(shù)量進(jìn)行計(jì)要的貢獻(xiàn)，而化學(xué)家凱萊在對(duì)碳?xì)浠衔锏耐之悩?gòu)體的數(shù)量進(jìn)行計(jì)數(shù)時(shí)推動(dòng)了圖論中樹的計(jì)數(shù)問題的研究。數(shù)時(shí)推動(dòng)了圖論中樹的計(jì)數(shù)問題的研究。 圖論的歷史上最具有傳奇色彩的問題也許要數(shù)著名的圖論的歷史上最具有傳奇色彩的問題也許要數(shù)著名的“四色猜想四色猜想”了了歷史上許許多多數(shù)學(xué)猜想之一。它描述對(duì)一張地圖著色的問題，歷史上許許多多數(shù)學(xué)猜想之一。它描述對(duì)一張地圖著色的問題，曾經(jīng)有一位數(shù)學(xué)家這樣說：曾經(jīng)有一位數(shù)學(xué)家這樣說：“對(duì)于這個(gè)問題，一位數(shù)學(xué)家可以用

4、不到對(duì)于這個(gè)問題，一位數(shù)學(xué)家可以用不到五分鐘的時(shí)間向馬路上任何一位行人講述清楚它，然后，兩人都明白五分鐘的時(shí)間向馬路上任何一位行人講述清楚它，然后，兩人都明白這一問題，但是，兩人都無能為力。這一問題，但是，兩人都無能為力?！毙疫\(yùn)的是在幸運(yùn)的是在 1970s 終于由美國終于由美國的的兩位數(shù)學(xué)家借助大型計(jì)算機(jī)將其證明了。兩位數(shù)學(xué)家借助大型計(jì)算機(jī)將其證明了。圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 圖論與網(wǎng)絡(luò)分析理論所研究的問題十分廣泛，內(nèi)容極其豐富。正圖論與網(wǎng)絡(luò)分析理論所研究的問題十分廣泛，內(nèi)容極其豐富。正如一位數(shù)學(xué)家所說：如一位數(shù)學(xué)家所說：“可以說，圖論為任何一個(gè)

5、可以說，圖論為任何一個(gè)包含了某種二元關(guān)系包含了某種二元關(guān)系的系統(tǒng)提供了一種分析和描述的模型。的系統(tǒng)提供了一種分析和描述的模型。” 下面我們來看一個(gè)案例下面我們來看一個(gè)案例 國慶大假期間旅游非?；鸨瑱C(jī)票早已訂購一空。成都一家旅行國慶大假期間旅游非常火爆，機(jī)票早已訂購一空。成都一家旅行社由于信譽(yù)好、服務(wù)好，所策劃的國慶首都游的行情看好，要求參加社由于信譽(yù)好、服務(wù)好，所策劃的國慶首都游的行情看好，要求參加的游客眾多，游客甚至不惜多花機(jī)票錢暫轉(zhuǎn)取道它地也愿參加此游。的游客眾多，游客甚至不惜多花機(jī)票錢暫轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急電傳他在全國各地的辦事處要求協(xié)助解決此問題。很旅行社只好緊急電

6、傳他在全國各地的辦事處要求協(xié)助解決此問題。很快，各辦事處將其已訂購機(jī)票的情況傳到了總社。根據(jù)此資料，總社快，各辦事處將其已訂購機(jī)票的情況傳到了總社。根據(jù)此資料，總社要作出計(jì)劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機(jī)。要作出計(jì)劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機(jī)。下面是各辦事處已訂購機(jī)票的詳細(xì)情況表：下面是各辦事處已訂購機(jī)票的詳細(xì)情況表：圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念各辦事處已訂購機(jī)票情況表各辦事處已訂購機(jī)票情況表成都成都重慶重慶武漢武漢上海上海西安西安鄭州鄭州沈陽沈陽昆明昆明廣州廣州北京北京成都成都 重慶重慶 武漢武漢 上海上海

7、西安西安 鄭州鄭州 沈陽沈陽 昆明昆明 廣州廣州 北京北京10 5 15 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 將此問題通過圖的模型描述：將此問題通過圖的模型描述：下圖中，點(diǎn)下圖中，點(diǎn)各城市，帶箭頭連線各城市，帶箭頭連線從箭尾城市到箭頭城市已訂從箭尾城市到箭頭城市已訂購有機(jī)票，帶箭頭連線旁的數(shù)字購有機(jī)票，帶箭頭連線旁的數(shù)字機(jī)票數(shù)量。機(jī)票數(shù)量。成成重重武武昆昆上上廣廣西西鄭鄭沈沈京京8鄭州辦事處已訂鄭州辦事處已訂有的到北京的有的到北京的機(jī)票數(shù)量。機(jī)票數(shù)

8、量。圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念一、一、圖及其分類和術(shù)語圖及其分類和術(shù)語 1、 圖論中所研究的圖并非幾何學(xué)中的圖，也不是繪畫中的圖。在這圖論中所研究的圖并非幾何學(xué)中的圖，也不是繪畫中的圖。在這里我們所關(guān)心的僅僅是圖中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間有無線來連接，里我們所關(guān)心的僅僅是圖中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間有無線來連接，也就是說我們研究的是某個(gè)系統(tǒng)中的元素也就是說我們研究的是某個(gè)系統(tǒng)中的元素點(diǎn)，以及這些元素之間點(diǎn)，以及這些元素之間的某種關(guān)系的某種關(guān)系連線。連線。定義：定義：圖圖一個(gè)圖一個(gè)圖G是一個(gè)有序二元組（是一個(gè)有序二元組（V，E），記為），記為G=（V，E

9、）其中（其中（1） V是一個(gè)有限非空的集合，其元素稱為是一個(gè)有限非空的集合，其元素稱為G的點(diǎn)或頂點(diǎn)，而稱的點(diǎn)或頂點(diǎn)，而稱V為為G的點(diǎn)集的點(diǎn)集 V=v1，v2，vn；（；（2）E是是V中元素的無序?qū)χ性氐臒o序?qū)?vi，vj)所所構(gòu)成的一個(gè)集合，其元素稱為構(gòu)成的一個(gè)集合，其元素稱為G的邊，一般表示為的邊，一般表示為 e =(vi，vj)，而稱，而稱E是是G的邊集。的邊集。 邊（無向邊）邊（無向邊）沒有方向的連線沒有方向的連線?。ㄓ邢蜻叄┗。ㄓ邢蜻叄в蟹较虻倪B線帶有方向的連線無向圖無向圖 有向圖有向圖 簡(jiǎn)單圖簡(jiǎn)單圖 多重圖多重圖完全圖完全圖 二部圖（偶圖，雙圖）二部圖（偶圖，雙圖）圖與網(wǎng)絡(luò)模型G

10、raph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念子圖子圖 真子圖真子圖生成子圖生成子圖 點(diǎn)生成子圖點(diǎn)生成子圖 邊生成子圖邊生成子圖點(diǎn)的次點(diǎn)的次 奇次點(diǎn)奇次點(diǎn) 偶次點(diǎn)偶次點(diǎn)鏈鏈 圈圈 路路 回路回路 賦權(quán)圖賦權(quán)圖2、連通圖連通圖 在眾多各類圖中有一類在實(shí)際應(yīng)用中占有重要地位的圖在眾多各類圖中有一類在實(shí)際應(yīng)用中占有重要地位的圖 連通圖連通圖在圖中，任意兩點(diǎn)間至少存在著一條鏈在圖中，任意兩點(diǎn)間至少存在著一條鏈連通圖連通圖不連通圖不連通圖圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念3、圖與矩陣圖與矩陣 在圖與網(wǎng)絡(luò)分析的應(yīng)用中，將面臨一個(gè)問題在圖與網(wǎng)絡(luò)分析的應(yīng)用中，

11、將面臨一個(gè)問題如何分析、計(jì)算一如何分析、計(jì)算一個(gè)較大型的網(wǎng)絡(luò)，這當(dāng)然需借助快速的計(jì)算工具個(gè)較大型的網(wǎng)絡(luò)，這當(dāng)然需借助快速的計(jì)算工具計(jì)算機(jī)。那么，如計(jì)算機(jī)。那么，如何將一個(gè)圖表示在計(jì)算機(jī)中，或者，如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)何將一個(gè)圖表示在計(jì)算機(jī)中，或者，如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來表示一個(gè)圖，在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來表示一個(gè)圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有鄰接矩陣、關(guān)聯(lián)矩陣、鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。權(quán)矩陣等。鄰接矩陣鄰接矩陣對(duì)于圖對(duì)于圖G=（V，E），），| V

12、 |=n， | E |=m，有，有n n階方階方矩陣矩陣A=（aij） n n，其中其中 aij = k 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)vi與與vj之間有條邊時(shí)之間有條邊時(shí) 0 其它其它圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念鄰接矩陣鄰接矩陣A=（aij） n n=0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 2 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 10 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 2 0 1 0 0 0 v1v2v3v4v5v6v7v8v1 v2 v3 v4 v5

13、v6 v7 v8 v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣對(duì)于圖對(duì)于圖G=（V，E），），| V |=n， | E |=m，有，有m n階階矩陣矩陣M=（mij） m n，其中其中 mij = 2 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) vi是邊是邊ej 的兩個(gè)端點(diǎn)的兩個(gè)端點(diǎn) 1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) vi是邊是邊ej 的一個(gè)端點(diǎn)的一個(gè)端點(diǎn)例例 0 其它其它v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8M=（mij）=1 0 1 0 0 0 0 0

14、 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 圖與網(wǎng)絡(luò)模型Graph Theory最小樹問題最小樹問題二、二、樹（樹（Tree）和最小樹）和最小樹 樹是圖論中一類重要的圖，實(shí)際中有很多系統(tǒng)的結(jié)構(gòu)都是

15、樹。樹是圖論中一類重要的圖，實(shí)際中有很多系統(tǒng)的結(jié)構(gòu)都是樹。樹樹連通且不含圈的圖，簡(jiǎn)記為連通且不含圈的圖，簡(jiǎn)記為 T 。 下面的說法是等價(jià)的：下面的說法是等價(jià)的：T是一個(gè)樹。是一個(gè)樹。 T無圈，且無圈，且 m = n-1。 T連通，且連通，且 m = n-1。 T無圈，但每加一條新的邊即出現(xiàn)唯一一個(gè)圈。無圈，但每加一條新的邊即出現(xiàn)唯一一個(gè)圈。 T連通，但每舍去一連通，但每舍去一條邊就不連通。條邊就不連通。 T中任意兩點(diǎn)，有唯一的一條鏈相連。中任意兩點(diǎn)，有唯一的一條鏈相連。 T是邊是邊數(shù)最少的數(shù)最少的連通圖。連通圖。圖的生成樹圖的生成樹若若G圖的一個(gè)點(diǎn)圖的一個(gè)點(diǎn)生成子圖是一個(gè)樹，則稱此樹是生成子圖

16、是一個(gè)樹，則稱此樹是G圖的圖的一個(gè)一個(gè)生成樹。生成樹。樹的權(quán)樹的權(quán)若若Tk是加權(quán)圖是加權(quán)圖G的一棵樹，則樹的一棵樹，則樹T的全部邊的權(quán)之和稱為樹的全部邊的權(quán)之和稱為樹Tk的權(quán)，記為的權(quán)，記為 （ Tk ）= （e）；）； e Tk最小樹最小樹T*是加權(quán)圖是加權(quán)圖G的一棵的一棵最小最小樹，即樹，即 （ T* ）=min (Tk) k圖與網(wǎng)絡(luò)模型Graph Theory最小樹問題最小樹問題破圈法，避圈法求破圈法，避圈法求生成樹：生成樹：圖圖G生成樹生成樹T生成樹生成樹T圖與網(wǎng)絡(luò)模型Graph Theory最小樹問題最小樹問題破圈法，避圈法求最小破圈法，避圈法求最小生成樹：生成樹：圖圖G生成樹生成樹

17、T生成樹生成樹T15424531344215121231211212312112圖與網(wǎng)絡(luò)模型Graph Theory最短路問題最短路問題三、三、路（路（Path）和最短路）和最短路 最短路問題是網(wǎng)絡(luò)分析中應(yīng)用最廣泛的問題之一。盡管前面介紹最短路問題是網(wǎng)絡(luò)分析中應(yīng)用最廣泛的問題之一。盡管前面介紹了用動(dòng)態(tài)規(guī)劃方法求解，但有時(shí)卻較困難，此時(shí)圖論的方法卻十分有了用動(dòng)態(tài)規(guī)劃方法求解，但有時(shí)卻較困難，此時(shí)圖論的方法卻十分有效。效。 最短路問題的一般描述：最短路問題的一般描述：G = （V，E）是連通圖，圖中各邊（）是連通圖，圖中各邊（vi，vj）有權(quán)有權(quán)l(xiāng)ij（= 表示表示vi，vj間間無邊無邊），），v

18、s 、vt為為圖中任意兩指定點(diǎn)，求一條路圖中任意兩指定點(diǎn)，求一條路 ，使其是從，使其是從 vs到到 vt的的所有路中最短（路中各邊的權(quán)之和最?。┑囊粭l路。即所有路中最短（路中各邊的權(quán)之和最?。┑囊粭l路。即L（ ）= min lij（vi，vj） 圖與網(wǎng)絡(luò)模型Graph Theory最短路問題最短路問題 E.W.Dijkstra 算法（標(biāo)號(hào)算法）算法（標(biāo)號(hào)算法）算法基本思路分析：（逐步向外搜索）算法基本思路分析：（逐步向外搜索）52165828997221210X（P標(biāo)號(hào)）標(biāo)號(hào)）Y（T標(biāo)號(hào)）標(biāo)號(hào)）起點(diǎn)到起點(diǎn)到該點(diǎn)的該點(diǎn)的最短距最短距離離起點(diǎn)到起點(diǎn)到該點(diǎn)的該點(diǎn)的最短距最短距離的離的上上界界2527

19、 5111212105756 679 910106 3 3人、狼、羊、草渡河游戲人、狼、羊、草渡河游戲一個(gè)人帶著一條狼、一只羊、一筐白菜過河蛤由于船太小，人一次只能帶一樣?xùn)|西乘船過河。狼和羊、羊和白菜不能單獨(dú)留在同岸，否則羊或白菜會(huì)被吃掉。人人 M（Man），）， 狼狼 W（Wolf），）， 羊羊 G（Goat），草），草 H（Hay）。）。點(diǎn)點(diǎn) vi 表示河岸的狀態(tài)，表示河岸的狀態(tài)，邊邊 ek 表示由狀態(tài)表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài)經(jīng)一次渡河到狀態(tài) vj ，權(quán)權(quán)邊邊 ek 上的權(quán)定為上的權(quán)定為 1。 我們可以得到下面的加權(quán)有向圖：我們可以得到下面的加權(quán)有向圖：圖與網(wǎng)絡(luò)模型Graph T

20、heory最短路問題最短路問題v1，u1 =（M，W，G，H）；）； v2，u2 =（M，W，G）；）；v3，u3 =（M，W，H）；）； v4，u4 =（M，G，H）；）；v5，u5 =（M，G）。）。此游戲轉(zhuǎn)化為在下面的二部圖中求從此游戲轉(zhuǎn)化為在下面的二部圖中求從 v1 到到 u1 的最短路問題。的最短路問題。v1v2v3v4v5u5u4u3u2u1圖與網(wǎng)絡(luò)模型Graph Theory最短路問題最短路問題 在在 E.W.Dijkstra 算法中必須滿足一個(gè)條件算法中必須滿足一個(gè)條件 在圖在圖 G 中所有邊的權(quán)中所有邊的權(quán) lij 0。若在圖。若在圖 G 中存在有負(fù)中存在有負(fù)權(quán)邊（權(quán)邊（當(dāng)然

21、，這種情形只針對(duì)有向圖而言當(dāng)然，這種情形只針對(duì)有向圖而言）時(shí)必）時(shí)必須對(duì)須對(duì)E.W.Dijkstra 算法加以修改算法加以修改 稱為修改的稱為修改的 E.W.Dijkstra 算法。算法。2、情況二：、情況二： wij0設(shè)從設(shè)從V1到到Vj(j=1,2,t)的最短路長(zhǎng)為的最短路長(zhǎng)為P1jV1到到Vj無任何中間點(diǎn)無任何中間點(diǎn) P1j（1）= wijV1到到Vj中間最多經(jīng)過一個(gè)點(diǎn)中間最多經(jīng)過一個(gè)點(diǎn) P1j（2）= min P1j（1）+wijV1到到Vj中間最多經(jīng)過兩個(gè)點(diǎn)中間最多經(jīng)過兩個(gè)點(diǎn) P1j（3）= min P1j（2）+wij.V1到到Vj中間最多經(jīng)過中間最多經(jīng)過t-2個(gè)點(diǎn)個(gè)點(diǎn) P1j（t

22、-1）= min P1j（t-2）+wij終止原則：終止原則：1）當(dāng)）當(dāng)P1j（k）= P1j（k+1）可停止，最短路可停止，最短路P1j*= P1j（k）2）當(dāng)）當(dāng)P1j（t-1）= P1j（t-2）時(shí)，再多迭代一次時(shí)，再多迭代一次P1j（t） ，若，若P1j（t） = P1j（t-1） ，則原問題無解，存在負(fù)回路。，則原問題無解，存在負(fù)回路。 例：例： 求下圖所示有向圖中從求下圖所示有向圖中從v1到各點(diǎn)的到各點(diǎn)的最短路。最短路。v1v4v2v3v5v6v7v825-34674-23-1-342 wij d(t)(v1,vj) v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v

23、4v5v6v7v80 25-30 -2406400-3 0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910說明：表中空格處為說明：表中空格處為+ 。4例例 設(shè)備更新問題設(shè)備更新問題制訂一設(shè)備更新問題，使得總費(fèi)用最小制訂一設(shè)備更新問題，使得總費(fèi)用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購買費(fèi)購買費(fèi) 13 14 16 19 24 使用年數(shù)使用年數(shù) 0-1 1-2 2-3 3-4 4-5 維修費(fèi)維修費(fèi) 8 10 13 18 27 解解設(shè)以設(shè)以vi(i=1,2,

24、3,4,5)表示表示“第第i年初購進(jìn)一臺(tái)年初購進(jìn)一臺(tái)新設(shè)備新設(shè)備”這種狀態(tài)，以這種狀態(tài)，以v6表示表示“第第5年末年末”這種狀態(tài)；這種狀態(tài)；以弧以弧(vi, vj)表示表示“第第i年初購置的一臺(tái)設(shè)備一直使用到年初購置的一臺(tái)設(shè)備一直使用到第第j年初年初”這一方案，以這一方案，以wij表示這一方案所需購置費(fèi)表示這一方案所需購置費(fèi)和維護(hù)費(fèi)之和。和維護(hù)費(fèi)之和。v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31, V1)(44,V1)(62,V1)(78,V3)這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問

25、題就可歸結(jié)為從圖中找出一條從可歸結(jié)為從圖中找出一條從v1到到v6的最短路問題。的最短路問題。用用Dijkstra標(biāo)號(hào)法，求得最短路為標(biāo)號(hào)法，求得最短路為 v1v3v6 即第一年初購置的設(shè)備使用到第三年初予以更新，即第一年初購置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費(fèi)用最然后一直使用到第五年末。這樣五年的總費(fèi)用最少，為少，為78。圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法距離矩陣摹乘法Dijkstra算法比較簡(jiǎn)單，但是，對(duì)于含有負(fù)權(quán)弧的網(wǎng)絡(luò)可能失效。算法比較簡(jiǎn)單，但是，對(duì)于含有負(fù)權(quán)弧的網(wǎng)絡(luò)可能失效。這時(shí)，應(yīng)對(duì)算法加以修改，即所謂這時(shí)，應(yīng)對(duì)算法加以修改，即所謂“

26、修改的修改的 Dijkstra 算法算法”。下面，。下面，介紹一種算法介紹一種算法距離矩陣摹乘法，它適用于任何網(wǎng)絡(luò)的最短路問題。距離矩陣摹乘法，它適用于任何網(wǎng)絡(luò)的最短路問題。例如例如v1v3v4v2v6v534233-24411-16333圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法距離矩陣摹乘法1、網(wǎng)絡(luò)的距離矩陣、網(wǎng)絡(luò)的距離矩陣設(shè)一網(wǎng)絡(luò)設(shè)一網(wǎng)絡(luò)N中有中有n個(gè)點(diǎn)，其中任意兩點(diǎn)個(gè)點(diǎn)，其中任意兩點(diǎn) vi 與與 vj 之間都有一條邊之間都有一條邊 ( vi, vj )，其權(quán)數(shù)為，其權(quán)數(shù)為 wij -。若。若 vi 與與 vj 不相鄰，則虛設(shè)一條邊不相鄰，則虛設(shè)一條邊( vi, vj )，并，并

27、令其權(quán)數(shù)令其權(quán)數(shù)wij = 。距離矩陣距離矩陣 W = （ wij ）前例中的距離矩陣為前例中的距離矩陣為W = v1 v2 v3 v4 v5 v6v1 0 3 2 4v2 0 4 4 1v3 0 -1 6 v4 3 -2 0 1 v5 5 0 3v6 3 3 0圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法距離矩陣摹乘法2、求各點(diǎn)至某點(diǎn)的最短路、求各點(diǎn)至某點(diǎn)的最短路求求 vi（i = 1, 2, , n）至某點(diǎn)）至某點(diǎn) vr 的最短路。的最短路。令：令：dir(k) = vi 走走k步達(dá)到步達(dá)到 vr 的最短距離，的最短距離， i = 1, 2, , n則有則有 dir(1) = wir

28、 , i = 1, 2, , ndir(k) = min wij + djr(k-1) , i = 1, 2, , n1jn令：令：dk =（ d1r(k) , d2r(k) , dnr(k) , ）T , k = 1, 2, 圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法距離矩陣摹乘法矩陣摹乘運(yùn)算法：矩陣摹乘運(yùn)算法： dk = W dk-1 , ( k = 2 , 3 , )當(dāng)當(dāng) dk = dk-1 , ( k= 2, 3, )則計(jì)算停止，則計(jì)算停止， dk 中的元素即為各點(diǎn)到中的元素即為各點(diǎn)到 vr 的最短距離。的最短距離。圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題網(wǎng)絡(luò)中心

29、和重心問題一、一、基本概念基本概念 網(wǎng)絡(luò)最短距離矩陣網(wǎng)絡(luò)最短距離矩陣 D = ( dij )nn dij表示表示vi到到vj的最短距離的最短距離（ 1 ）網(wǎng)絡(luò)的中心）網(wǎng)絡(luò)的中心令：令： d( vi )= max dij , i = 1, 2, , n若若 max d( vi ) = d( vk )1in1jn則稱點(diǎn)則稱點(diǎn) vk 為網(wǎng)絡(luò)的中心。為網(wǎng)絡(luò)的中心。圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題網(wǎng)絡(luò)中心和重心問題（ 2 ）網(wǎng)絡(luò)的重心）網(wǎng)絡(luò)的重心 設(shè)設(shè) gi 為點(diǎn)為點(diǎn) vi 的權(quán)重（的權(quán)重（ i = 1, 2, , n ），），令：令： h ( vj ) = gidij , j =

30、 1, 2, , ni=1n若若 max h( vj ) = h( vr )1jn則稱點(diǎn)則稱點(diǎn) vr 為網(wǎng)絡(luò)的重心。為網(wǎng)絡(luò)的重心。圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題網(wǎng)絡(luò)中心和重心問題二、二、應(yīng)用應(yīng)用例例 某地某地 7 個(gè)村鎮(zhèn)之間的現(xiàn)有交通道路如下圖，邊旁數(shù)值為各村個(gè)村鎮(zhèn)之間的現(xiàn)有交通道路如下圖，邊旁數(shù)值為各村鎮(zhèn)之間道路的長(zhǎng)度，點(diǎn)旁數(shù)值為各村鎮(zhèn)的小學(xué)生人數(shù)?，F(xiàn)擬在某一村鎮(zhèn)鎮(zhèn)之間道路的長(zhǎng)度，點(diǎn)旁數(shù)值為各村鎮(zhèn)的小學(xué)生人數(shù)?，F(xiàn)擬在某一村鎮(zhèn)建一商店和小學(xué)，試問：建一商店和小學(xué)，試問：（1）商店應(yīng)該建在何村，能使各村都離它較近？）商店應(yīng)該建在何村，能使各村都離它較近？（2）小學(xué)應(yīng)該建在

31、何村，能使各村小學(xué)生總的行走路程最短？）小學(xué)應(yīng)該建在何村，能使各村小學(xué)生總的行走路程最短？圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題網(wǎng)絡(luò)中心和重心問題v1v3v4v5v6v7v2746435712324230404535252050距離距離人數(shù)人數(shù)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題網(wǎng)絡(luò)中心和重心問題（1）中心問題）中心問題 網(wǎng)絡(luò)最短距離矩陣如下：網(wǎng)絡(luò)最短距離矩陣如下： vj viD = ( dij )d( vi )= max dij 123456710345781010230324577343055688452502355 ( min )574520137685

32、63102871078532010j結(jié)論：結(jié)論： 商店應(yīng)該建在商店應(yīng)該建在 v4 村。村。圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題網(wǎng)絡(luò)中心和重心問題（2）重心問題）重心問題 vj vi gidij123456710120160200280320400275075501001251753180135022522527036041506015006090150514080100400206062801752101053507075003504002501501000h ( vj )13259201095870850(min)9251215結(jié)論：結(jié)論： 小學(xué)應(yīng)該建在小學(xué)應(yīng)該建在 v5

33、村。村。第四節(jié)第四節(jié) 最大流問題最大流問題 如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡(luò)的最大流量是多少？該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題定義定義1 1：定一個(gè)有向圖：定一個(gè)有向圖D=(V,E),D=(V,E),在在V V中有一個(gè)發(fā)點(diǎn)中有一個(gè)發(fā)點(diǎn)vsvs和一收點(diǎn)和一收點(diǎn)v vt t，其余，其余的點(diǎn)為中間點(diǎn)。對(duì)于每一條弧的點(diǎn)為中間點(diǎn)。對(duì)于每一條弧( (v vi i,v,vj j),),對(duì)應(yīng)有一個(gè)對(duì)應(yīng)有一個(gè)c(c(v vi i,v,vj j)

34、) 0,(0,(c cijij) )稱稱為弧的容量。這樣的有向圖稱為容量網(wǎng)絡(luò)。記為為弧的容量。這樣的有向圖稱為容量網(wǎng)絡(luò)。記為D=(V,E,C)D=(V,E,C)。1、網(wǎng)絡(luò)流、網(wǎng)絡(luò)流義在弧集合義在弧集合E上的一個(gè)函數(shù)上的一個(gè)函數(shù)f=f(vi,vj)，稱，稱f(vi,vj)為弧為弧(vi,vj)上的流量，簡(jiǎn)記上的流量，簡(jiǎn)記fij 。2、可行流、可行流3、最大流、最大流4、增廣鏈、增廣鏈5、最小截集、最小截集2、可行流與最大流、可行流與最大流定義定義2 滿足下列條件的流稱為滿足下列條件的流稱為可行流可行流：1) 0 fij cij2)平衡條件：平衡條件：中間點(diǎn)中間點(diǎn) fij = fji(vi,vj)

35、 A(vj,vi) A發(fā)點(diǎn)發(fā)點(diǎn)vs fsj fjs=v(f)(vs,vj) A (vj,vs) A ftj fjt= v(f)(vt,vj) A收點(diǎn)收點(diǎn)vt，(vj,vt) A式中式中v(f)稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。（或收點(diǎn)的凈輸入量）。最大流問題：求一流最大流問題：求一流fij滿足滿足0 fij cij v(f) i=s fij fji= 0 i s，t v(f) i=t且使且使v(f)達(dá)到最大。達(dá)到最大。3、增廣鏈、增廣鏈 給定可行流給定可行流f=fij，使，使fij=cij的弧稱為的弧稱為飽和弧飽和弧，使使fij0

36、的弧稱為的弧稱為非零流弧非零流弧。 若若 是網(wǎng)絡(luò)中連接發(fā)點(diǎn)是網(wǎng)絡(luò)中連接發(fā)點(diǎn)vs和收點(diǎn)和收點(diǎn)vt的一條鏈，定的一條鏈，定義鏈的方向是從義鏈的方向是從vs到到vt，則鏈上的弧被分成兩類：，則鏈上的弧被分成兩類：前向?。夯〉姆较蚺c鏈的方向一致前向?。夯〉姆较蚺c鏈的方向一致 全體全體 +后向?。夯〉姆较蚺c鏈的方向相反后向?。夯〉姆较蚺c鏈的方向相反 全體全體 定義定義3 設(shè)設(shè)f是一可行流，是一可行流， 是從是從vs到到vt的一條鏈，的一條鏈，若若 滿足下列條件，則稱之為（關(guān)于流滿足下列條件，則稱之為（關(guān)于流f的）一條的）一條增廣鏈：增廣鏈： 在弧在弧(vi,vj)+上，上，0 fijcij 在弧在弧(v

37、i,vj)上，上，0fij cij 4、截集與截量、截集與截量 定義定義4 給定網(wǎng)絡(luò)給定網(wǎng)絡(luò)D=(V,A,C)，若點(diǎn)集，若點(diǎn)集V被被剖分為兩個(gè)非空集合剖分為兩個(gè)非空集合V1和和V1，使，使vs V1，vt V1，則把弧集，則把弧集(V1,V1)稱為是（分離稱為是（分離vs和和vt的）的）截集。截集。截集是從截集是從vs到到vt的必經(jīng)之路。的必經(jīng)之路。 定義定義5 給定一截集給定一截集(V1,V1)，把截集，把截集(V1,V1)中所有弧的容量之和稱為這個(gè)截集的容量中所有弧的容量之和稱為這個(gè)截集的容量(截量截量),記為記為C(V1,V1)。v(f) C(V1,V1)圖與網(wǎng)絡(luò)模型Graph Theo

38、ry網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題1、流量、流量截量定理截量定理容量網(wǎng)絡(luò)上任何一個(gè)可行流的流量不超過任何一個(gè)截集的容量網(wǎng)絡(luò)上任何一個(gè)可行流的流量不超過任何一個(gè)截集的截量。截量。2、增廣鏈調(diào)整定理、增廣鏈調(diào)整定理在增廣鏈上對(duì)可行流進(jìn)行調(diào)整可以得到一個(gè)流量更大的可在增廣鏈上對(duì)可行流進(jìn)行調(diào)整可以得到一個(gè)流量更大的可行流。行流。3、最大流定理、最大流定理可行流是最大流的充分必要條件是不存在關(guān)于該可行流的可行流是最大流的充分必要條件是不存在關(guān)于該可行流的增廣鏈。增廣鏈。步驟步驟：2、 標(biāo)號(hào)過程標(biāo)號(hào)過程1、選取一個(gè)可行流（可選擇零流?。⑦x取一個(gè)可行流（可選擇零流?。?從從Vs出發(fā)，出發(fā)，在在前向前向弧弧上上(vi

39、,vj) ，若，若fij0，則給，則給vj標(biāo)號(hào)標(biāo)號(hào)( Vi,l(vj)，其中其中l(wèi)(vj)=minl(vi)，fji。二、尋找最大流的標(biāo)號(hào)法二、尋找最大流的標(biāo)號(hào)法(Ford Fulkerson) 思想：從一可行流出發(fā)，檢查關(guān)于此流是否思想：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增大流存在增廣鏈。若存在增廣鏈，則增大流量，使此量，使此鏈變?yōu)榉窃鰪V鏈；這時(shí)再檢查是非還有增廣鏈，鏈變?yōu)榉窃鰪V鏈；這時(shí)再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。 3、若標(biāo)號(hào)延續(xù)到、若標(biāo)號(hào)延續(xù)到vt，表明得到一條從，表明得到一條從vs到到vt

40、的增的增廣鏈廣鏈 ，轉(zhuǎn)入調(diào)整階段，轉(zhuǎn)入調(diào)整階段4，否則當(dāng)前流即為最大流。，否則當(dāng)前流即為最大流。4、調(diào)整過程、調(diào)整過程令調(diào)整量為令調(diào)整量為 = l(vt)令令 fij+ (vi,vj)+ fij = fij (vi,vj) fij (vi,vj)去掉所有的標(biāo)號(hào)，對(duì)新的可行流去掉所有的標(biāo)號(hào)，對(duì)新的可行流f =fij ，重新進(jìn)，重新進(jìn)入標(biāo)號(hào)過程。入標(biāo)號(hào)過程?？山Y(jié)合下圖理解其實(shí)際涵義?？山Y(jié)合下圖理解其實(shí)際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3

41、,1)(2,1)(6,3)(7,7)例例 求下列網(wǎng)絡(luò)的最大流與最小截集。求下列網(wǎng)絡(luò)的最大流與最小截集。解解一、標(biāo)號(hào)過程一、標(biāo)號(hào)過程則則v1的標(biāo)號(hào)為的標(biāo)號(hào)為(vs,l(v1)，其中，其中l(wèi)(v1)=minl(vs)，cs1fs1=min+ ，9 2=2（3）檢查）檢查v1,在弧在弧(v1,v4)上上,f14=7,c14=9,f140，則則v3的標(biāo)號(hào)為的標(biāo)號(hào)為(-v4, l(v3)，其中，其中l(wèi)(v3)=minl(v4)，f34=min2，1=1（5）檢查）檢查v3,在弧在弧(v3,vt)上上,f3t=3,c3t=6,f3tc3t,則則vt的標(biāo)號(hào)為的標(biāo)號(hào)為(v3,l(vt)，其中，其中l(wèi)(vt)=

42、minl(v3)，c3tf3t=min1，6-3=1這樣，我們得到了一增廣鏈這樣，我們得到了一增廣鏈 ,如圖所示。如圖所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0, )(vs,2)(v1,2)(-v4,1)(v3,1)其中其中 +=(vs,v1),(v1,v4),(v3,vt)， =(v3,v4)二、調(diào)整過程二、調(diào)整過程取調(diào)整量為取調(diào)整量為 =1，在，在 上調(diào)整上調(diào)整f。在在 +上：上： fs1+ =7+1=8 f14+ =2+1=3 f4t+ =5+1=6在在 上：上： f43 =11=0s1vtvv3(9,8)

43、(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7) 在上圖中重復(fù)上述標(biāo)號(hào)過程，依次給在上圖中重復(fù)上述標(biāo)號(hào)過程，依次給vs,v2,v1,v4標(biāo)號(hào)標(biāo)號(hào)后，由于標(biāo)號(hào)無法繼續(xù)下去，算法結(jié)束。這時(shí)的流為最后，由于標(biāo)號(hào)無法繼續(xù)下去，算法結(jié)束。這時(shí)的流為最大流，最大流的流量為大流，最大流的流量為vvv(4,4)v(f)=8+3=11 與此同時(shí)，可找到最小截集與此同時(shí)，可找到最小截集(V1,V1)，其中，其中V1為標(biāo)號(hào)點(diǎn)集為標(biāo)號(hào)點(diǎn)集合，合，V1為未標(biāo)號(hào)點(diǎn)集合，弧集合為未標(biāo)號(hào)點(diǎn)集合，弧集合(V1,V1) 即為最小截集。即為最小截集。此例中，此例中， V1=vs,v2,v1,v4, V1=v3

44、,vt,(V1,V1)=(v1,v3)， (v4,vt)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題容量網(wǎng)絡(luò)容量網(wǎng)絡(luò) N 上最大流的標(biāo)號(hào)（上最大流的標(biāo)號(hào)（Ford-Fulkerson）算法：）算法： 下面，我們采用此算法來求解前面的旅行總社計(jì)劃問下面，我們采用此算法來求解前面的旅行總社計(jì)劃問題案例題案例圖與網(wǎng)絡(luò)模型Graph Theory最大流問題最大流問題各辦事處已訂購機(jī)票情況表各辦事處已訂購機(jī)票情況表成都成都vs重慶重慶v1武漢武漢v2上海上海v3西安西安v4鄭州鄭州v5沈陽沈陽v6昆明昆明v7廣州廣州v8北京北京vt成都成都 重慶重慶 武漢武漢 上海上海 西安西安 鄭州鄭州 沈陽