圖論和網(wǎng)絡(luò)分析算法及Matlab實現(xiàn)(Graph_and_Network_Analysis)

1、圖論與網(wǎng)絡(luò)分析圖論與網(wǎng)絡(luò)分析 ( (Graph Theory and Network Analysis)Graph Theory and Network Analysis)一、圖論的基本概念一、圖論的基本概念 二、網(wǎng)絡(luò)分析算法二、網(wǎng)絡(luò)分析算法三、三、MatlabMatlab實現(xiàn)實現(xiàn)2022-3-15涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問題涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問題1、最短路問題、最短路問題貨柜車貨柜車司機司機奉命在最短的時間內(nèi)將一車貨物奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱縱橫交錯橫交錯，因此有多種行車路線，這名司機應(yīng)，因此有多種行車路線，這名

2、司機應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運行速度是選擇哪條線路呢？假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條恒定的，那么這一問題相當于需要找到一條從甲地到乙地的從甲地到乙地的最短路最短路。 2022-3-152 2、最小支撐樹問題最小支撐樹問題某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些路把這些城市連接城市連接起來，使得從其中任何一個城起來，使得從其中任何一個城市都可以經(jīng)高速公路市都可以經(jīng)高速公路直接或間接直接或間接到達另一個城市到達另一個城市。假定已經(jīng)知道了任意兩個城市之間修建。假定已經(jīng)知道了任意兩個城市之間修建高速公高速公路成本路

3、成本，那么應(yīng)如何決定在哪些城市間修建高速，那么應(yīng)如何決定在哪些城市間修建高速公路，使得公路，使得總成本最小總成本最??？2022-3-153 3、 指派問題指派問題Assignment problemAssignment problem 一家公司經(jīng)理一家公司經(jīng)理安排安排N N名員工去完成名員工去完成N N項任務(wù)，每項任務(wù)，每人一項。由于各員工的人一項。由于各員工的特點不同特點不同，不同的員工，不同的員工去完成同一項任務(wù)時所獲得的去完成同一項任務(wù)時所獲得的回報不同回報不同。如何。如何分配工作方案可以使總分配工作方案可以使總回報最大回報最大？ 2022-3-154 4、中國郵遞員問題、中國郵遞員問題

4、Chinese postman problemChinese postman problem一名一名郵遞員郵遞員負責(zé)投遞某個街區(qū)的郵件。如何為負責(zé)投遞某個街區(qū)的郵件。如何為他（她）設(shè)計一條最短的他（她）設(shè)計一條最短的投遞路線投遞路線（從郵局出（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次街道至少一次，最后返，最后返回郵局）？回郵局）？我國管梅谷教授我國管梅谷教授1960年首先提出，年首先提出，國際上稱之為中國郵遞員問題。國際上稱之為中國郵遞員問題。 2022-3-155 5 、旅行商問題、旅行商問題Traveling salesman problemTraveling sale

5、sman problem一名一名推銷員推銷員準備前往若干準備前往若干城市城市推銷產(chǎn)推銷產(chǎn)品。如何為他設(shè)計一條品。如何為他設(shè)計一條最短最短的旅行的旅行路線？路線？ （從駐地出發(fā)，經(jīng)過每個城（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）市恰好一次，最后返回駐地）2022-3-156 6、運輸問題、運輸問題Transportation problemTransportation problem 某種原材料有某種原材料有 M M個產(chǎn)地個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)，現(xiàn)在需要將原材料從產(chǎn)地運往地運往 N N個使用這些原材料的工廠。假定個使用這些原材料的工廠。假定 M M個產(chǎn)個產(chǎn)地的產(chǎn)量和地的產(chǎn)量和 N

