圖論和網(wǎng)絡(luò)分析算法及Matlab實現(xiàn)(Graph-and-Network-Analysis)

圖論與網(wǎng)絡(luò)分析

(GraphTheoryandNetworkAnalysis)一、圖論的基本概念

二、網(wǎng)絡(luò)分析算法三、Matlab實現(xiàn)2024/7/5涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問題1、最短路問題貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。

2024/7/52、最小支撐樹問題某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達(dá)另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？2024/7/53、指派問題

Assignmentproblem

一家公司經(jīng)理安排N名員工去完成N項任務(wù)，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務(wù)時所獲得的回報不同。如何分配工作方案可以使總回報最大？

2024/7/54、中國郵遞員問題

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

2024/7/55、旅行商問題

Travelingsalesmanproblem一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他設(shè)計一條最短的旅行路線？（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）2024/7/56、運輸問題

Transportationproblem某種原材料有M個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往N個使用這些原材料的工廠。假定M個產(chǎn)地的產(chǎn)量和N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？2024/7/5問題的兩個共同特點（1）目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)問題稱為最優(yōu)化或優(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ī)劃等。

2024/7/5一、圖論的基本概念1.圖與子圖e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如

G：簡單圖：無自環(huán)、無重邊的圖。2024/7/5|V|=n表示圖G中節(jié)點個數(shù)為n，此節(jié)點個數(shù)n也稱為圖G的階|E|=m表示圖G中邊的個數(shù)為m任一頂點相關(guān)聯(lián)的邊的數(shù)目稱為該頂點的度完全圖：任意兩點有邊相連，用表示完全圖的邊，和每點的度是多少？2024/7/52.關(guān)聯(lián)與相鄰2024/7/52024/7/53.鏈與圈2024/7/54.有向圖與無向圖，圈，回路比較：2024/7/5v1v2v3v5v48342172024/7/52024/7/55.樹

例1已知有5個城市，要在它們之間架設(shè)電話線網(wǎng)，要求任2城市都可通話（允許通過其它城市），并且電話線的根數(shù)最少。v1v2v3v5v4

特點：連通、無圈。樹——無圈的連通圖，記為T。2024/7/5v1v2v3v5v4樹的性質(zhì)：（1）樹的任2點間有且僅有1鏈；（2）在樹中任去掉1邊，則不連通；（3）在樹中不相鄰2點間添1邊，恰成1圈；（4）若樹T有n個頂點，則T有n-1條邊。2024/7/56.圖的支撐樹

若圖G=（V，E）的子圖T=（V，E’）是樹，則稱T為G的支撐樹。特點——邊少、點不少。性質(zhì)：G連通，則G必有支撐樹。證：破圈、保連通。2024/7/5二、網(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)容:

最小支撐樹

最短路

最大流。2024/7/5一.最小支撐樹問題問題：求網(wǎng)絡(luò)D的支撐樹，使其權(quán)和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例2求如圖網(wǎng)絡(luò)的最小支撐樹。v5v1v3v6v4v2v7255233575711Kruskal,J.B.(1956).OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem.ProceedingsoftheAmericanMathematicalSociety7,48-50.

2024/7/5避圈法是一種選邊的過程，其步驟如下：1.從網(wǎng)絡(luò)D中任選一點vi，找出與vi相關(guān)聯(lián)的權(quán)最小的邊[vi，vj]，得第二個頂點vj；2.把頂點集V分為互補的兩部分V1,1，其中2024/7/5對G中各邊按權(quán)大小順序排列，不妨設(shè)為W1≤W2≤

…

≤Wm填寫Wj對應(yīng)的各邊aj

