運籌學(xué)11-圖與網(wǎng)絡(luò).ppt

1、第十一章 圖與網(wǎng)絡(luò)規(guī)劃Graph Theory and Network Analysis,11.1 圖與網(wǎng)絡(luò)的基本概念 11.2 最短路問題 11.3 網(wǎng)絡(luò)最大流問題 11.4 最小費用最大流問題,內(nèi)容簡介,是近幾十年來運籌學(xué)領(lǐng)域中發(fā)展迅速、而且十分活躍的一個分支 對實際問題的描述具有直觀性 廣泛應(yīng)用于物理學(xué)、化學(xué)、信息論、控制論、計算機科學(xué)、社會科學(xué)以及現(xiàn)代經(jīng)濟(jì)管理科學(xué)等許多科學(xué)領(lǐng)域 圖與網(wǎng)絡(luò)分析的內(nèi)容十分豐富本章只介紹圖與網(wǎng)絡(luò)的基本概念以及圖論在路徑問題、網(wǎng)絡(luò)流問題等領(lǐng)域中的應(yīng)用重點講明方法的物理概念、基本原理及計算步驟,11.1 圖與網(wǎng)絡(luò)的基本概念,圖的理論研究已有200多年的歷史了早期

2、圖論與“數(shù)學(xué)游戲”有著密切關(guān)系所謂“哥尼斯堡七橋”問題就是其中之一,200多年前的東普魯士有一座哥尼斯堡城，城中有一條河叫普雷格爾河，河中有兩個島嶼共建七座橋平時城中居民大都喜歡來這里散步，并提出這樣一個問題：一個散步者能否經(jīng)過每座橋恰恰一次再回到原出發(fā)點,11.1 圖與網(wǎng)絡(luò)的基本概念,當(dāng)時有許多人都探討了這個問題，但不得其解 著名數(shù)學(xué)家歐拉（Euler）將這個問題簡化為一個如右圖所示圖形圖4個點A、B、C、D表示兩岸和小島兩兩點間連線表示橋,11.1 圖與網(wǎng)絡(luò)的基本概念,于是問題轉(zhuǎn)化為一筆畫問題，即能否從某一點開始一筆畫出這個圖形，不許重復(fù)，最后回到原出發(fā)點 歐拉否定了這種可能性 原因是圖中

3、與每一個點相關(guān)聯(lián)的線都是奇數(shù)條 為此他寫下了被公認(rèn)為世界第一篇有關(guān)圖論方面的論文（1736年）,11.1 圖與網(wǎng)絡(luò)的基本概念,1859年哈密爾頓提出了另一種游戲：在一個實心的12面體（見圖）的20個頂點上標(biāo)以世界上著名的城市名稱，要求游戲者從某一城市出發(fā)，遍歷各城市恰恰一次而返回原地，這就是所謂“繞行世界問題”,11.1 圖與網(wǎng)絡(luò)的基本概念,作圖，此問題變成在從某一點出發(fā)尋找一條路徑，過所有20個點僅僅一次，再回到出發(fā)點 解決這個問題可以按序號1234一一201所形成的一個閉合路徑，并稱此路徑為哈密爾頓圈 具有哈密爾頓圈的圖稱為哈密爾頓圖,11.1 圖與網(wǎng)絡(luò)的基本概念,由此可見，圖論中所研究的

4、圖是由實際問題抽象出來的邏輯關(guān)系圖 這種圖與幾何中的圖形和函數(shù)論中所研究的圖形是不相同的 這種圖的畫法具有一定的隨意性，在保持相對位置和相互關(guān)系不變的前提下，點的位置不一定要按實際要求畫，線的長度也不一定表示實際的長度而且畫成直線或曲線都可以 通俗地說，這種圖是一種關(guān)系示意圖,11.1 圖與網(wǎng)絡(luò)的基本概念,圖的概念 所謂圖，就是頂點和邊的集合，點的集合記為V，邊的集合記為E，則圖可以表示為：G（V，E），點代表被研究的事物，邊代表事物之間的聯(lián)系，因此，邊不能離開點而獨立存在，每條邊都有兩個端點。 在畫圖時，頂點的位置、邊和長短形狀都是無關(guān)緊要的，只要兩個圖的頂點及邊是對應(yīng)相同的，則兩個圖相同。