6、 N家工廠家工廠的需要量已知，單位產(chǎn)品從的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸方案可以使總運輸成本運輸成本最低？最低？2022-3-15問題的兩個共同特點問題的兩個共同特點（1 1）目的都是從若干可能的安排或方案中尋求）目的都是從若干可能的安排或方案中尋求 某種意義下的某種意義下的最優(yōu)安排最優(yōu)安排或方案，數(shù)學(xué)問題稱或方案，數(shù)學(xué)問題稱 為最優(yōu)化或為最優(yōu)化或優(yōu)化問題優(yōu)化問題。（2 2）它們都可用）它們都可用圖形圖形形式直觀描述，數(shù)學(xué)上把這形式直觀描述，數(shù)學(xué)上把這 種與圖相關(guān)的結(jié)構(gòu)稱為種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)網(wǎng)

7、絡(luò)。圖和網(wǎng)絡(luò)相關(guān)圖和網(wǎng)絡(luò)相關(guān) 的最優(yōu)化問題就是的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化網(wǎng)絡(luò)最優(yōu)化。 網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)流為研究的對象，常網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)流為研究的對象，常 常被稱為網(wǎng)絡(luò)流或常被稱為網(wǎng)絡(luò)流或網(wǎng)絡(luò)流規(guī)劃網(wǎng)絡(luò)流規(guī)劃等。等。 一、圖論的基本概念1 . 圖與子圖11( ,),nmGV EVvvEee，其中為，圖頂點集為邊集。11111(,),GV EVV EE其中子圖。e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：簡單圖：無自環(huán)、無重邊的圖。2022-3-15 |V|=n表示圖G中節(jié)點個數(shù)為n，此節(jié)點個數(shù)n也稱為圖G的階 |E|=m表示圖G中邊的個

8、數(shù)為m 任一頂點相關(guān)聯(lián)的邊的數(shù)目稱為該頂點的度 完全圖：任意兩點有邊相連，用 表示 完全圖的邊，和每點的度是多少？nK2 . 關(guān)聯(lián)與相鄰121212, ,()ev vev vvve（邊與點關(guān)系）：若 是二點間的邊，記稱或聯(lián)與關(guān)關(guān)聯(lián)。12121212 vvvveeee（邊與邊、點與點）：點 與 有公共邊，稱 與 相鄰； 邊 與 有公共點，稱 與鄰接相鄰。n1110100110001000110100001101： 關(guān)聯(lián)矩陣： *m或者是m*n圖在計算機中的表示n0111101011011011鄰接矩陣： *n鄰接矩陣為對稱陣，簡單圖對角線元素為03 . 鏈與圈1 1 2 211 , Matlab

9、kkiiiGv ev eevev vG:由 中的某些點與邊相間構(gòu)成的序列，若滿足則稱此邊點序鏈列為 中的一條鏈。 鏈在中的存儲：只儲存頂點標號圈：封閉的鏈。G：圖 中任二點間至少存連通圖在一條鏈。4. 有向圖與無向圖 ( ,),(, , ). ,),kijijijGV EGvv vv vGGv v無向圖也可記若點對無序，稱 為；否則稱 為。為區(qū)別起見，稱有向圖圖有向圖弧的邊為，記（在圖上用箭線表示。），路有向圖：弧（，鏈無向圖：邊,，圈，回路比較：1ijijavv 有向圖的存儲：行為起點，列為終點存在弧賦權(quán)圖：邊有長度v1v2v3v5v4834217 W= .41 .99 .51 .32 .1