S=φ，i=0，j=1{aj}∪S構(gòu)成回路？|S|=n-1ei+1=ajS={ei+1}∪Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN2024/7/5用避圈法解例2v5v1v3v6v4v2v7255233575711?最小部分樹如圖上紅線所示；最小權(quán)和為14。思考：破圈法是怎樣做的呢？——見圈就破，去掉其中權(quán)最大的。2024/7/5最小支撐樹問題的應(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è)方案。6EACBFD51093539782842024/7/5二.最短路問題1.問題：求網(wǎng)絡(luò)D中一定點v1到其它點的最短路。例3求如圖網(wǎng)絡(luò)中v1至v7的最短路，圖中數(shù)字為兩點間距離。v5v1v3v6v4v2v72552335757112024/7/52.方法：Dijkstra算法（Dijkstra，1959）Dijkstra,E.W.(1959).Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik1,269–271.原理：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)<W(P1)+W(P3)=W(P)，此說明G中存在一條從Vs沿P2到Vl沿P3再到Vt的更短的一條路，這與P使G中從Vs到Vt的一條最短路矛盾。2024/7/5算法思想：設(shè)G中從Vs到Vt的最小路P：Vs…Vj…Vk…Vt，則P不僅是從Vs到Vt的最小路，而且從Vs到P中任意中間點的最短路也在P上，為此可采用如下求解步驟：⑴為求得Vs到Vt的最短路，可先求得Vs到中間點的最短路，然后由中間點再逐步過渡到終點Vt。

⑵在計算過程中，需要把V中“經(jīng)判斷為最短路P途徑之點i”和“尚未判斷是否為最短路P途徑之點j”區(qū)分開來，可設(shè)置集合I和J,前者歸入I，后者歸入J，并令算法初始時，I中僅包含Vs，其他點全在J中，然后隨著求解過程的進(jìn)行，I中的點逐漸增加（相應(yīng)J中的點逐漸減少），直到終點Vt歸入I（相應(yīng)J=φ），此時迭代結(jié)束。I稱為已標(biāo)號集合,J稱為未標(biāo)號集合。2024/7/5⑶為區(qū)分中間點Vk是否已歸入I中以及逆向求解最短路的方便，可在歸入I中的點Vj上方給予雙標(biāo)號（lj,Vk），此中l(wèi)j表示從Vs到Vj最短路的距離，而Vk則為從Vs到Vj最短路P中Vj的前一途徑點。⑷為在計算機上實現(xiàn)上述求解思想，還需引入G中各點間一步可達(dá)距離陣D=(dij)n×n，其中|V|=n

2024/7/5由圖G建立一步可達(dá)距離陣D=(dij)n×n給V1(Vs)括號(l1,Vk)=(0,s)給出已標(biāo)號集合I和未標(biāo)號集合J的元素對于給定的I和J，確定集合A={aij|Vi∈I，Vj∈J}

計算距離給Vk括號(lk,Vh)lk=lh+WhkI=I+{Vk}J=J–{Vk}A=φ或J＝φ從Vt

逆向搜索雙括號，可得最小路P途徑各點及最小路距離ENDNYDijkstra算法2024/7/5用標(biāo)號法解例3v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1][4，v2][7，v3][8，v5][13，v6]最短距為13；最短路為v1-v2-v3-v5-v6-v7。2024/7/52024/7/5迭代過程2024/7/5最短路問題應(yīng)用廠址選擇廠址布局設(shè)備更新網(wǎng)絡(luò)線路安裝工程設(shè)計企業(yè)管理2024/7/5最短路問題的應(yīng)用例子

某汽車公司正在制訂5年內(nèi)購買汽車的計劃。下面給出一輛新汽車的價格以及一輛汽車的使用維修費用(萬元)：

年份 1 2 3 4 5年初價格 11 11 12 12 13

使用年數(shù)0～11～22～3 3～44～5年維護費用5 6 8 11 18

試用網(wǎng)絡(luò)分析中求最短路的方法確定公司可采用的最優(yōu)策略。2024/7/5解：設(shè)Vi—i年初購進(jìn)一臺新設(shè)備aij—i年初購進(jìn)之新設(shè)備使用到第j年初ωij—i年初購進(jìn)之新設(shè)備使用到第j年初之總費用