5、,圖的表示,點與邊,頂點數(shù) 集合V中元素的個數(shù)，記作p(G)。 邊數(shù) 集合E中元素的個數(shù)，記作q(G)。 若e=u,vE，則稱u和v為e的端點，而稱e為u和v的關(guān)聯(lián)邊，也稱u，v與邊e相關(guān)聯(lián)。 例如圖中的圖G，p(G)=6，q(G)=9， v1，v2是e1和e2的端點，e1和e2都是v1和v2的關(guān)聯(lián)邊。,點邊關(guān)系,若點u和v與同一條邊相關(guān)聯(lián)，則u和v為相鄰點；若兩條邊ei和ej有同一個端點，則稱ei與ej為相鄰邊。 例如在圖中v1和v2為相鄰點， v1和v5不相鄰；e1與e5為相鄰邊，e1和e7不相鄰。,簡單圖,若一條邊的兩個端點是同一個頂點，則稱該邊為環(huán)；又若兩上端點之間有多于一條邊，則稱為

6、多重邊或平行邊。 例如圖的e8為環(huán)，e1，e2為兩重邊，e4，e5也是兩重邊。 含有多重邊的圖稱作多重圖。 無環(huán)也無多重邊的圖稱作簡單圖。,圖的次,次 點v作為邊的端點的次數(shù)，記作d(v)，如圖中，d(v1)=5, d(v4)=6等 端點次為奇數(shù)的點稱作奇點；次為偶數(shù)的點稱作偶點。 次為1的點稱為懸掛點，與懸掛點連接的邊稱作懸掛邊； 次為0的點稱為孤立點。 圖中的點v5即為懸掛點，邊e9即為懸掛邊，而點v6則是弧立點。,定理,若圖G中所有點都是孤立點，則稱圖G為空圖。 定理1 所有頂點的次的和，等于所有邊數(shù)的2倍。即,定理2 在任一圖中，奇點的個數(shù)必為偶數(shù)。 設(shè)V1和V2分別是圖G中次數(shù)為奇數(shù)

7、和偶數(shù)的頂點集合。由定理1有,鏈,由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列稱為鏈。 v0稱為鏈的起點， vn稱為鏈的終點。 若v0 vn則稱該鏈為開鏈，反之稱為閉鏈或回路。,簡單鏈,若鏈中所含的邊均不相同，則稱為簡單鏈；若點均不相同，則稱為初等鏈或通路。 除起點和終點外點均不相同的閉鏈，稱為初等回路或稱為圈。 例如圖中,是一條鏈，且是開鏈，也是簡單鏈，但不是初等鏈，因為v1出現(xiàn)兩次。,圈,若鏈中所含的邊均不相同，則稱為簡單鏈；若點均不相同，則稱為初等鏈或通路。除起點和終點外點均不相同的閉鏈，稱為初等回路或稱為圈。 例如圖中,是一個圈。,連通性,若一個圖G的任意兩點之間均至少有一條通路（初等鏈

8、）連接起來，則稱這個圖G是一個連通圖，否則稱作不連通圖。 例如圖中，v1和v6之間沒有通路，因此它不是連通圖，而如果去掉v6，則構(gòu)成一個連通圖。,連通的意義,連通是一個很重要的概念，如果一個問題所對應(yīng)的圖是一個不連通圖，則該問題一定可以分解成互不相關(guān)的子問題來加以研究，即可以把不連通圖分解成連通的子圖來研究。,子圖,子圖的定義 設(shè)， G1=(V1,E1), G2=(V2,E2)，如果V1V2 ，又E1E2 ，則稱G1是G2的子圖。,必須指出，并不是從圖G2中任選一些頂點和邊在一起就組成G2的子圖G1，而只有在G2中的一條邊以及連接該邊的兩個端點均選入G1時，G1才是G2的子圖。,特殊子圖,當(dāng)G

