圖與網(wǎng)絡(luò)模型Graph Theory引言 十八世紀(jì)的哥尼斯堡城中流過(guò)一條河（普雷.格爾河），河上有 7 座橋連接著河的兩岸和河中的兩個(gè)小島。當(dāng)時(shí)那里的人們熱衷于這樣一個(gè)游戲：一個(gè)游者怎樣才能一次連續(xù)走過(guò)這 7 座橋，回到原出發(fā)點(diǎn)，而每座橋只允許走一次。沒(méi)有人想出走法，又無(wú)法說(shuō)明走法不存在，這就是著名的“哥尼斯堡 7 橋”難題。ABCD第1頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory引言 “哥尼斯堡 7 橋”難題最終在 1736 年由數(shù)學(xué)家 Euler 的一篇論文給予了完滿的解決，這是圖論的第一篇論文。在后來(lái)的兩百年間圖論的發(fā)展是緩慢的，直到 1936 年匈牙利數(shù)學(xué)家 O.Knig寫出了圖論的第一本專著有限圖與無(wú)限圖的理論。在圖論的發(fā)展過(guò)程中還有兩位著名科學(xué)家值得一提，他們是克?；舴蚝蛣P萊?？讼；舴蛟谘芯侩娋W(wǎng)絡(luò)時(shí)對(duì)圖的獨(dú)立回路理論作出了重要的貢獻(xiàn)，而化學(xué)家凱萊在對(duì)碳?xì)浠衔锏耐之悩?gòu)體的數(shù)量進(jìn)行計(jì)數(shù)時(shí)推動(dòng)了圖論中樹(shù)的計(jì)數(shù)問(wèn)題的研究。圖論的歷史上最具有傳奇色彩的問(wèn)題也許要數(shù)著名的“四色猜想”了歷史上許許多多數(shù)學(xué)猜想之一。它描述對(duì)一張地圖著色的問(wèn)題，曾經(jīng)有一位數(shù)學(xué)家這樣說(shuō)：“對(duì)于這個(gè)問(wèn)題，一位數(shù)學(xué)家可以用不到五分鐘的時(shí)間向馬路上任何一位行人講述清楚它，然后，兩人都明白這一問(wèn)題，但是，兩人都無(wú)能為力?！毙疫\(yùn)的是在 1970s 終于由美國(guó)的兩位數(shù)學(xué)家借助大型計(jì)算機(jī)將其證明了。第2頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 圖論與網(wǎng)絡(luò)分析理論所研究的問(wèn)題十分廣泛，內(nèi)容極其豐富。正如一位數(shù)學(xué)家所說(shuō)：“可以說(shuō)，圖論為任何一個(gè)包含了某種二元關(guān)系的系統(tǒng)提供了一種分析和描述的模型?！毕旅嫖覀儊?lái)看一個(gè)案例 國(guó)慶大假期間旅游非常火爆，機(jī)票早已訂購(gòu)一空。成都一家旅行社由于信譽(yù)好、服務(wù)好，所策劃的國(guó)慶首都游的行情看好，要求參加的游客眾多，游客甚至不惜多花機(jī)票錢暫轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急電傳他在全國(guó)各地的辦事處要求協(xié)助解決此問(wèn)題。很快，各辦事處將其已訂購(gòu)機(jī)票的情況傳到了總社。根據(jù)此資料，總社要作出計(jì)劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機(jī)。下面是各辦事處已訂購(gòu)機(jī)票的詳細(xì)情況表：第3頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 各辦事處已訂購(gòu)機(jī)票情況表成都成都重慶重慶武漢武漢上海上海西安西安鄭州鄭州沈陽(yáng)沈陽(yáng)昆明昆明廣州廣州北京北京成都成都 重慶重慶 武漢武漢 上海上海 西安西安 鄭州鄭州 沈陽(yáng)沈陽(yáng) 昆明昆明 廣州廣州 北京北京10 5 15 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 第4頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 將此問(wèn)題通過(guò)圖的模型描述：下圖中，點(diǎn)各城市，帶箭頭連線從箭尾城市到箭頭城市已訂購(gòu)有機(jī)票，帶箭頭連線旁的數(shù)字機(jī)票數(shù)量。成重武昆上廣西鄭沈京8鄭州辦事處已訂有的到北京的機(jī)票數(shù)量。第5頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 一、圖及其分類和術(shù)語(yǔ) 1、圖論中所研究的圖并非幾何學(xué)中的圖，也不是繪畫中的圖。在這里我們所關(guān)心的僅僅是圖中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間有無(wú)線來(lái)連接，也就是說(shuō)我們研究的是某個(gè)系統(tǒng)中的元素點(diǎn)，以及這些元素之間的某種關(guān)系連線。定義：圖一個(gè)圖G是一個(gè)有序二元組（V，E），記為G=（V，E）其中（1）V是一個(gè)有限非空的集合，其元素稱為G的點(diǎn)或頂點(diǎn)，而稱V為G的點(diǎn)集 V=v1，v2，vn；（2）E是V中元素的無(wú)序?qū)?vi，vj)所構(gòu)成的一個(gè)集合，其元素稱為G的邊，一般表示為 e=(vi，vj)，而稱E是G的邊集。邊（無(wú)向邊）沒(méi)有方向的連線 弧（有向邊）帶有方向的連線 無(wú)向圖 有向圖 簡(jiǎn)單圖 多重圖 完全圖 二部圖（偶圖，雙圖）第6頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 子圖 真子圖 生成子圖 點(diǎn)生成子圖 邊生成子圖 點(diǎn)的次 奇次點(diǎn) 偶次點(diǎn) 鏈 圈 路 回路 賦權(quán)圖 2、連通圖 在眾多各類圖中有一類在實(shí)際應(yīng)用中占有重要地位的圖 連通圖在圖中，任意兩點(diǎn)間至少存在著一條鏈連通圖連通圖不連通圖不連通圖第7頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 3、圖與矩陣 在圖與網(wǎng)絡(luò)分析的應(yīng)用中，將面臨一個(gè)問(wèn)題如何分析、計(jì)算一個(gè)較大型的網(wǎng)絡(luò)，這當(dāng)然需借助快速的計(jì)算工具計(jì)算機(jī)。那么，如何將一個(gè)圖表示在計(jì)算機(jī)中，或者，如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來(lái)表示一個(gè)圖，圖的矩陣表示也根據(jù)所關(guān)心的問(wèn)題不同而有鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。鄰接矩陣對(duì)于圖G=（V，E），|V|=n，|E|=m，有n n階方矩陣A=（aij）n n，其中 aij=k 當(dāng)且僅當(dāng)vi與vj之間有條邊時(shí) 0 其它第8頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(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 v6 v7 v8 v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8第9頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 關(guān)聯(lián)矩陣對(duì)于圖G=（V，E），|V|=n，|E|=m，有m n階矩陣M=（mij）m n，其中 mij =2 當(dāng)且僅當(dāng) vi是邊ej 的兩個(gè)端點(diǎn) 1 當(dāng)且僅當(dāng) vi是邊ej 的一個(gè)端點(diǎn) 例 0 其它v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8M=（mij）=1 0 1 0 0 0 0 0 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 第10頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最小樹(shù)問(wèn)題 二、樹(shù)（Tree）和最小樹(shù) 樹(shù)是圖論中一類重要的圖，實(shí)際中有很多系統(tǒng)的結(jié)構(gòu)都是樹(shù)。樹(shù)連通且不含圈的圖，簡(jiǎn)記為 T。下面的說(shuō)法是等價(jià)的：T是一個(gè)樹(shù)。T無(wú)圈，且 m=n-1。T連通，且 m=n-1。T無(wú)圈，但每加一條新的邊即出現(xiàn)唯一一個(gè)圈。T連通，但每舍去一條邊就不連通。T中任意兩點(diǎn)，有唯一的一條鏈相連。T是邊數(shù)最少的連通圖。圖的生成樹(shù)若G圖的一個(gè)點(diǎn)生成子圖是一個(gè)樹(shù)，則稱此樹(shù)是G圖的一個(gè)生成樹(shù)。樹(shù)的權(quán)若Tk是加權(quán)圖G的一棵樹(shù)，則樹(shù)T的全部邊的權(quán)之和稱為樹(shù)Tk的權(quán)，記為 （Tk）=（e）；e Tk 最小樹(shù)T*是加權(quán)圖G的一棵最小樹(shù)，即（T*）=min (Tk)k第11頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最小樹(shù)問(wèn)題 破圈法，避圈法求生成樹(shù)：圖圖G生成樹(shù)生成樹(shù)T生成樹(shù)生成樹(shù)T第12頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最小樹(shù)問(wèn)題 破圈法，避圈法求最小生成樹(shù)：圖圖G生成樹(shù)生成樹(shù)T生成樹(shù)生成樹(shù)T15424531344215121231211212312112第13頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最短路問(wèn)題 三、路（Path）和最短路 最短路問(wèn)題是網(wǎng)絡(luò)分析中應(yīng)用最廣泛的問(wèn)題之一。盡管前面介紹了用動(dòng)態(tài)規(guī)劃方法求解，但有時(shí)卻較困難，此時(shí)圖論的方法卻十分有效。最短路問(wèn)題的一般描述：G=（V，E）是連通圖，圖中各邊（vi，vj）有權(quán)l(xiāng)ij（=表示vi，vj間無(wú)邊），vs、vt為圖中任意兩指定點(diǎn)，求一條路，使其是從 vs到 vt的所有路中最短（路中各邊的權(quán)之和最?。┑囊粭l路。即L（）=min lij（vi，vj）第14頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最短路問(wèn)題 E.W.Dijkstra 算法（標(biāo)號(hào)算法）算法基本思路分析：（逐步向外搜索）52165828997221210X（P標(biāo)號(hào)）Y（T標(biāo)號(hào)）起點(diǎn)到該點(diǎn)的最短距離起點(diǎn)到該點(diǎn)的最短距離的上界2527 5111212105756 679 910106 3 3第15頁(yè)/共59頁(yè)人、狼、羊、草渡河游戲 一個(gè)人帶著一條狼、一只羊、一筐白菜過(guò)河蛤由于船太小，人一次只能帶一樣?xùn)|西乘船過(guò)河。狼和羊、羊和白菜不能單獨(dú)留在同岸，否則羊或白菜會(huì)被吃掉。人 M（Man），狼 W（Wolf），羊 G（Goat），草 H（Hay）。點(diǎn) vi 表示河岸的狀態(tài)，邊 ek 表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài) vj，權(quán)邊 ek 上的權(quán)定為 1。我們可以得到下面的加權(quán)有向圖：第16頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最短路問(wèn)題 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)化為在下面的二部圖中求從 v1 到 u1 的最短路問(wèn)題。v1v2v3v4v5u5u4u3u2u1第17頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最短路問(wèn)題 在 E.W.Dijkstra 算法中必須滿足一個(gè)條件 在圖 G 中所有邊的權(quán) lij 0。若在圖 G 中存在有負(fù)權(quán)邊（當(dāng)然，這種情形只針對(duì)有向圖而言）時(shí)必須對(duì)E.W.Dijkstra 算法加以修改 稱為修改的 E.W.Dijkstra 算法。第18頁(yè)/共59頁(yè)2、情況二：wij0設(shè)從V1到Vj(j=1,2,t)的最短路長(zhǎng)為P1jV1到Vj無(wú)任何中間點(diǎn) P1j（1）=wijV1到Vj中間最多經(jīng)過(guò)一個(gè)點(diǎn) P1j（2）=min P1j（1）+wijV1到Vj中間最多經(jīng)過(guò)兩個(gè)點(diǎn) P1j（3）=min P1j（2）+wij.V1到Vj中間最多經(jīng)過(guò)t-2個(gè)點(diǎn) P1j（t-1）=min P1j（t-2）+wij終止原則：1）當(dāng)P1j（k）=P1j（k+1）可停止，最短路P1j*=P1j（k）2）當(dāng)P1j（t-1）=P1j（t-2）時(shí)，再多迭代一次P1j（t），若P1j（t）=P1j（t-1），則原問(wèn)題無(wú)解，存在負(fù)回路。第19頁(yè)/共59頁(yè) 例：求下圖所示有向圖中從v1到各點(diǎn)的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第20頁(yè)/共59頁(yè) wij d(t)(v1,vj)v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v80 25-30-2406400-3 0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910說(shuō)明：表中空格處為說(shuō)明：表中空格處為+。4第21頁(yè)/共59頁(yè)例例 設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題制訂一設(shè)備更新問(wèn)題，使得總費(fèi)用最小制訂一設(shè)備更新問(wèn)題，使得總費(fèi)用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購(gòu)買費(fèi)購(gòu)買費(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,3,4,5)表示表示“第第i年初購(gòu)進(jìn)一臺(tái)年初購(gòu)進(jìn)一臺(tái)新設(shè)備新設(shè)備”這種狀態(tài)，以這種狀態(tài)，以v6表示表示“第第5年末年末”這種狀態(tài)；這種狀態(tài)；以弧以弧(vi,vj)表示表示“第第i年初購(gòu)置的一臺(tái)設(shè)備一直使用到年初購(gòu)置的一臺(tái)設(shè)備一直使用到第第j年初年初”這一方案，以這一方案，以wij表示這一方案所需購(gòu)置費(fèi)表示這一方案所需購(gòu)置費(fèi)和維護(hù)費(fèi)之和。和維護(hù)費(fèi)之和。第22頁(yè)/共59頁(yè)v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31,V1)(44,V1)(62,V1)(78,V3)第23頁(yè)/共59頁(yè)這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問(wèn)題就這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問(wèn)題就可歸結(jié)為從圖中找出一條從可歸結(jié)為從圖中找出一條從v1到到v6的最短路問(wèn)題。的最短路問(wèn)題。用用Dijkstra標(biāo)號(hào)法，求得最短路為標(biāo)號(hào)法，求得最短路為 v1v3v6 即第一年初購(gòu)置的設(shè)備使用到第三年初予以更新，即第一年初購(gòu)置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費(fèi)用最然后一直使用到第五年末。這樣五年的總費(fèi)用最少，為少，為78。第24頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法Dijkstra算法比較簡(jiǎn)單，但是，對(duì)于含有負(fù)權(quán)弧的網(wǎng)絡(luò)可能失效。這時(shí)，應(yīng)對(duì)算法加以修改，即所謂“修改的 Dijkstra 算法”。下面，介紹一種算法距離矩陣摹乘法，它適用于任何網(wǎng)絡(luò)的最短路問(wèn)題。例如v1v3v4v2v6v534233-24411-16333第25頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法1、網(wǎng)絡(luò)的距離矩陣設(shè)一網(wǎng)絡(luò)N中有n個(gè)點(diǎn)，其中任意兩點(diǎn) vi 與 vj 之間都有一條邊(vi,vj)，其權(quán)數(shù)為 wij -。若 vi 與 vj 不相鄰，則虛設(shè)一條邊(vi,vj)，并令其權(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第26頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法2、求各點(diǎn)至某點(diǎn)的最短路求 vi（i=1,2,n）至某點(diǎn) vr 的最短路。令：dir(k)=vi 走k步達(dá)到 vr 的最短距離，i=1,2,n則有 dir(1)=wir,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,第27頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法矩陣摹乘運(yùn)算法：dk=W dk-1 ,(k=2,3,)當(dāng) dk=dk-1,(k=2,3,)則計(jì)算停止，dk 中的元素即為各點(diǎn)到 vr 的最短距離。第28頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問(wèn)題一、基本概念 網(wǎng)絡(luò)最短距離矩陣 D=(dij)nn dij表示vi到vj的最短距離（1）網(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ò)的中心。第29頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問(wèn)題（2）網(wǎng)絡(luò)的重心 設(shè) gi 為點(diǎn) vi 的權(quán)重（i=1,2,n），令：令：h(vj)=gidij ,j=1,2,ni=1n若若 max h(vj)=h(vr)1jn則稱點(diǎn)則稱點(diǎn) vr 為網(wǎng)絡(luò)的重心。為網(wǎng)絡(luò)的重心。第30頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問(wèn)題二、應(yīng)用例 某地 7 個(gè)村鎮(zhèn)之間的現(xiàn)有交通道路如下圖，邊旁數(shù)值為各村鎮(zhèn)之間道路的長(zhǎng)度，點(diǎn)旁數(shù)值為各村鎮(zhèn)的小學(xué)生人數(shù)?，F(xiàn)擬在某一村鎮(zhèn)建一商店和小學(xué)，試問(wèn)：（1）商店應(yīng)該建在何村，能使各村都離它較近？（2）小學(xué)應(yīng)該建在何村，能使各村小學(xué)生總的行走路程最短？第31頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問(wèn)題v1v3v4v5v6v7v2746435712324230404535252050距離人數(shù)第32頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問(wèn)題（1）中心問(wèn)題 網(wǎng)絡(luò)最短距離矩陣如下：vj viD=(dij)d(vi)=max dij 123456710345781010230324577343055688452502355(min)57452013768563102871078532010j結(jié)論：結(jié)論：商店應(yīng)該建在商店應(yīng)該建在 v4 村。村。第33頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問(wèn)題（2）重心問(wèn)題 vj vi gidij123456710120160200280320400275075501001251753180135022522527036041506015006090150514080100400206062801752101053507075003504002501501000h(vj)13259201095870850(min)9251215結(jié)論：結(jié)論：小學(xué)應(yīng)該建在小學(xué)應(yīng)該建在 v5 村。村。第34頁(yè)/共59頁(yè)第四節(jié) 最大流問(wèn)題 如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問(wèn)：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234第35頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問(wèn)題定義1：定一個(gè)有向圖D=(V,E),在V中有一個(gè)發(fā)點(diǎn)vs和一收點(diǎn)vt，其余的點(diǎn)為中間點(diǎn)。對(duì)于每一條弧(vi,vj),對(duì)應(yīng)有一個(gè)c(vi,vj)0,(cij)稱為弧的容量。這樣的有向圖稱為容量網(wǎng)絡(luò)。記為D=(V,E,C)。1、網(wǎng)絡(luò)流義在弧集合E上的一個(gè)函數(shù)f=f(vi,vj)，稱f(vi,vj)為弧(vi,vj)上的流量，簡(jiǎn)記fij。2、可行流3、最大流4、增廣鏈5、最小截集第36頁(yè)/共59頁(yè)2、可行流與最大流、可行流與最大流定義定義2 滿足下列條件的流稱為滿足下列條件的流稱為可行流可行流：1)0 fij cij2)平衡條件：平衡條件：中間點(diǎn)中間點(diǎn) fij=fji(vi,vj)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)vt，(vj,vt)A式中v(f)稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。第37頁(yè)/共59頁(yè)最大流問(wèn)題：求一流最大流問(wèn)題：求一流fij滿足滿足0 fij cij v(f)i=s fij fji=0 i s，t v(f)i=t且使且使v(f)達(dá)到最大。達(dá)到最大。第38頁(yè)/共59頁(yè)3、增廣鏈、增廣鏈 給定可行流給定可行流f=fij，使，使fij=cij的弧稱為的弧稱為飽和弧飽和弧，使使fij0的弧稱為的弧稱為非零流弧非零流弧。若若 是網(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è)f是一可行流，是從vs到vt的一條鏈，若 滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)+上，0 fijcij 在弧(vi,vj)上，0fij cij第39頁(yè)/共59頁(yè) 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)第40頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問(wèn)題1、流量截量定理容量網(wǎng)絡(luò)上任何一個(gè)可行流的流量不超過(guò)任何一個(gè)截集的截量。2、增廣鏈調(diào)整定理在增廣鏈上對(duì)可行流進(jìn)行調(diào)整可以得到一個(gè)流量更大的可行流。3、最大流定理可行流是最大流的充分必要條件是不存在關(guān)于該可行流的增廣鏈。第41頁(yè)/共59頁(yè)步驟步驟：2、標(biāo)號(hào)過(guò)程標(biāo)號(hào)過(guò)程1、選取一個(gè)可行流（可選擇零流弧）、選取一個(gè)可行流（可選擇零流弧）從從Vs出發(fā)，出發(fā)，在在前向前向弧弧上上(vi,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)整，直至不存在增廣鏈為止。第42頁(yè)/共59頁(yè) 3、若標(biāo)號(hào)延續(xù)到、若標(biāo)號(hào)延續(xù)到vt，表明得到一條從，表明得到一條從vs到到vt的增的增廣鏈廣鏈，轉(zhuǎn)入調(diào)整階段，轉(zhuǎn)入調(diào)整階段4，否則當(dāng)前流即為最大流。，否則當(dāng)前流即為最大流。4、調(diào)整過(guò)程、調(diào)整過(guò)程令調(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)過(guò)程。入標(biāo)號(hào)過(guò)程。第43頁(yè)/共59頁(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)第44頁(yè)/共59頁(yè)vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例例 求下列網(wǎng)絡(luò)的最大流與最小截集。求下列網(wǎng)絡(luò)的最大流與最小截集。解解一、標(biāo)號(hào)過(guò)程一、標(biāo)號(hào)過(guò)程則則v1的標(biāo)號(hào)為的標(biāo)號(hào)為(vs,l(v1)，其中，其中第45頁(yè)/共59頁(yè)l(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,第46頁(yè)/共59頁(yè)則則vt的標(biāo)號(hào)為的標(biāo)號(hào)為(v3,l(vt)，其中，其中l(wèi)(vt)=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)第47頁(yè)/共59頁(yè)二、調(diào)整過(guò)程二、調(diào)整過(guò)程取調(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)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)第48頁(yè)/共59頁(yè) 在上圖中重復(fù)上述標(biāo)號(hào)過(guò)程，依次給在上圖中重復(fù)上述標(biāo)號(hào)過(guò)程，依次給vs,v2,v1,v4標(biāo)號(hào)標(biāo)號(hào)后，由于標(biāo)號(hào)無(wú)法繼續(xù)下去，算法結(jié)束。這時(shí)的流為最后，由于標(biāo)號(hào)無(wú)法繼續(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,vt,(V1,V1)=(v1,v3)，(v4,vt)第49頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問(wèn)題容量網(wǎng)絡(luò) N 上最大流的標(biāo)號(hào)（Ford-Fulkerson）算法：下面，我們采用此算法來(lái)求解前面的旅行總社計(jì)劃問(wèn)題案例第50頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最大流問(wèn)題 各辦事處已訂購(gòu)機(jī)票情況表成都成都vs重慶重慶v1武漢武漢v2上海上海v3西安西安v4鄭州鄭州v5沈陽(yáng)沈陽(yáng)v6昆明昆明v7廣州廣州v8北京北京vt成都成都 重慶重慶 武漢武漢 上海上海 西安西安 鄭州鄭州 沈陽(yáng)沈陽(yáng) 昆明昆明 廣州廣州 北京北京10 15 12 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 第51頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最大流問(wèn)題 發(fā)點(diǎn)vs=成都，收點(diǎn)vt=北京。前面已訂購(gòu)機(jī)票情況表中的數(shù)字即是各邊上的容量（允許通過(guò)的最大旅客量），當(dāng)各邊上的實(shí)際客流量為零時(shí)略去不寫，以零流作為初始可行流。重武昆上廣西鄭沈京成0，+標(biāo)號(hào)，但未檢查標(biāo)號(hào)，但且已檢查 vs，300+30第52頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最大流問(wèn)題重武昆上廣西鄭沈京成300，+vs，10vs，15vs，12vs，10vs，8vs，150，+v7，10v7，8vs，120+100+10第53頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最大流問(wèn)題重武昆上廣西鄭沈京成301066122841221061010000010801801000，+vs，8vs，13v2，4vs，13-v2，4 v1，4-v2，40+44-42+4v1，4第54頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最大流問(wèn)題重武昆上廣西鄭沈京成30106612280126106101000001080184100vs，8vs，9v2，40，+-v4，6vs，8 v1，6-v4，64+66-60+6vs，9第55頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最大流問(wèn)題重武昆上廣西鄭沈京成301006122801261061010600010801810100vs，90，+vs，2v2，4vs，9v3，4v2，4v5，4-v5，2v3，4-v5，2v5，4vs，2第56頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最大流問(wèn)題重武昆上廣西鄭沈京成301006122801261061010600010801810100v(f*)=10+6+12+30+12+10+6=86第57頁(yè)/共59頁(yè)圖與網(wǎng)絡(luò)模型Graph Theory最小費(fèi)用大流問(wèn)題五、最小費(fèi)用大流問(wèn)題 前面討論的旅行社的計(jì)劃問(wèn)題中，旅行社解決了將盡可能多的游客（86人）送往了目的地北京，但旅行社計(jì)劃時(shí)沒(méi)有考慮機(jī)票的成本?，F(xiàn)在旅行社考慮的問(wèn)題是既要送出盡可能多的游客（86人），又要使機(jī)票的總成本最低，應(yīng)該如何制定新的計(jì)劃呢？這就是最小費(fèi)用大流所研究解決的一類流量問(wèn)題。最小費(fèi)用大流問(wèn)題還廣泛應(yīng)用于諸如最優(yōu)匹配，運(yùn)輸問(wèn)題等一類問(wèn)題。應(yīng)該注意的是：最小費(fèi)用大流問(wèn)題首先要解決網(wǎng)絡(luò)上的最大流，目的是尋找使總費(fèi)用達(dá)到最小的那個(gè)最大流。第58頁(yè)/共59頁(yè)感謝您的觀看！第59頁(yè)/共59頁(yè)