10、5 .45 .38 .32 .36 .29 .21 ;DG=sparse6 1 2 2 3 4 4 5 5 6 1 , 2 6 3 5 4 1 6 3 4 3 5 ,Wview(biograph(DG,ShowWeights,on)UG tril DG DGview(biograph(UG,ShowWeights,on)；賦權(quán)圖在Matlab中的存儲：5. 樹 例1 已知有5個城市，要在它們之間架設(shè)電話線網(wǎng)，要求任2城市都可通話（允許通過其它城市），并且電話線的根數(shù)最少。v1v2v3v5v4 特點：連通、無圈。樹無圈的連通圖，記為T。v1v2v3v5v4樹的性質(zhì)：（1）樹的任2點間有且僅有1鏈

11、； （2）在樹中任去掉1邊，則不連通； （3）在樹中不相鄰2點間添1邊，恰成1圈； （4）若樹T有n個頂點，則T有n-1條邊。6.圖的支撐樹 若圖G=（V，E）的子圖T=（V，E）是樹，則稱T為G的支撐樹。特點邊少、點不少。性質(zhì)：G連通，則G必有支撐樹。證：破圈、保連通。二、網(wǎng)絡(luò)分析網(wǎng)絡(luò)賦權(quán)圖，記D=（V，E，C），其中C=c1，cn， ci為邊ei上的權(quán)（設(shè)ci ）。網(wǎng)絡(luò)分析主要內(nèi)容: 最小支撐樹 最短路 最大流。0一. 最小支撐樹問題問題：求網(wǎng)絡(luò)D的支撐樹，使其權(quán)和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如圖網(wǎng)絡(luò)的最小支撐樹。v5v1v3v6v

12、4v2v7255233575711Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7, 48-50. 避圈法是一種選邊的過程，其步驟如下：1. 從網(wǎng)絡(luò)D中任選一點vi，找出與vi相關(guān)聯(lián)的 權(quán)最小的邊vi，vj，得第二個頂點vj；2. 把頂點集V分為互補的兩部分V1, 1 ，其中V集；不與已選邊相關(guān)聯(lián)的點，與已選邊相關(guān)聯(lián)的點集， 11VV其中權(quán)最

13、小的；挑選其中考慮所有這樣的邊 , 3.11svsvvvjiji。即，直至全部頂點屬于重復(fù))(3 4.11ss2022-3-15對對G中各邊按權(quán)大小順序排列，不妨設(shè)為中各邊按權(quán)大小順序排列，不妨設(shè)為W1 W2 Wm填寫填寫Wj對應(yīng)的各邊對應(yīng)的各邊aj S= ，i = 0，j=1aj S構(gòu)成回路？構(gòu)成回路？|S| = n-1= n-1ei+1=aj S=ei+1 Si=i +1 j=j+1j=j+1T*=S打印打印T*ENDYYNN用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分樹如圖上紅線所示；最小權(quán)和為14。思考：破圈法是怎樣做的呢？見圈就破，去掉其中權(quán)最大的。最小

14、支撐樹問題的應(yīng)用例子 已知有A、B、C、D、E、F六個城鎮(zhèn)間的道路網(wǎng)絡(luò) 如圖，現(xiàn)要在六個城鎮(zhèn)間架設(shè)通訊網(wǎng)絡(luò)（均沿道路架設(shè)），每段道路上的架設(shè)費用如圖。求能保證各城鎮(zhèn)均能通話且總架設(shè)費用最少的架設(shè)方案。6EACBFD5109353978284二. 最短路問題1. 問題：求網(wǎng)絡(luò)D中一定點v1到其它點的最短路。 例3 求如圖網(wǎng)絡(luò)中v1至v7的最短路，圖中數(shù)字為兩點間距離。v5v1v3v6v4v2v72552335757112022-3-15 2. 方法：Dijkstra算法（Dijkstra，1959） Dijkstra, E.W. (1959). A note on two problems in

15、 connexion with graphs. Numerische Mathematik 1, 269271. 原理： Bellman最優(yōu)化原理 若P是網(wǎng)絡(luò)G中從Vs到Vt的一條最短路，Vl是P中除Vs與Vt外的任何一個中間點，則沿P從Vs到Vl的一條路P1亦必是Vs到Vl的最短路。 證明（反證）： 若P1不是從Vs到Vl的最短路，則存在另一條 Vs到Vl的路P2使W(P2)W(P1)，若記路P中從Vl到Vt的路為P3。則有W(P2)+W(P3) 300 300米米) ) 對坡度對坡度的限制的限制 0.125= 0 0.100 2022-3-15模型計算方法模型計算方法 (1) (1) 對地

16、圖網(wǎng)格加密，形成圖。對地圖網(wǎng)格加密，形成圖。 (2) (2) 計算網(wǎng)格的距離，用費用作為權(quán)值。計算網(wǎng)格的距離，用費用作為權(quán)值。 (3) (3) 求賦權(quán)圖兩點間的最短距離。求賦權(quán)圖兩點間的最短距離。 2022-3-15參考答案參考答案2022-3-15 災(zāi)情巡視路線，下圖為某縣的鄉(xiāng)（鎮(zhèn)）、災(zāi)情巡視路線，下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視關(guān)部門負責(zé)人到全縣各鄉(xiāng)（

