1、第第7章章 圖圖 論論 7.1 問題驅動：最佳災情巡視路線 根據最新天氣預報，某縣將要遭遇特大暴雨，為預防洪澇災情發生，提前做好預防工作，縣政府決定抽調各職能部門相關人員組成三個工作組到各鄉鎮、村進行巡視。假設你是縣政府秘書，請設計最佳巡視路線。1.圖論基本知識2.圖論與網絡模型（1）最短路問題（2）最小生成樹（3）遍歷（4）網絡流問題7.2 圖論基本知識7.2.1 起源起源 哥尼斯堡是東普魯士的一座城市，第二次世界大戰后劃歸蘇聯，也就是現在的加里寧格勒。 普萊格爾河流經此城市，河中有兩個孤島，有七座橋將兩島及島與河岸相連，如圖所示。當時那里的居民熱衷于這樣一個問題：從一個點出發，能否通過每座

2、橋一次且僅一次，最后回到原來的出發點？7.2.2 圖論中的一些基本概念圖論中的一些基本概念 1.有序三元組 稱為一個圖圖。其中（1） 是有窮非空集，稱為頂點集，其中的元素叫圖g的頂點頂點。 （2） 稱為邊集，其中的元素叫圖g的邊邊。（3） 是從邊集到頂點集中的有序或無序的元素偶對的集合的映射，稱為關聯函數關聯函數。,evg,21nvvvv,21neeee2.邊有方向的圖，稱為有向圖有向圖，邊無方向的圖稱為無向圖無向圖。連接兩個頂點至多有一條邊，且一條邊的兩個頂點不重合的圖稱為簡單圖簡單圖。（a）（b）（c）（d）3.圖 、 ，若 、 ，則稱圖 是 的子圖。如圖中的（b）即為圖（a）的子圖。),