方法：以年號作頂點繪圖，連線表示連續(xù)使用期間，以費用作路長。2024/7/52024/7/52024/7/5費用矩陣2024/7/5方法：以年號作頂點繪圖，連線表示連續(xù)使用期間，以

費用作路長。2024/7/52024/7/5可知最短費用流（相當(dāng)于最短路）

P：V1V3V6

或者是V1V4V6

|

P|=53萬元

結(jié)論：公司五年期設(shè)備更新方案有兩個：A與B，總費用均為53萬元。

A方案：第1年初購置設(shè)備使用到第3年初,第3年初再購置新設(shè)備使用到第5年末（第6年初）

B方案：第1年初購置設(shè)備使用到第4年初，第4年初再購置新設(shè)備使用到第5年末（第6年初）

2024/7/5三.最大流問題1.問題已知網(wǎng)絡(luò)D=（V，A，C），其中V為頂點集，A為弧集，C={cij}為容量集，cij為?。╲i，vj）上的容量。現(xiàn)D上要通過一個流f={fij}，其中fij為?。╲i，vj）上的流量。問應(yīng)如何安排流量fij可使D上通過的總流量v最大？例如：v4v2vsv1vtv32131453252024/7/5可采用線性規(guī)劃的單純型法求解（容量約束）（平衡條件）問題：最大流問題的決策變量、目標(biāo)函數(shù)、約束條件各是什么？2.數(shù)學(xué)模型2024/7/53.基本概念與定理如：在前面例舉的網(wǎng)絡(luò)流問題中，若已給定一個可行流（如括號中后一個數(shù)字所示），請指出相應(yīng)的弧的類型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2024/7/5（2）可增值鏈（增廣鏈）v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2024/7/5（3）截集與截量截量：截集上的容量和，記為。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）例4對于下圖，若V1={vs，v1}，請指出相應(yīng)的截集與截量。2024/7/5例4對于下圖，若V1={vs，v1}，請指出相應(yīng)的截集與截量。解：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2024/7/5（4）流量與截量的關(guān)系截集上的流量和相應(yīng)于截集的反向弧上流量和最大流最小割定理：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2024/7/54.解法（5）最大流的判別條件2024/7/5步驟：2024/7/52024/7/51．算法思想給定N＝{V，A，C}，任取一可行流f＝{fij}，若無可行流，可取零流。l＝1在f中任取一可增路pl利用標(biāo)號規(guī)則與調(diào)整規(guī)則對沿著路p的各弧作最大可能調(diào)整是否對N中所有路均作調(diào)整打印經(jīng)調(diào)整后的最大流f*及最大流量v（f*）取N的一條新可增路pll＝l＋1END雙標(biāo)號算法2024/7/5尋找一可增路pl，l＝1vs標(biāo)號（s，∞），沿pl尋找vs的下一相鄰節(jié)點vj按標(biāo)號規(guī)則對vj進(jìn)行雙標(biāo)號（vj，l（vj））

vs＝vt沿pl從收點vt開始反向搜索途經(jīng)各弧，按調(diào)整規(guī)則作流量調(diào)整抹去pl上各點之雙標(biāo)號，從而由原可行流f調(diào)整為新可行流f1，并有v（f）＜v（f1）是否還有新的可增路打印并輸出經(jīng)調(diào)整后的最大流f*＝{fij∣aij∈A}，最大流量v（f*）結(jié)束l＝l＋1取N的新的可增路plj＝k，i＝j(luò)沿pl尋找vj的相鄰的一點vkNYYN2、調(diào)整步驟2024/7/5例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。解：第一次標(biāo)號及所得可增值鏈如圖，調(diào)量=1，調(diào)后進(jìn)行第二次標(biāo)號如圖。第二次標(biāo)號未進(jìn)行到底，得最大流如圖，最大流量v=5，同時得最小截v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）??????20202024/7/5最大流問題的應(yīng)用例子汽車由A城通往B城的可能的路線如下圖所示。環(huán)境保護部門擬建立足夠數(shù)量的汽車尾氣檢查站，以便使每輛汽車至少必須經(jīng)過一個檢查站。建立檢查站的費用根據(jù)各路段的條件而有所不同(如圖上數(shù)字所示)。若求這個問題的最小費用解，可使用

