1、圖論與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis)一、圖論的基本概念 二、網(wǎng)絡(luò)分析算法三、Matlab實現(xiàn)2022/9/21涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問題1、最短路問題貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。 2022/9/212、最小支撐樹問題某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假定已經(jīng)知道了任意兩個

2、城市之間修建高速公路成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最?。?022/9/213、 指派問題Assignment problem 一家公司經(jīng)理安排N名員工去完成N項任務(wù)，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務(wù)時所獲得的回報不同。如何分配工作方案可以使總回報最大？ 2022/9/214、中國郵遞員問題Chinese postman problem一名郵遞員負(fù)責(zé)投遞某個街區(qū)的郵件。如何為他（她）設(shè)計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？我國管梅谷教授1960年首先提出，國際上稱之為中國郵遞員問題。 2022/9/21

3、5 、旅行商問題Traveling salesman problem一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他設(shè)計一條最短的旅行路線？ （從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）2022/9/216、運輸問題Transportation problem 某種原材料有 M個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往 N個使用這些原材料的工廠。假定 M個產(chǎn)地的產(chǎn)量和 N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？2022/9/21問題的兩個共同特點（1）目的都是從若干可能的安排或方案中尋求 某種意義下的最優(yōu)安排或方案，數(shù)學(xué)問題稱 為最優(yōu)化或

4、優(yōu)化問題。（2）它們都可用圖形形式直觀描述，數(shù)學(xué)上把這 種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)。圖和網(wǎng)絡(luò)相關(guān) 的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化。 網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)流為研究的對象，常 常被稱為網(wǎng)絡(luò)流或網(wǎng)絡(luò)流規(guī)劃等。 2022/9/21 一、圖論的基本概念1 . 圖與子圖e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：簡單圖：無自環(huán)、無重邊的圖。2022/9/21|V|=n表示圖G中節(jié)點個數(shù)為n，此節(jié)點個數(shù)n也稱為圖G的階|E|=m表示圖G中邊的個數(shù)為m任一頂點相關(guān)聯(lián)的邊的數(shù)目稱為該頂點的度完全圖：任意兩點有邊相連，用 表示 完全圖的邊，和每點的度是多少？2022/9

5、/212 . 關(guān)聯(lián)與相鄰2022/9/212022/9/213 . 鏈與圈2022/9/214. 有向圖與無向圖，圈，回路比較：2022/9/21v1v2v3v5v48342172022/9/212022/9/215. 樹 例1 已知有5個城市，要在它們之間架設(shè)電話線網(wǎng)，要求任2城市都可通話（允許通過其它城市），并且電話線的根數(shù)最少。v1v2v3v5v4 特點：連通、無圈。樹無圈的連通圖，記為T。2022/9/21v1v2v3v5v4樹的性質(zhì)：（1）樹的任2點間有且僅有1鏈； （2）在樹中任去掉1邊，則不連通； （3）在樹中不相鄰2點間添1邊，恰成1圈； （4）若樹T有n個頂點，則T有n-1條

6、邊。2022/9/216.圖的支撐樹 若圖G=（V，E）的子圖T=（V，E）是樹，則稱T為G的支撐樹。特點邊少、點不少。性質(zhì)：G連通，則G必有支撐樹。證：破圈、保連通。2022/9/21二、網(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)容: 最小支撐樹 最短路 最大流。2022/9/21一. 最小支撐樹問題問題：求網(wǎng)絡(luò)D的支撐樹，使其權(quán)和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如圖網(wǎng)絡(luò)的最小支撐樹。v5v1v3v6v4v2v7255233575711Kruskal, J.B. (195

7、6). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7, 48-50. 2022/9/21避圈法是一種選邊的過程，其步驟如下：1. 從網(wǎng)絡(luò)D中任選一點vi，找出與vi相關(guān)聯(lián)的 權(quán)最小的邊vi，vj，得第二個頂點vj；2. 把頂點集V分為互補的兩部分V1, 1 ，其中2022/9/21對G中各邊按權(quán)大小順序排列，不妨設(shè)為W1 W2 Wm填寫Wj對應(yīng)的各邊aj S= ，i = 0，j=1

8、aj S構(gòu)成回路？|S| = n-1ei+1=aj S=ei+1 Si=i +1 j=j+1j=j+1T*=S打印T*ENDYYNN2022/9/21用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分樹如圖上紅線所示；最小權(quán)和為14。思考：破圈法是怎樣做的呢？見圈就破，去掉其中權(quán)最大的。2022/9/21最小支撐樹問題的應(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è)方案。6EACBFD51093539782842022/9/21二. 最

9、短路問題1. 問題：求網(wǎng)絡(luò)D中一定點v1到其它點的最短路。 例3 求如圖網(wǎng)絡(luò)中v1至v7的最短路，圖中數(shù)字為兩點間距離。v5v1v3v6v4v2v72552335757112022/9/212. 方法：Dijkstra算法（Dijkstra，1959） Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269271. 原理： Bellman最優(yōu)化原理 若P是網(wǎng)絡(luò)G中從Vs到Vt的一條最短路，Vl是P中除Vs與Vt外的任何一個中間點，則沿P從Vs到Vl的