3、(evg ),(111evg 1vv 1ee 1gg（a）（b）通路44112544141vevevevevwvv道路4332264521141vevevevevevtvv路徑4521141vevevpvv6.任意兩個頂點之間都有邊相連的簡單圖，稱為完備圖完備圖。7.如果圖 的子圖 是一棵樹，且 ，則稱 是 的生成樹生成樹。8.設對圖 的每一條邊 賦予一個實數 ，稱為邊的權，則稱 為賦權圖賦權圖(或加權圖或加權圖)。連通的賦權圖的權和最小的生成樹稱為的最小生成樹最小生成樹9.有向圖 中，每邊加權 ，則稱這個賦權的有向圖為一個網絡網絡，記作 , 其中c為容量函數，c(e)稱為邊e的容量，容量，x

4、與y為網絡的發點集與收點集，x的頂點稱作發點或源，y的頂點稱作收點或匯，其余為中間點集。10.網絡 中，若函數 滿足(1) 任給 ，(2) 任給 ， ，其中 是 以為終點的邊集， 是以 為起點的邊集，稱 為網絡的一個流流， 為邊的流量流量。),(evg tttevg,vvttgg),(evg e ew),(evg ecyxcevn,yxcevn,ref:ee ecef0匯源, vv0)()()()(vnevneefef vnv vnvf ef（2，1）（5，4）（3，0）（2，2）（1，1）（4，4）（1，0）（5，2）（4，3）7.2.3 圖的矩陣表示圖的矩陣表示 圖的矩陣表示常用的有兩種形

5、式：鄰接矩陣和關聯矩陣。鄰接矩陣常用于研究圖的各種道路的問題，關聯矩陣常用于研究子圖的問題。由于矩陣的行列有固定的順序，因此在用矩陣表示圖之前，須將圖的結點和邊加以編號（定序），以確定與矩陣元素的對應關系。 1.鄰接矩陣鄰接矩陣 設 是一簡單有向圖，結點集為 。構造矩陣 其中 則稱a為有向圖g的鄰接矩陣鄰接矩陣。 這個定義也適用于無向圖，只須把其中的有向表示換成無向表示就行了。 對于賦權圖，其鄰接矩陣記作 ，其中：),(evg nvvvv,21nnijaa)(, 0, 1evvevvajijiij當當)(ijaaevvjiwevvwajiijjiijij),(0,),(若若為其權且若2.關聯矩

6、陣關聯矩陣 設 是一個無環的有向圖， 。構造矩陣 ，其中 稱m是g的關聯矩陣。 設 是無環的無向圖， 。構造矩陣 ，其中 ,稱m為g的關聯矩陣。),(evg mneeeevvvv,2121nnijmm，ve，vemijijij其它的入邊是當的出邊是當01, 1),(evg mneeeevvvv,2121mnijmm)(，evmjiij其它關聯與若, 0, 1例例1 圖的鄰接矩陣是4321432105375083802720vvvvvvvv例例2 圖的關聯矩陣如下43215432110110011000101110001vvvveeeee7.3 圖論與網絡模型7.3.1最短路問題最短路問題 假設

7、給定連接若干城市的公路網，尋求從指定城市到各城去的最短路線。 設指定城市為圖的一個頂點 ，其余任一城市為圖的一個頂點 ，連接任意兩城市的公路為圖的邊 ， 為邊之長，即在加權圖中求 兩點之間的路徑 ，使該路徑上的邊權之和最小，即 解決這一問題可以用迪克斯特拉（dijkstra）算法， 0-1規劃法、動態規劃法求解。本節主要介紹0-1規劃法。 0uve ewvu,),(0vupp )()()(minpeewpw 設1為起點， n為終點。引入 表示：若弧(i,j)在最短路上, ；否則， 。z為目標函數上各弧的路程之和。起點1必定有一條弧出發,所以， 終點n必定有一條弧到達,所以 。 其它點有兩種情況

8、：(1)點i不在最短路上，即無進線弧，也無出線弧。滿足： ，且 (2)點i在最短路上，即有進線弧，也有出線弧。滿足： ，且 改寫上述兩個等式為：01njijx01njjix11njijx11njjix0,11iinjjinjijxxx1 , 01 ,11. .min111111,ijnjjinjijnjjnnjjnjiijijxnixxxxtsxwz1 , 0ijx1ijx0ijx121njjx111njjnx例例3 在圖中，點表示城市，現有7個城市，點與點之間的連線表示城市間有道路相連，連線旁的數字表示道路的長度。某人計劃從城市a到城市 d去，請設計出路程最短的路線。ab1b2c1c2c3d

9、24314313132解：本題要求城市a到城市 d的最短路線設計方案，城市間路長作為邊上的權，問題就轉化為兩點間的最短路問題，編寫lingo程序求解如下： model: sets:city/a, b1, b2, c1, c2, c3, d/; road(city, city)/ a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/: w, x; endsets data: w = 2 4 3 3 1 2 3 1 1 3 4; enddata n=size(city); min=sum(road: w*x); for(city

10、(i) | i #ne# 1 #and# i #ne# n: sum(road(i,j): x(i,j) = sum(road(j,i): x(j,i); sum(road(i,j)|i #eq# 1 : x(i,j)=1; endlingo軟件計算結果如下global optimal solution found at iteration: 0 objective value: 6.000000 variable value reduced cost x( a, b1) 1.000000 0.000000 x( b1, c1) 1.000000 0.000000 x( c1, d) 1.00

11、0000 0.000000即最短路是, 最短路長為6個單位。dcba117.3.2最小生成樹最小生成樹 欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為cij。設計一個線路圖，使修筑鐵路的總造價最低。 設計要求鐵路將n個城市連通，不要求任意兩城直達，但總造價最低。將城市看作點，城市之間欲修的鐵路看作邊，而城市間的鐵路造價作權，則構成一個賦權連通圖，該問題就是在賦權連通圖中求權值最小的連通子圖，即邊權之和最小的生成樹。數學模型 。 解決這類構造最小生成樹問題的算法有kruskal算法、prim算法、破圈法、整數規劃法。本節主要介紹整數規劃法。)()()(minteewtw整數規劃法整數規

12、劃法 假設 表示點i到點j的權，當兩個節點沒有線路相通時， 。設0-1變量,當 ,表示從節點i到節點j的邊在樹中;當 ,表示從節點i到節點j的邊不在樹中。 目標函數: 約束條件：（1）假設根節點為 ，根節點只有出去的線路，且出去的線路不少于1條，但沒有進來的線路,有 ；（2）其它節點（除根節點外）必須有且只有一條線路進來，即 。 僅僅上述條件還不夠，因為一棵樹是連通且不能有圈的。引入變量 ，其中 ，為避免形成圈，約束ijwijw1ijx0ijxnjiijijxwz1,min1v0, 12121njjnjjxxjinjxniij,.,3 ,2, 11ujinjnuuj, 2, 11 , 01nj

13、nkxnxnxuujkkjkjkj2 ,1 ,312綜上，求最小生成樹模型njnkxnxnxuujinjnuujinjxxtsxwzjkkjkjkjjniijnjjnjiijij2 ,1 ,312, 2, 11 , 0,.,3 , 2, 11. .min11211,例例4 某地區共有1個城市（標記為1）和9個鄉鎮（標記為2-10）組成，該地區不久將用上天然氣，其中城市1含有井源。現要設計一供氣系統，使得從城市1到每個鄉鎮（2-10）都有一條管道相通，并且鋪設的管子的量盡可能的少。下表給出了城鎮之間的距離。101111116816814915157108181571017317121271197

14、22141811817159221716121412958-2 3 4 5 6 7 8 9 101 23456789解：本題要求設計一條管道使得城市1到每個鄉鎮（2-10）都相通，但總長最短。將城市、鄉鎮看作點，之間連線看作邊，之間距離作邊權，構成一個賦權連通圖。求使各點相互連通，總長最短的連線，即權和最小的生成樹。 編寫lingo程序求解如下：model: sets: city/1.10/:u; link(city, city): distance, x; endsets data: distance = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11

15、18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddata n=size(city); min=sum(link: distance*x);for(link : bin(x); for(city(k) |k #g

16、t# 1 : sum(city(i)| i #ne# k: x(i,k)=1; for(city(j)| j #gt# 1 #and# j #ne# k: u(j) = u(k) + x(k,j) - (n-2)*(1-x(k,j) + (n-3)*x(j,k); ); sum(city(j)| j #gt# 1: x(1,j)=1; for(city(k) |k #gt# 1 :u(k)=n-1-(n-2)*x(1,k); ); end在上述程序中，利用變量(u)來保證所選的邊不構成圈。計算結果如下：global optimal solution found at iteration: 34

17、objective value: 60.00000 variable value reduced cost x( 1, 2) 1.000000 8.000000 x( 1, 3) 1.000000 5.000000 x( 3, 4) 1.000000 7.000000 x( 3, 7) 1.000000 7.000000 x( 4, 5) 1.000000 3.000000 x( 5, 8) 1.000000 6.000000 x( 7, 9) 1.000000 6.000000 x( 9, 6) 1.000000 8.000000 x( 9, 10) 1.000000 10.00000連接這

18、10個城鎮的最小距離為60公里。7.3.3 遍遍 歷歷 一、中國郵路問題一、中國郵路問題 一位郵遞員從郵局選好郵件去投遞，然后返回郵局，他必須經過所負責投遞的每條街道至少一次，為他設計一條投遞路線，使得他行程最短。這個問題稱為中國郵路問題。定義定義 設g=(v,e)是連通無向圖（1）經過g的每邊正好一次的回路稱為歐拉回路歐拉回路。（2）存在歐拉回路的圖稱為歐拉圖歐拉圖。（3）經過g的每邊正好一次的道路稱為歐拉道路歐拉道路。 左圖中 是一條歐拉道路，但無歐拉回路，所以不是歐拉圖。右圖存在歐拉回路 ，所以是歐拉圖。e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e651 1

19、 2 2 31 4 4 3 3v ev e v e v e v e v1 1 2 2 3 5 1 44 3 3 6 1v ev e v e v e v e v e v定理定理 連通圖g是歐拉圖當且僅當g不含奇次頂點。 將投遞區的街道用邊表示，街道的長度用邊權表示，郵局街道交叉口用點表示，則一個投遞區構成一個賦權連通無向圖中國郵遞員問題轉化為：在一個非負賦權連通圖中，尋求一個權最小的回路這樣的回路稱為最佳回路。對于歐拉圖，可由fleury算法求出圖的一個歐拉回路即是最佳回路。 對于無向加權連通圖，設 為從 i到 j 經過的次數，則得如下數學模型ijxjivvijijxwminevvnxevvxx

20、vvxxjiijjijiijvvivvkiijjiik, 1,二、推銷員問題二、推銷員問題 一名推銷員準備前往若干城市推銷產品，如何為他設計一條旅行路線，使其從駐地出發，經過每個城市至少一次，最后返回出發地的總行程最小？這個問題稱為推銷員問題。 若用頂點表示城鎮，邊表示連接兩城鎮的路，邊上的權表示距離（或時間、費用），于是推銷員問題就轉化為在加權圖中尋找一條經過每個頂點至少一次的最短閉通路問題。 定義 設g=(v,e)是連通無向圖（1）經過g的每個頂點正好一次的圈，稱為g的哈密爾頓圈哈密爾頓圈或h圈。（2）含h圈的圖稱為哈密爾頓圖哈密爾頓圖或h圖。v1v2v5v3v4圖7-20v10v9v6v

21、7v8 定義定義在加權圖g=(v,e)中，（）權最小的哈密爾頓圈稱為最佳最佳h圈圈。（）經過每個頂點至少一次的權最小的閉通路稱為最佳推銷員回路最佳推銷員回路。 一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈。 定理定理在加權圖g=(v,e)中，若對任意x,y,z v，zx,zy,都有w(x,y) w(x,z)+w(z,y) ，則圖g的最佳h圈也是最佳推銷員回路。 最佳推銷員回路問題可轉化為最佳h圈問題方法是由給定的圖g=(v,e)構造一個以v為頂點集的完備圖g=(v,e)，e的每條邊(x,y)的權等于頂點x與y在圖中最短路的權。即：w(x,y)=mi

22、ndg(x,y) 定理定理加權圖g的最佳推銷員回路的權與g的最佳h圈的權相同。 加權圖中求最佳推銷員回路問題就轉化為再完備加權圖中尋求最佳h圈問題，而求h圈至今仍無有效算法。我們常采用近似算法，如二邊逐次修正法，或建立數學模型用軟件求解。設當從 到 時， ，否則， ， ，則得如下模型ivjv1ijx0ijxji jinjniuunnxuunjixjinjxijnixtsxwjiijjiijniijnjijninjijij, 2, 2 , 1, 0, 1, 1, 1 , 0, 1, 1, 1, 1. .min1111、例例5 某公司計劃在某地區作廣告宣傳，各城鎮之間的距離如表,推銷員從城市1出發

23、，經過各個鄉鎮，再回到城市1，為節約開支，公司希望推銷員走過這10 個城鎮的總距離最少。 10111111681681491515710818157101731712127119722141811817159221716121412958-2 3 4 5 6 7 8 9 101 23456789解：本題是最佳推銷員問題，編寫lingo程序如下model: sets: city/1.10/:u; link(city, city): distance, x; endsets data: distance = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18

24、 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddatan=size(city); min=sum(link: distance*x); for(link : bin(x); for(city(k) :sum(ci

25、ty(i)| i#ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1;); for(city(i): for(city(j) | j #gt# 1 #and#i #ne# j : u(i)-u(j)+n*x(i,j)=n-1);); for(city(i):u(i)=n-1);for(link : bin(x); end變量u是用來保證所選的邊除第1點外不構成圈。lingo軟件計算結果如下：global optimal solution found at iteration: 90objective value: 73.00000 variable

26、 value reduced cost x( 1, 2) 1.000000 8.000000 x( 2, 6) 1.000000 8.000000 x( 3, 1) 1.000000 5.000000 x( 4, 3) 1.000000 7.000000 x( 5, 4) 1.000000 3.000000 x( 6, 9) 1.000000 8.000000 x( 7, 10) 1.000000 11.00000 x( 8, 5) 1.000000 6.000000 x( 9, 7) 1.000000 6.000000 x( 10, 8) 1.000000 11.00000旅行商經過10 個

27、城鎮的最短距離為73公里，次序1345810796217.3.4 網絡流問題網絡流問題 現實生活中存在很多網絡，鐵路網、通信網、運輸網等。把商品從生產地運往市場，交通網上每個路段能力給定的條件下，設計一個運輸方案，使得運輸最快。 在單源單匯具有容量上限的網絡中求從源到匯的流量最大的流。求網絡最大流中有ford-fulkerson算法，但是網絡最大流也是一個線性規劃問題。其數學模型如下：其中1發點，表示收點。最小費用最大流問題數學模型 nijifikfcjiftsnfvjvkij, 1, ),(),(),(0. ., 1max的最大流到為網絡頂點nnfnijifikfcjiftsnjnifczv

28、jvkijejiijij1, 1, 1, ),(),(),(0. ., 1,min,例例6 現需要將城市s的石油通過管道運送到城市t，中間有4個中轉站v1v2v3v4 , 城市與中轉站的連接，由于輸油管道的長短不一或地質等原因，使每條管道上運輸費用也不相同，因此，除考慮輸油管道的最大流外，還需要考慮輸油管道輸送最大流的最小費用，如圖示是帶有運費的網絡，其中第1個數字是網絡的容量，第2個數字是網絡的單位運費。stv1v2v3v4(8,2)(7,8)(9,3)(9,2)(2,1)(5,5)(5,6)(10,7)(6,4)解： 本例所提出的問題就是最小費用最大流問題，即考慮網絡在最大流情況下的最小費

29、用，先求網絡最大流，編寫lingo程序如下：model: sets: nodes/s,1,2,3,4,t/; links(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; endsets data: c = 8 7 5 9 9 2 5 6 10; enddatamax = f(s,t);for(links (i,j) :f(i,j)=c(i,j);for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j);endlingo軟件的計算結果如下:global optimal s

30、olution found at iteration: 6 objective value: 14.00000 variable value reduced cost flow 14.00000 0.000000 f( s, 1) 7.000000 0.000000 f( s, 2) 7.000000 0.000000 f( 1, 2) 2.000000 0.000000 f( 1, 3) 5.000000 0.000000 f( 2, 4) 9.000000 -1.000000 f( 3, 2) 0.000000 0.000000 f( 3, t) 5.000000 -1.000000 f(

31、 4, 3) 0.000000 1.000000 f( 4, t) 9.000000 0.000000在網絡最大流的限制下，求輸油管道輸送最大流的最小費用，編寫lingo程序如下：model: sets: nodes/s,1,2,3,4,t/; links(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u, f; endsets data: c= 8 7 5 9 9 2 5 6 10; u= 2 8 5 2 3 1 6 4 7; enddata f(s,t)=14; min=sum(links:u*f); for(links(i

32、,j):f(i,j)=c(i,j);for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j);endlingo軟件的計算結果如下:global optimal solution found at iteration: 3 objective value: 205.0000 variable value reduced cost f( s, 1) 8.000000 -1.000000 f( s, 2) 6.000000 0.000000 f( 1, 2) 1.000000 0.000000 f( 1, 3) 7.000000 0.00000

33、0 f( 2, 4) 9.000000 0.000000 f( 3, 2) 2.000000 -2.000000 f( 3, t) 5.000000 -7.000000 f( 4, t) 9.000000 0.000000因此，最大流的最小費用是205單位。7.4驅動問題建模求解7.4.1 問題分析問題分析 題中給出了某縣的公路網絡圖，要求的是在不同的條件下，災情巡視的最佳分組方案和路線。從若干可能的安排或方案中尋求最優安排或方案，數學上把這種問題稱為最優化或優化問題。 將每個鄉（鎮）或村看作一個圖的頂點，各鄉鎮、村之間的公路看作此圖對應頂點間的邊，各條公路的長度（或行駛時間）看作對應邊上的權

34、，所給公路網就轉化為加權網絡圖，問題就轉化圖論中一類稱之為推銷員問題，即在給定的加權網絡圖中尋找從給定點o出發，行遍所有頂點至少一次再回到點o，使得總權（路程或時間）最小。本題即推銷員問題的延伸多推銷員員問題。7.4.2 假假 設設 1汽車在路上的速度總是一定，不會出現拋錨等現象； 2巡視當中，在每個鄉鎮、村的停留時間一定，不會出現特殊情況而延誤時間； 3每個小組的汽車行駛速度完全一樣； 4分組后，各小組只能走自己區內的路，不能走其他小組的路，除公共路外。 5村鎮被巡視一次后，再次經過時不會停留。 7.4.3模模 型型 的的 建建 立立 與與 求求 解解 將公路網圖中，每個鄉（鎮）或村看作圖中

35、的一個節點，各鄉（鎮）、村之間的公路看作圖中對應節點間的邊，各條公路的長度（或行駛時間）看作對應邊上的權，所給公路網就轉化為加權網絡圖，問題就轉化為在給定的加權網絡圖中尋找從給定點o出發，行遍所有頂點至少一次再回到o點，使得總程最小，此即最佳推銷員回路問題。 在加權圖g中求最佳推銷員回路問題是np完全問題，我們采用一種近似算法求出該問題的一個近似最優解，來代替最優解，算法如下： 1.用圖論軟件求出g中任意兩個頂點間的最短路，構造出完備圖 ， ， ； 2.輸入圖的一個初始h圈； 3.隨機搜索出中若干個h圈； 4.對第2、3步所得的每個h圈，用二邊逐次修正法進行優化，得到近似最佳h圈； 5.在第4

36、步求出的所有h圈中，找出權最小的一個，此即要找的最佳h圈的近似解。 由于二邊逐次修正法的結果與初始圈有關，故本算法第2、3步分別用兩種方法產生初始圈，以保證能得到較優的計算結果。),(evgeyx ,yxmindyxg,具體求解如下： 此問題是多個推銷員的最佳推銷員回路問題，即在加權圖g中求頂點集v的劃分 ，將g分成n個生成子圖 ，使得（1）頂點 i=1，2，3n（2）（3） ，其中 為 的導出子圖中的最佳推銷員回路， 為 的權，i，j=1，2，3n（4）定義 稱為分組的實際均衡度。 為最大容許均衡度。nvvv,.,21 nvgvgvg,.,21ivogvvnii1iijijicmaxccma

37、x,icivicicmincnii1iijijicmaxccmax,0 從o點出發去其它點，要使路程較小應盡量走o點到該點的最短路。故用圖論軟件包求出o點到其余頂點的最短路，這些最短路構成一棵樹，將從o點出發的樹枝稱為干枝，見下圖，從圖中可以看出，從o點出發到其它點共有6條干枝，它們的名稱分別為，。根據實際工作的經驗及上述分析，在分組時應遵從以下準則：一、盡量使同一干枝上及其分枝上的點分在同一組；二、應將相鄰的干枝上的點分在同一組；三、盡量將長的干枝與短的干枝分在同一組。根據上述分組準則，我們找到兩種分組形式如下：分組一：（，），（，），（，）分組二：（，），（，），（，）顯然分組一的方法極不均衡，故考慮