9、1中不包含G2中所有的頂點和邊，則稱G1是G2的真子圖。 部分圖 若V1=V2，E1E2 ，則稱G1為G2的一個部分圖。 若V1V2 ， E1= u,v | uV1, vV1，則稱G1是G2中 由V1導(dǎo)出的導(dǎo)出子圖。,有向圖,在有些圖中，邊是沒有方向的，即u,v=v,u，這種圖稱為無向圖。 而有些關(guān)系是不對稱的，例如父子關(guān)系、上下級關(guān)系、加工工序的先后順序等都具有單向性，用圖來表示這些關(guān)系時，得到的邊是具有方向的，用帶箭頭的線來表示，稱為弧。 從頂點u指向的弧a，記作a=(u,v),(u,v)(v,u)，其中u稱為a的起點，v稱為a的終點，這樣的圖稱為有向圖。仍以V表示點的集合，以A表示弧的集

10、合，則有向圖表示為D（V，A）,有向圖例,有向圖的鏈路,有向圖中，在不考慮邊的方向時，也可以相同地定義鏈，若有向圖D（V，A）中，P是一個從u到v的鏈，且對P中每一條弧而言，在序列中位于該弧前面的點恰好是其起點，而位于該弧后面的點恰好是其終點，這個鏈P就稱為是D中從u到v的一條路。 當(dāng)路的起點與終點相同，即u=v時，稱作一條回路。 頂點全不相同的路稱為初等路。 除起點和終點外點均不相同的回路稱為初等回路。,樹及最小樹問題,任何樹至少有一個懸掛節(jié)點,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果樹的節(jié)點個數(shù)為m，則邊的個數(shù)為m-1,樹中任意兩個節(jié)點之間只有唯一的一條鏈,在樹的任

11、意兩個不相鄰的節(jié)點之間增加一條邊，則形成唯一的圈,樹及最小樹問題,一個沒有圈的圖稱為一個無圈圖或稱為林。 一個連通的無圈圖則稱為樹，一個林的每個連通子圖都是一個樹。 定理 以下關(guān)于樹的六種不同描述是等價的： 無圈連通圖。 無圈，q=p-1。 連通，q=p-1。 無圈，但若任意增加一條邊，則可得到一個且僅一個圈。 連通，但若任意舍棄一條邊，圖便不連通。 每一對頂點之間有一條且僅有一條鏈。,網(wǎng)絡(luò)概念,圖只能用來研究事物之間有沒有某種關(guān)系，而不能研究這種關(guān)系的強弱程度。 網(wǎng)絡(luò) 賦權(quán)的圖 權(quán) 程度的度量，數(shù)量描述。,網(wǎng)絡(luò)概念,節(jié)點與（有向）邊 每一條邊和兩個節(jié)點關(guān)聯(lián)，一條邊可以用兩個節(jié)點的標(biāo)號表示（i

12、，j）,路徑（Path） 前后相繼并且方向相同的邊序列 P=(1,2),(2,3),(3,4),4,2,3,1,4,2,3,1,網(wǎng)絡(luò)由節(jié)點和邊組成,網(wǎng)絡(luò)概念,回路（Circuit） 起點和終點重合的路徑稱為回路 =(1,2),(2,4),(4,1) 回路中各條邊方向相同,4,2,3,1,鏈（Chain） 前后相繼并且方向不一定相同的邊序列稱為鏈 C=(1,2),(3,2),(3,4),4,2,3,1,網(wǎng)絡(luò)概念,連通圖 任意兩個節(jié)點之間至少有一條鏈的圖稱為連通圖,2,4,3,5,1,圈(Cycle) 起點和終點重合的鏈稱為圈 =(1,2),(2,4),(3,4),(1,3) 圈中各條邊方向不一定