10、一條路P1亦必是Vs到Vl的最短路。 證明（反證）： 若P1不是從Vs到Vl的最短路，則存在另一條 Vs到Vl的路P2使W(P2)W(P1)，若記路P中從Vl到Vt的路為P3。則有W(P2)+W(P3) 300米) 對坡度的限制 0.125= 0 0.100 2022/9/21模型計算方法 (1) 對地圖網(wǎng)格加密，形成圖。 (2)計算網(wǎng)格的距離，用費用作為權(quán)值。 (3) 求賦權(quán)圖兩點間的最短距離。 2022/9/21參考答案2022/9/211998年全國大學(xué)生數(shù)學(xué)建模競賽 災(zāi)情巡視路線，下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織

11、自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。2022/9/21若分三組（路）巡視，試設(shè)計總路程最短且各組盡可能均衡的巡視路線。 假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。若巡視組數(shù)已定(如三組)，要求盡快完成巡視，討論T，t和V改變對最佳巡視路線的影響。 上述關(guān)于T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你

12、認(rèn)為最佳的巡視路線。2022/9/21鄉(xiāng)村分布圖2022/9/21點的行遍性問題1、圖論-哈密爾頓問題（是否存在經(jīng)過所有點一次的圈）2、組合優(yōu)化-旅行商問題（賦權(quán)圖經(jīng)過所有頂點至少一次） 非完全圖的多旅行商問題兩點間的最短路長度作為兩點間的權(quán)，構(gòu)造完全圖。兩邊權(quán)之和不小于第三邊的權(quán)=完全圖的最優(yōu)哈密爾頓圈=原圖的最優(yōu)旅行商問題。完全圖-增廣完全圖=求最優(yōu)哈密爾頓圈近似算法或分組后直接搜索注意（1） 兩點間的最短路長度可用Dijkstra算法（2） 多旅行商問題=最優(yōu)哈密爾頓圈2022/9/21線性規(guī)劃模型2022/9/21問題解答：1、分三組（路）巡視，試設(shè)計總路程最短且 各組盡可能均衡的巡視

13、路線。 目標(biāo)函數(shù)： min(C1+C2+C3) 限制條件：min(C3 - C1) 或 者 ：min(C1)2、假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線。2022/9/21 目標(biāo)函數(shù)： min(H1+H2+H3) 花費時間：Hi=2mi+ni+Ci/V 限制條件：min(max(Hi)總時間69小時=至少4組，4組的路線可以找到。3、在上述關(guān)于T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認(rèn)為最佳的巡視路線

14、。 單獨巡視的最短時間=最遠距離 （1）每組時間不超過最遠距離時間 （2）巡視組足夠少，22組4、 若巡視組數(shù)已定(如三組)，要求盡快完成巡視，討論T，t和 V改變對最佳巡視路線的影響。 討論花費時間函數(shù)：Hi=2mi+ni+Ci/V注意：多旅行商問題=單旅行商問題（LINGO）2022/9/212005年全國大學(xué)生數(shù)學(xué)建模競賽DVD在線租賃隨著信息時代的到來，網(wǎng)絡(luò)成為人們生活中越來越不可或缺的元素之一。許多網(wǎng)站利用其強大的資源和知名度，面向其會員群提供日益專業(yè)化和便捷化的服務(wù)。例如，音像制品的在線租賃就是一種可行的服務(wù)。這項服務(wù)充分發(fā)揮了網(wǎng)絡(luò)的諸多優(yōu)勢，包括傳播范圍廣泛、直達核心消費群、強烈

15、的互動性、感官性強、成本相對低廉等，為顧客提供更為周到的服務(wù)。考慮如下的在線DVD租賃問題。顧客繳納一定數(shù)量的月費成為會員，訂購DVD租賃服務(wù)。會員對哪些DVD有興趣，只要在線提交訂單，網(wǎng)站就會通過快遞的方式盡可能滿足要求。會員提交的訂單包括多張DVD，這些DVD是基于其偏愛程度排序的。網(wǎng)站會根據(jù)手頭現(xiàn)有的DVD數(shù)量和會員的訂單進行分發(fā)。每個會員每個月租賃次數(shù)不得超過2次，每次獲得3張DVD。會員看完3張DVD之后，只需要將DVD放進網(wǎng)站提供的信封里寄回（郵費由網(wǎng)站承擔(dān)），就可以繼續(xù)下次租賃。請考慮以下問題：2022/9/211) 網(wǎng)站正準(zhǔn)備購買一些新的DVD，通過問卷調(diào)查1000個會員，得到了愿意觀看這些DVD的人數(shù)（表1給出了其中5種DVD的數(shù)據(jù)）。此外，歷史數(shù)據(jù)顯示，60%的會員每月租賃DVD兩次，而另外的40%只租一次。假設(shè)網(wǎng)站現(xiàn)有10萬個會員，對表1中的每種DVD來說，應(yīng)該至少準(zhǔn)備多少張，才能保證希望看到該DVD的會員中至少50%在一個月內(nèi)能夠看到該DVD？如果要求保證在三個月內(nèi)至少95%的會員能夠看到該DVD呢？2） 表2中列出了網(wǎng)站手上100種DVD的現(xiàn)有張數(shù)和當(dāng)前需要處理的1000位會員的在線訂單（表2的數(shù)據(jù)格式示例如下表2，具體數(shù)據(jù)請下），如何