模型。

a.最短路模型；b.最大流模型；c.最小支撐樹模型AacbdefgB8244526433673782024/7/5延伸問題最小費用流中國郵遞員問題、歐拉回路（邊）旅行商問題、漢密爾頓圈（點）可平面化問題指派問題統(tǒng)籌網(wǎng)絡(luò)計劃匹配問題2024/7/5數(shù)學(xué)建模競賽涉及題目1994修路路線設(shè)計問題

1998災(zāi)情巡查路線設(shè)計

2005DVD在線租賃問題

2007乘公交看奧運問題

2011圍追堵截崗?fù)ぴO(shè)置問題2024/7/51994全國大學(xué)生數(shù)學(xué)建模競賽

要在一山區(qū)修建公路,首先測得一些地點的高程,數(shù)據(jù)見表1(平面區(qū)域0≤x≤5600,0≤y≤4800,表中數(shù)據(jù)為坐標(biāo)點的高程,單位:米).數(shù)據(jù)顯示:

在y=3200處有一東西走向的山峰;從坐標(biāo)(2400,2400)到(4800,0)有一西北---東南走向的山谷;在(2000,2800)附近有一山口湖,其最高水位略高于1350米,雨季在山谷中形成一溪流.經(jīng)調(diào)查知,雨量最大時溪流水面寬度w與(溪流最深處)的x坐標(biāo)的關(guān)系可近似表示為w(x)=((x-24003/4)/2)+5(2400≤x≤4000).公路從山腳(0,800)處開始,經(jīng)居民點(4000,2000)至礦區(qū)(2000,4000).已知路段工程成本及對路段坡度α(上升高程與水平距離之比)的限制如表2.

2024/7/5題目要求試給出一種線路設(shè)計方案,包括原理、方法及比較精確的線路位置(含橋梁、隧道),并估算該方案的總成本.

如果居民點改為3600≤x≤4000,2000≤y≤2400的居民區(qū),公路只須經(jīng)過居民區(qū)即可,那么你的方案需要有什么改變？2024/7/5表1

2024/7/5表2

工程種類┃一般路段┃橋梁┃隧道_________┃_______工程成本(元/米)┃300┃2000┃1500(長度≤300米);3000(長度>300米)對坡度α的限制┃α<0.125┃α=0┃α<0.1002024/7/5模型計算方法(1)

對地圖網(wǎng)格加密，形成圖。(2)

計算網(wǎng)格的距離，用費用作為權(quán)值。(3)求賦權(quán)圖兩點間的最短距離。

2024/7/5參考答案2024/7/51998年全國大學(xué)生數(shù)學(xué)建模競賽

災(zāi)情巡視路線，下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。2024/7/5若分三組（路）巡視，試設(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的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認(rèn)為最佳的巡視路線。2024/7/5鄉(xiāng)村分布圖2024/7/5點的行遍性問題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)哈密爾頓圈2024/7/5線性規(guī)劃模型2024/7/5問題解答：1、分三組（路）巡視，試設(shè)計總路程最短且各組盡可能均衡的巡視路線。

目標(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)分幾組；給出這種分組下最佳的巡視路線。2024/7/5

目標(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)為最佳的巡視路線。

單獨巡視的最短時間=最遠(yuǎn)距離（1）每組時間不超過最遠(yuǎn)距離時間（2）巡視組足夠少，22組4、

若巡視組數(shù)已定(如三組)，要求盡快完成巡視，討論T，t和