13、相同,4,2,3,1,樹(Tree) 無圈的連通圖稱為樹 樹中只與一條邊關(guān)聯(lián)的節(jié)點稱為懸掛節(jié)點,網(wǎng)絡(luò)概念,平面圖(planar graph)，若在平面上可以畫出該圖而沒有任何邊相交 走過圖中所有邊且每條邊僅走一次的閉行走稱為歐拉回路 定理 ：偶圖一定存在歐拉回路(一筆畫定理) 圖中都是偶點的圖稱為偶圖(even graph),哈密爾頓回路( Hamiltonian circuit)問題,連通圖G(V,E)中的回路稱為哈密爾頓回路，若該回路包括圖中所有的點。顯然哈密爾頓回路有且只有 n 條邊，若|V|=n 連通圖具有哈密爾頓回路的充分必要條件是什么？這個問題是由愛爾蘭數(shù)學(xué)家哈密爾頓1859年提出

14、的，但至今仍未解決 歐拉回路是對邊進(jìn)行訪問的問題，哈密爾頓回路是對點進(jìn)行訪問的問題 搜索哈密爾頓回路的難度是 NP-complete 任兩點間都有邊的圖稱為完全圖(或全連接圖) 完全圖中有多少個不同的哈密爾頓回路？ (n1)!/2 完全圖中有多少個邊不相交的哈密爾頓回路？ (n1)/2 最小哈密爾頓回路問題 (NP-complete) 哈密爾頓路徑：包含圖中所有點的路徑 為什么說找兩點間的最長路是非常困難的問題？,中國郵遞員問題,中國郵遞員問題(Chinese Postman Problem, CPP)是由我國管梅谷教授于1962年首先提出并發(fā)表的 問題是從郵局出發(fā)，走遍郵區(qū)的所有街道至少一次

15、再回到郵局，走什么路由才能使總的路程最短？ 如果街區(qū)圖是一個偶圖，根據(jù)定理 3，一定有歐拉回路，CPP問題也就迎刃而解了 若街區(qū)圖不是偶圖，則必然有一些街道要被重復(fù)走過才能回到原出發(fā)點 顯然要在奇次點間加重復(fù)邊 如何使所加的邊長度最少 歸結(jié)為求奇次點間的最小 匹配( minimum weighted match) 由Edmons 給出多項式算法(1965),旅行推銷員問題(Traveling Salesman Problem),TSP：設(shè)v1, v2, .,vn 為 n 個已知城市，城市之間的旅程也是已知的，要求推銷員從 v1出發(fā)，走遍所有城市一次且僅一次又回到出發(fā)點，并使總旅程最短 這種不允

16、許點重復(fù)的旅行推銷員問題就是最小哈密爾頓回路問題 一般旅行推銷員問題(GTSP)：允許點重復(fù)的TSP 典型的應(yīng)用： 鄉(xiāng)郵員的投遞路線 郵遞員開郵箱取信的路線問題 郵車到各支局的轉(zhuǎn)趟問題 運鈔 送奶、送水 .,網(wǎng)絡(luò)最短樹問題,最短樹問題的一般提法是：選取網(wǎng)絡(luò)中的部分圖，使得網(wǎng)絡(luò)連通，且使總權(quán)數(shù)最短。 在實際應(yīng)用中，經(jīng)常碰到需要求一個賦權(quán)連通圖的最短樹的問題。例如，用節(jié)點表示城市，用邊表示可以在兩個城市之間架設(shè)光纜，邊上的權(quán)表示光纜的長度，試求應(yīng)如何架設(shè)光纜，才能使任意兩城市之間均由光纜相通，且使光纜的總長度最短。 求最短樹的方法，依據(jù)的是樹的特點，即無圈和連通，加上最短的要求，方法主要有兩種：一