17、鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。路線。2022-3-15若分三組（路）巡視，試設(shè)計總路程最短且各組盡可若分三組（路）巡視，試設(shè)計總路程最短且各組盡可能均衡的巡視路線。能均衡的巡視路線。 假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2T=2小時，在各小時，在各村停留時間村停留時間t=1t=1小時，汽車行駛速度小時，汽車行駛速度V=35V=35公里公里/ /小時。小時。要在要在2424小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分小時內(nèi)完成巡視，至少應(yīng)

18、分幾組；給出這種分組下你認為最佳的巡視路線。組下你認為最佳的巡視路線。若巡視組數(shù)已定若巡視組數(shù)已定(如三組如三組)，要求盡快完成巡視，討論，要求盡快完成巡視，討論T，t和和V改變對最佳巡視路線的影響。改變對最佳巡視路線的影響。 上述關(guān)于上述關(guān)于T , t和和V的假定下，如果巡視人員足夠多，的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認為最佳的巡視路線。成巡視的要求下，你認為最佳的巡視路線。2022-3-15鄉(xiāng)村分布圖鄉(xiāng)村分布圖2022-3-15點的行遍性問題點的行遍性問題1 1、圖論、圖論-哈密爾頓

19、問題（是否存在經(jīng)過所有點一次的圈）哈密爾頓問題（是否存在經(jīng)過所有點一次的圈）2 2、組合優(yōu)化、組合優(yōu)化-旅行商問題（賦權(quán)圖經(jīng)過所有頂點至少一次）旅行商問題（賦權(quán)圖經(jīng)過所有頂點至少一次） 非完全圖的多旅行商問題非完全圖的多旅行商問題v 兩點間的最短路長度作為兩點間的權(quán)，構(gòu)造完全圖。兩點間的最短路長度作為兩點間的權(quán)，構(gòu)造完全圖。v 兩邊權(quán)之和不小于第三邊的權(quán)兩邊權(quán)之和不小于第三邊的權(quán)=v 完全圖的最優(yōu)哈密爾頓圈完全圖的最優(yōu)哈密爾頓圈=原圖的最優(yōu)旅行商問題。原圖的最優(yōu)旅行商問題。v 完全圖完全圖-增廣完全圖增廣完全圖=求最優(yōu)哈密爾頓圈求最優(yōu)哈密爾頓圈v 近似算法或分組后直接搜索近似算法或分組后直接搜

20、索v 注意注意（1 1） 兩點間的最短路長度可用兩點間的最短路長度可用DijkstraDijkstra算法算法（2 2） 多旅行商問題多旅行商問題=最優(yōu)哈密爾頓圈最優(yōu)哈密爾頓圈2022-3-15線性規(guī)劃模型線性規(guī)劃模型2022-3-15問題解答：問題解答：1 1、分三組（路）巡視，試設(shè)計總路程最短且分三組（路）巡視，試設(shè)計總路程最短且 各組盡可能均衡的巡視路線。各組盡可能均衡的巡視路線。 目標函數(shù)：目標函數(shù)： min(C1+C2+C3)min(C1+C2+C3) 限制條件：限制條件：min(C3 - C1)min(C3 - C1) 或或 者者 ：min(C1)min(C1)2、假定巡視人員在各

