運籌學課件圖與網(wǎng)絡分析

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

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

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

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

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

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

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)絡模型Graph Theory圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 將此問題通過圖的模型描述：將此問題通過圖的模型描述：下圖中，點下圖中，點各城市，帶箭頭連線各城市，帶箭頭連線從箭尾城市到箭頭城市已訂從箭尾城市到箭頭城市已訂購有機票，帶箭頭連線旁的數(shù)字購有機票，帶箭頭連線旁的數(shù)字機票數(shù)量。機票數(shù)量。成成重重武武昆昆上上廣廣西西鄭鄭沈沈京京8鄭州辦事處已訂鄭州辦事處已訂有的到北京的有的到北京的機票數(shù)量。機票數(shù)

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

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

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

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

12、 |=n， | E |=m，有，有n n階方階方矩陣矩陣A=（aij） n n，其中其中 aij = k 當且僅當當且僅當vi與與vj之間有條邊時之間有條邊時 0 其它其它圖與網(wǎng)絡模型Graph Theory圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念鄰接矩陣鄰接矩陣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)絡模型Graph Theory圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣對于圖對于圖G=（V，E），），| V |=n， | E |=m，有，有m n階階矩陣矩陣M=（mij） m n，其中其中 mij = 2 當且僅當當且僅當 vi是邊是邊ej 的兩個端點的兩個端點 1 當且僅當當且僅當 vi是邊是邊ej 的一個端點的一個端點例例 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)絡模型Graph Theory最小樹問題最小樹問題二、二、樹（樹（Tree）和最小樹）和最小樹 樹是圖論中一類重要的圖，實際中有很多系統(tǒng)的結(jié)構(gòu)都是

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

16、是一個樹，則稱此樹是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)絡模型Graph Theory最小樹問題最小樹問題破圈法，避圈法求破圈法，避圈法求生成樹：生成樹：圖圖G生成樹生成樹T生成樹生成樹T圖與網(wǎng)絡模型Graph Theory最小樹問題最小樹問題破圈法，避圈法求最小破圈法，避圈法求最小生成樹：生成樹：圖圖G生成樹生成樹

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

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

19、 5111212105756 679 910106 3 3人、狼、羊、草渡河游戲人、狼、羊、草渡河游戲一個人帶著一條狼、一只羊、一筐白菜過河蛤由于船太小，人一次只能帶一樣東西乘船過河。狼和羊、羊和白菜不能單獨留在同岸，否則羊或白菜會被吃掉。人人 M（Man），）， 狼狼 W（Wolf），）， 羊羊 G（Goat），草），草 H（Hay）。）。點點 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)絡模型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)絡模型Graph Theory最短路問題最短路問題 在在 E.W.Dijkstra 算法中必須滿足一個條件算法中必須滿足一個條件 在圖在圖 G 中所有邊的權(quán)中所有邊的權(quán) lij 0。若在圖。若在圖 G 中存在有負中存在有負權(quán)邊（權(quán)邊（當然

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

22、-1）= min P1j（t-2）+wij終止原則：終止原則：1）當）當P1j（k）= P1j（k+1）可停止，最短路可停止，最短路P1j*= P1j（k）2）當）當P1j（t-1）= P1j（t-2）時，再多迭代一次時，再多迭代一次P1j（t） ，若，若P1j（t） = P1j（t-1） ，則原問題無解，存在負回路。，則原問題無解，存在負回路。 例：例： 求下圖所示有向圖中從求下圖所示有向圖中從v1到各點的到各點的最短路。最短路。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例例 設備更新問題設備更新問題制訂一設備更新問題，使得總費用最小制訂一設備更新問題，使得總費用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購買費購買費 13 14 16 19 24 使用年數(shù)使用年數(shù) 0-1 1-2 2-3 3-4 4-5 維修費維修費 8 10 13 18 27 解解設以設以vi(i=1,2,

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

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

26、修改的修改的 Dijkstra 算法算法”。下面，。下面，介紹一種算法介紹一種算法距離矩陣摹乘法，它適用于任何網(wǎng)絡的最短路問題。距離矩陣摹乘法，它適用于任何網(wǎng)絡的最短路問題。例如例如v1v3v4v2v6v534233-24411-16333圖與網(wǎng)絡模型Graph Theory距離矩陣摹乘法距離矩陣摹乘法1、網(wǎng)絡的距離矩陣、網(wǎng)絡的距離矩陣設一網(wǎng)絡設一網(wǎng)絡N中有中有n個點，其中任意兩點個點，其中任意兩點 vi 與與 vj 之間都有一條邊之間都有一條邊 ( vi, vj )，其權(quán)數(shù)為，其權(quán)數(shù)為 wij -。若。若 vi 與與 vj 不相鄰，則虛設一條邊不相鄰，則虛設一條邊( 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)絡模型Graph Theory距離矩陣摹乘法距離矩陣摹乘法2、求各點至某點的最短路、求各點至某點的最短路求求 vi（i = 1, 2, , n）至某點）至某點 vr 的最短路。的最短路。令：令：dir(k) = vi 走走k步達到步達到 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)絡模型Graph Theory距離矩陣摹乘法距離矩陣摹乘法矩陣摹乘運算法：矩陣摹乘運算法： dk = W dk-1 , ( k = 2 , 3 , )當當 dk = dk-1 , ( k= 2, 3, )則計算停止，則計算停止， dk 中的元素即為各點到中的元素即為各點到 vr 的最短距離。的最短距離。圖與網(wǎng)絡模型Graph Theory網(wǎng)絡中心和重心問題網(wǎng)絡中心

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

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

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

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

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

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

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

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

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

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

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

40、的增的增廣鏈廣鏈 ，轉(zhuǎn)入調(diào)整階段，轉(zhuǎn)入調(diào)整階段4，否則當前流即為最大流。，否則當前流即為最大流。4、調(diào)整過程、調(diào)整過程令調(diào)整量為令調(diào)整量為 = l(vt)令令 fij+ (vi,vj)+ fij = fij (vi,vj) fij (vi,vj)去掉所有的標號，對新的可行流去掉所有的標號，對新的可行流f =fij ，重新進，重新進入標號過程。入標號過程?？山Y(jié)合下圖理解其實際涵義?？山Y(jié)合下圖理解其實際涵義。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)絡的最大流與最小截集。求下列網(wǎng)絡的最大流與最小截集。解解一、標號過程一、標號過程則則v1的標號為的標號為(vs,l(v1)，其中，其中l(wèi)(v1)=minl(vs)，cs1fs1=min+ ，9 2=2（3）檢查）檢查v1,在弧在弧(v1,v4)上上,f14=7,c14=9,f140，則則v3的標號為的標號為(-v4, l(v3)，其中，其中l(wèi)(v3)=minl(v4)，f34=min2，1=1（5）檢查）檢查v3,在弧在弧(v3,vt)上上,f3t=3,c3t=6,f3tc3t,則則vt的標號為的標號為(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) 在上圖中重復上述標號過程，依次給在上圖中重復上述標號過程，依次給vs,v2,v1,v4標號標號后，由于標號無法繼續(xù)下去，算法結(jié)束。這時的流為最后，由于標號無法繼續(xù)下去，算法結(jié)束。這時的流為最大流，最大流的流量為大流，最大流的流量為vvv(4,4)v(f)=8+3=11 與此同時，可找到最小截集與此同時，可找到最小截集(V1,V1)，其中，其中V1為標號點集為標號點集合，合，V1為未標號點集合，弧集合為未標號點集合，弧集合(V1,V1) 即為最小截集。即為最小截集。此例中，此例中， V1=vs,v2,v1,v4, V1=v3

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