17、種稱為破圈法，一種稱為避圈法,11.2 最短路問題,最短路問題的一般提法是：欲尋找網(wǎng)絡(luò)中從起點1到終點n的最短路線，即尋求連接這兩點的邊的總長度為最小的通路，最短路線中的網(wǎng)絡(luò)大都是有向網(wǎng)絡(luò)，也可以是無向網(wǎng)絡(luò)。 最短路問題是網(wǎng)絡(luò)分析中的一個基本問題，它不僅可以直接應(yīng)用于解決生產(chǎn)實際的許多問題，如管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個基本工具，用于解決其它的優(yōu)化問題。,最短路問題的Dijkstra算法(雙標(biāo)號法）,步驟： 1.給出點V1以標(biāo)號(0,s) 2.找出已標(biāo)號的點的集合I，沒標(biāo)號的點的集合J以及弧的集合 3.如果上述弧的集合是空集，則計算結(jié)束。如果vt已標(biāo)號（lt,kt），則

18、vs到vt的距離為lt，而從 vs到vt的最短路徑，則可以從kt反向追蹤到起點vs 而得到。如果vt 未標(biāo)號，則可以斷言不存在從 vs到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。 4. 對上述弧的集合中的每一條弧，計算 sij=li+cij 。在所有的 sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點以雙標(biāo)號（scd,c）,返回步驟2。,例1 求下圖中v1到v6的最短路 解：采用Dijkstra算法，可解得最短路徑為v1 v3 v4 v6 各點的標(biāo)號圖如下：,例2 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的

19、交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。 解：這是一個求無向圖的最短路的問題。可以把無向圖的每一邊（vi,vj）都用方向相反的兩條弧（vi,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標(biāo)號的點到未標(biāo)號的點的弧的集合改成已標(biāo)號的點到未標(biāo)號的點的邊的集合即可。,例2最終解得： 最短路徑v1 v3 v5 v6 v7，每點的標(biāo)號見下圖,（0,s） V1 （甲地）,15,17,6,2,4,4,3,10,6,5,(13,3) v2,(22,6) V7 （乙地）,V5 (14,3),V6 (16,5),

20、V3 (10,1),V4 (18,5),例3 設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費，當(dāng)然新設(shè)備的維修費用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費，但維修費用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。 已知：設(shè)備每年年初的價格表 設(shè)備維修費如下表,例3的解：將問題轉(zhuǎn)化為最短路問題，如下圖： 用vi表示“第i年年初購進(jìn)一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進(jìn)的 設(shè)備一直使用到第j年年初。 把所有弧的權(quán)數(shù)計算如下表：,(繼上頁) 把權(quán)數(shù)賦到圖中，再用Di

21、jkstra算法求最短路。 最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條： v1 -v3-v6和 v1-v4-v6,11.4 網(wǎng)絡(luò)最大流問題,所謂最大流問題就是在一定的條件下，要求流過網(wǎng)絡(luò)的物流、能量流或信息流等流量為最大的問題，在最大流問題中一般有如下規(guī)定： 網(wǎng)絡(luò)有一個起點s和一個終點t 網(wǎng)絡(luò)是有向網(wǎng)絡(luò)，即流有方向性。 在網(wǎng)絡(luò)各條弧上都有一個權(quán)，表示允許流過的最大流量。若以bij表示由i到j(luò)的弧上允許流過的最大流量，以xij表示實際流過該弧的流量，則0 xij bij 網(wǎng)絡(luò)中，除起點s和終點t之外的任何頂點，流入量總和應(yīng)該等于流出量的總和。,一、最大流問題的數(shù)學(xué)模型,二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖: (a)和 (b)、(c)和(d)的意義相同。,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,求最大流的基本算法 （1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。 （2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。 （3）在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的逆流容量