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

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

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

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

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

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

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

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

9、kkiiiGv ev eevev vG:由 中的某些點與邊相間構成的序列，若滿足則稱此邊點序鏈列為 中的一條鏈。 鏈在中的存儲：只儲存頂點標號圈：封閉的鏈。G：圖 中任二點間至少存連通圖在一條鏈。4. 有向圖與無向圖 ( ,),(, , ). ,),kijijijGV EGvv vv vGGv v無向圖也可記若點對無序，稱 為；否則稱 為。為區別起見，稱有向圖圖有向圖弧的邊為，記（在圖上用箭線表示。），路有向圖：弧（，鏈無向圖：邊,，圈，回路比較：1ijijavv 有向圖的存儲：行為起點，列為終點存在弧賦權圖：邊有長度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)；賦權圖在Matlab中的存儲：5. 樹 例1 已知有5個城市，要在它們之間架設電話線網，要求任2城市都可通話（允許通過其它城市），并且電話線的根數最少。v1v2v3v5v4 特點：連通、無圈。樹無圈的連通圖，記為T。v1v2v3v5v4樹的性質：（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的支撐樹。特點邊少、點不少。性質：G連通，則G必有支撐樹。證：破圈、保連通。二、網絡分析網絡賦權圖，記D=（V，E，C），其中C=c1，cn， ci為邊ei上的權（設ci ）。網絡分析主要內容: 最小支撐樹 最短路 最大流。0一. 最小支撐樹問題問題：求網絡D的支撐樹，使其權和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如圖網絡的最小支撐樹。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. 從網絡D中任選一點vi，找出與vi相關聯的 權最小的邊vi，vj，得第二個頂點vj；2. 把頂點集V分為互補的兩部分V1, 1 ，其中V集；不與已選邊相關聯的點，與已選邊相關聯的點集， 11VV其中權最

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

14、支撐樹問題的應用例子 已知有A、B、C、D、E、F六個城鎮間的道路網絡 如圖，現要在六個城鎮間架設通訊網絡（均沿道路架設），每段道路上的架設費用如圖。求能保證各城鎮均能通話且總架設費用最少的架設方案。6EACBFD5109353978284二. 最短路問題1. 問題：求網絡D中一定點v1到其它點的最短路。 例3 求如圖網絡中v1至v7的最短路，圖中數字為兩點間距離。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最優化原理 若P是網絡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、圖網格加密，形成圖。對地圖網格加密，形成圖。 (2) (2) 計算網格的距離，用費用作為權值。計算網格的距離，用費用作為權值。 (3) (3) 求賦權圖兩點間的最短距離。求賦權圖兩點間的最短距離。 2022-3-15參考答案參考答案2022-3-15 災情巡視路線，下圖為某縣的鄉（鎮）、災情巡視路線，下圖為某縣的鄉（鎮）、村公路網示意圖，公路邊的數字為該路段村公路網示意圖，公路邊的數字為該路段的公里數。今年夏天該縣遭受水災。為考的公里數。今年夏天該縣遭受水災。為考察災情、組織自救，縣領導決定，帶領有察災情、組織自救，縣領導決定，帶領有關部門負責人到全縣各鄉（鎮）、村巡視關部門負責人到全縣各鄉（

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

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

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

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

21、鄉（鎮）停留時間假定巡視人員在各鄉（鎮）停留時間T=2T=2小時小時，在各村停留時間，在各村停留時間t=1t=1小時，汽車行駛速度小時，汽車行駛速度V=35V=35公里公里/ /小時。要在小時。要在2424小時內完成巡視，至少應分小時內完成巡視，至少應分幾組；給出這種分組下最佳的巡視路線幾組；給出這種分組下最佳的巡視路線。2022-3-15 目標函數：目標函數： 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、在上述關于在上述關于T , tT , t和和V V的假定下，如果巡視人員足夠多，完成的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認為最佳的巡視路線。下，你認為最佳的巡視路線。 單獨巡視的最短時間單獨巡視的最短時間= =最遠距離最遠距離 （1）每組時間不超過最遠距離時間）每組時間不超過最遠距離時間 （2）巡視組足夠少，）巡視組足夠少，2222組組4 4、 若巡視組數已定若巡視組數已定( (如三組如三組) )，要求盡快完成巡視，討論

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

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

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