21、鄉(xiāng)（鎮(zhèn)）停留時間假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2T=2小時小時，在各村停留時間，在各村停留時間t=1t=1小時，汽車行駛速度小時，汽車行駛速度V=35V=35公里公里/ /小時。要在小時。要在2424小時內(nèi)完成巡視，至少應(yīng)分小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線幾組；給出這種分組下最佳的巡視路線。2022-3-15 目標函數(shù)：目標函數(shù)： min(H1+H2+H3)min(H1+H2+H3) 花費時間：花費時間：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V 限制條件：限制條件：min(max(Hi)min(max(Hi)總時間總時間6969小時小時=至少至少

22、4 4組，組，4 4組的路線可以找到。組的路線可以找到。3 3、在上述關(guān)于在上述關(guān)于T , tT , t和和V V的假定下，如果巡視人員足夠多，完成的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認為最佳的巡視路線。下，你認為最佳的巡視路線。 單獨巡視的最短時間單獨巡視的最短時間= =最遠距離最遠距離 （1）每組時間不超過最遠距離時間）每組時間不超過最遠距離時間 （2）巡視組足夠少，）巡視組足夠少，2222組組4 4、 若巡視組數(shù)已定若巡視組數(shù)已定( (如三組如三組) )，要求盡快完成巡視，討論

23、，要求盡快完成巡視，討論T T，t t和和 V V改變對最佳巡視路線的影響。改變對最佳巡視路線的影響。 討論花費時間函數(shù)：討論花費時間函數(shù)：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V注意：多旅行商問題注意：多旅行商問題=單旅行商問題（單旅行商問題（LING2LING2）2022-3-15DVD在在線租賃線租賃隨著信息時代的到來，網(wǎng)絡(luò)成為人們生活中越來越不可或缺的元素之一。許隨著信息時代的到來，網(wǎng)絡(luò)成為人們生活中越來越不可或缺的元素之一。許多網(wǎng)站利用其強大的資源和知名度，面向其會員群提供日益專業(yè)化和便捷化多網(wǎng)站利用其強大的資源和知名度，面向其會員群提供日益專業(yè)化和便捷化的服務(wù)。例如

24、，音像制品的在線租賃就是一種可行的服務(wù)。這項服務(wù)充分發(fā)的服務(wù)。例如，音像制品的在線租賃就是一種可行的服務(wù)。這項服務(wù)充分發(fā)揮了網(wǎng)絡(luò)的諸多優(yōu)勢，包括傳播范圍廣泛、直達核心消費群、強烈的互動性、揮了網(wǎng)絡(luò)的諸多優(yōu)勢，包括傳播范圍廣泛、直達核心消費群、強烈的互動性、感官性強、成本相對低廉等，為顧客提供更為周到的服務(wù)。感官性強、成本相對低廉等，為顧客提供更為周到的服務(wù)?？紤]如下的在線考慮如下的在線DVD租賃問題。顧客繳納一定數(shù)量的月費成為會員，訂購租賃問題。顧客繳納一定數(shù)量的月費成為會員，訂購DVD租賃服務(wù)。會員對哪些租賃服務(wù)。會員對哪些DVD有興趣，只要在線提交訂單，網(wǎng)站就會通過有興趣，只要在線提交訂單

25、，網(wǎng)站就會通過快遞的方式盡可能滿足要求。會員提交的訂單包括多張快遞的方式盡可能滿足要求。會員提交的訂單包括多張DVD，這些這些DVD是基是基于其偏愛程度排序的。網(wǎng)站會根據(jù)手頭現(xiàn)有的于其偏愛程度排序的。網(wǎng)站會根據(jù)手頭現(xiàn)有的DVD數(shù)量和會員的訂單進行分數(shù)量和會員的訂單進行分發(fā)。每個會員每個月租賃次數(shù)不得超過發(fā)。每個會員每個月租賃次數(shù)不得超過2次，每次獲得次，每次獲得3張張DVD。會員看完會員看完3張張DVD之后，只需要將之后，只需要將DVD放進網(wǎng)站提供的信封里寄回（郵費由網(wǎng)站承擔），放進網(wǎng)站提供的信封里寄回（郵費由網(wǎng)站承擔），就可以繼續(xù)下次租賃。請考慮以下問題：就可以繼續(xù)下次租賃。請考慮以下問題：2022-3-151) 1) 網(wǎng)站正準備購買一些新的網(wǎng)站正準備購買一些新的DVD，通過問卷調(diào)查通過問卷調(diào)查1000個會員，得到了愿意觀個會員，得到了愿意