圖論基本概念

2012數學建模培訓第6講圖論模型及Matlab程序“圖論模型及其Matlab程序”學習內容1.如何理解圖、無向圖、有向圖？2.如何理解頂點與頂點及邊的關系？3.如何理解加權圖？4.如何確定圖的鄰接矩陣和關聯矩陣？5.如何確定網絡的鄰接矩陣？6.如何應用程序實現鄰接矩陣和關聯矩陣的轉化？7.什么是最短路徑問題，通常有幾類？8.Dijkstra算法和Floyd算法各適用于哪一類最短路問題？9.如何應用程序實現Dijkstra算法和Floyd算法，怎樣理解、改進輸出結果？10.如何理解樹、生成樹、最小生成樹？11.如何應用程序求解最小生成樹？12.什么叫環(huán)游、最優(yōu)環(huán)游、Euler環(huán)游、Hamilton環(huán)游、Euler圖、Hamilton圖？13.如何理解中國郵遞員問題和旅行商問題間的區(qū)別？14.如何利用程序判定Euler圖以及Hamilton圖？15.如何理解網絡流、網絡最大流、最小費用最大流？16.如何應用Ford-Fulkerson算法、Dinic算法及Busacker-Gowan算法求解最大流、最小費用最大流？圖論模型及其Matlab程序圖論是數學的一個分支，以圖為研究對象。圖論中的圖是由若干個給定頂點及若干條連接兩個頂點的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用頂點代表事物，用連接兩個頂點的邊表示相應兩個事物間具有這種關系。這種圖提供了一個很自然的數據結構，可以對自然科學和社會科學中許多領域的問題進行恰當的描述或建模，因此圖論研究越來越得到這些領域的專家和學者的重視。

圖論最早的研究起源于瑞士數學家歐拉，他在1736年成功地解決了哥尼斯堡七橋問題，從而開創(chuàng)了圖論的先河。在此后的200多年時間內,圖論的研究從萌芽階段，逐漸發(fā)展成為數學的一個新分支。20世紀70年代以后，由于高性能計算機的出現，使大規(guī)模圖論問題的求解成為可能。目前，圖論理論已廣泛應用于運籌學、計算機科學、電子學、信息論、控制論、網絡理論、經濟管理等領域。

由于圖論有著豐富的算法和廣泛的應用，所以一直以來圖論問題在信息類競賽中占有較大比重。例如，在著名的ACM/ICPC程序設計競賽中,圖的遍歷、最小生成樹、最短路徑、網絡流、匹配問題、圖的連通性、圖著色等都是常見問題。數學建模競賽中的圖論問題不及ICPC中的普遍，難度也不大。

本講主要介紹圖的一些基本概念及存儲方法、最短路問題、最小生成樹問題、可行遍性問題、網絡流問題及其Matlab程序。本講要求學生理解圖論的基本概念；掌握圖的鄰接矩陣表示方法；能較為熟練地根據實際問題正確地建立圖論模型，并利用相應的Matlab程序求解；不要求理解算法，編寫程序。一、圖的基本概念與圖的存儲1.圖的基本概念

圖論的一個特點就是概念特別多。這里只介紹一些基本的概念，其它概念在后面用到時再補充介紹。1.1圖圖是由頂點集合和邊的集合組成的數據結構，通常用G(V,E)來表示，其頂點集合和邊的集合分別用V(G)和E(G)表示。例如，右圖所示的圖可表示為G(V,E)。其中，V(G)={0,1,2,3,4,5}，E(G)={(0,1),(0,2),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4)}。1.2無向圖與有向圖所有邊都沒有方向的圖稱為無向圖，如1.1中的圖；每條邊都有方向的圖稱為有向圖，通常用<u,v>表示從u到v的有向邊。例如，對于右圖所示的有向圖G(V,E)，V(G)={0,1,2,3,4,5,6},E(G)={<0,1>,<1,2>,<1,4>,<1,5>,<2,4>,<3,2>,<4,1>,<4,3>,<5,6>}。1.3完全圖任何一對頂點都有一條邊的圖稱為完全圖；任何一對頂點u,v都有<u,v>和<v,u>兩條有向邊的圖稱為完全有向圖。例如，左圖為完全圖，右圖為完全有向圖。1.4頂點與頂點、頂點與邊的關系在圖論中，頂點與頂點、頂點與邊的關系是通過“鄰接(Adjacency)”這個概念來表示的。在無向圖G(V,E)中，若(u,v)是圖中的一條邊，則稱u和v互為鄰接頂點，邊(u,v)依附于u,v，或稱(u,v)與u,v相關聯。在有向圖G(V,E)中,若<u,v>是圖中的一條邊，則稱u鄰接到v，v鄰接自u，(u,v)與u,v相關聯。1.5路徑路徑是圖論中一個很重要的概念。在圖G(V,E)中,若從vi出發(fā)，沿著一些邊經過頂點vp1,vp2,…,vpm，到達頂點vj，則稱頂點序列(vi,vp1,vp2,…,vpm,vj)為從頂點vi

到vj的一條路徑或通路。路徑中邊的數量稱為路徑的長度。

若路徑中各頂點vi,vp1,vp2,…,vpm,vj均互相不重復，則稱之為簡單路徑。

若路徑中第一個頂點vi與最后一個頂點vj重合，則稱此路徑為回路。除第一個和最后一個頂點外，沒有頂點重復的路徑稱為簡單回路。例如，

在G1中，(0,1,4,3)為0到3的一條路徑，且為簡單路徑,長度為3；在G2中,(2,4,1,5)為2到5的一條路徑,長度也為3,而(4,3,2,4)為一簡單回路。1.6權值與網絡某些圖的邊具有與之相關的數，稱為權值。這些權值可以表示從一個頂點到另一個頂點的距離、時間、代價等。

若一個圖的所有邊都具有權值，則稱之為加權圖或網絡。根據圖中的邊是否有向，網絡又可以分為有向網和無向網。網絡也可以用G(V,E)表示，其中邊集E中的每個元素有3個分量：邊的兩個頂點和權值。例如，下面兩圖分別為無向網和有向網：

V(G1)={1,2,3,4,5,6}，

V(G2)={1,2,3,4,5,6,7}；

E(G1)={(1,2,28),(1,6,10),(2,3,16),(2,7,14),(3,4,12),(4,5,22),(4,7,18),(5,6,25),(5,7,24)}，

E(G2)={<1,2,12>,<2,4,85>,<3,2,43>,<4,3,65>,<5,1,58>,<5,2,90>,<5,6,19>,<5,7,70>,<6,4,24>,<7,6,50>}。2.圖的存儲方法圖的存儲方法有多種，最常用的存儲方法是鄰接矩陣和關聯矩陣。2.1鄰接矩陣設無向或有向圖G(V,E)，V={v1,v2,…,vn}，E={e1,e2,…,em}。用aij表示vi,vj間的邊數，即則稱A=(aij)n為圖G的鄰接矩陣。顯然，無向圖的鄰接矩陣為對稱陣。例如，注意：如果圖中存在環(huán)（連接某個頂點自身的邊）和重邊（多條邊的起點一樣，終點也一樣）的情形，則無法用鄰接矩陣存儲。2.2關聯矩陣設無向圖G(V,E)，V={v1,v2,…,vn}，E={e1,e2,…,em}。用mij表示頂點vi與邊ej關聯的次數，則稱A=(mij)nm為圖G的關聯矩陣。例如，對有向圖G(V,E)，類似地定義2.3網絡的鄰接矩陣對于網絡G(V,E)，鄰接矩陣A=(aij)n的定義為其中w(i,j)為連接頂點vi和vj的邊的權值。例如，2.4鄰接矩陣與關聯矩陣的轉化鄰接矩陣通過頂點與頂點的關系存儲圖，而關聯矩陣則借助頂點與邊的關系存儲圖。相比較而言，鄰接矩陣更加常用。鄰接矩陣與關聯矩陣可以相互轉化，具體程序見incToadj.m(無向圖)和diincTo

adj.m(有向圖)。

例1

已知圖G的鄰接矩陣為求圖G的關聯矩陣。結果為

例2

已知圖G的關聯矩陣為求圖G的鄰接矩陣。結果為3.作業(yè)與上機練習3.1理解圖的基本概念及存儲方法；3.2寫出下列兩圖的鄰接矩陣和關聯矩陣：3.3用程序incToadj.m

和diincToadj.m實現上題中鄰接矩陣和關聯矩陣的相互轉化。3.4寫出下列網絡的鄰接矩陣：二、最短路問題

最短路問題是計算機、運籌學、地理信息科學等領域的研究熱點之一。在數學建模中，時常出現各類最短路問題。最短路問題是指：若從圖中的某一頂點(源點)到達另一頂點(終點)的路徑不止一條，如何尋找一條路徑，使得沿此路徑各邊上的權值總和(源點到終點的距離)最小，這條路徑稱為最短路徑。

許多優(yōu)化問題都等價于在一個圖中尋找最短路。例如，管道的鋪設、線路的安排、廠址的選取和布局、設備的更新等。最短路問題一般歸為兩類：一類是求從某個頂點到其他頂點的最短路徑，可用Dijkstra算法求解;另一類是求圖中每一對頂點間的最短路徑，可用Floyd算法求解。

Dijkstra

算法和Floyd算法既適用于無向圖，也適用于有向圖。1.Dijkstra算法及Matlab程序1.1Dijkstra算法的基本思想設源點為u0，終點為uk。Dijkstra算法的基本思想是:按距離u0由近及遠為順序，依次求得u0到G的各頂點的最短路和距離，直至uk

或G的所有頂點。1.2Dijkstra算法的實現方法為避免重復并保留每一步的計算信息,Dijkstra算法采用標號算法。

(1)設置兩個頂點集合T和S；

①S中存放已找到最短路徑的頂點，初始時，S中只有u0；

②T中存放當前尚未找到最短路徑的頂點；

(2)在T中選取當前長度最短的一條最短路徑(u0,…,uk)，從而將uk加入S，并修改u0到T中各頂點的最短路徑長度。重復這一步驟，直到所有頂點都加入到S中。

當頂點數較大時,經典Dijkstra算法的運行效率較低。為此，研究人員陸續(xù)提出了兩個改進算法：DijkstraI和DijkstraII。1.3Dijkstra算法程序及實例

Dijkstra算法及其兩個改進算法的程序分別見Dijkf.m，dij1.m和dij2.m。在Dijkf

中，輸入為問題的鄰接矩陣，輸出為3個向量：d,index1,index2。其中di為由源點到第i個頂點的最短距離；index1為頂點標號順序,index2為標號頂點索引，即第i個元素為源點到第i點的最短路徑中第i點前一頂點的序號。在dijk1和dijk2中，輸入為問題的鄰接矩陣，輸出為最短路的距離矩陣。

例3

某公司在6個城市c1,…,c6中有分公司,從ci到cj的直接航班票價見下矩陣(∞表示無直接航班)。請設計從c1到其他城市間票價最低的路線圖。

輸出結果為

d=[0,35,45,35,25,10]index1=[1,6,5,2,4,3]index2=[1,6,5,6,1,1]

下面以c1到c2為例說明如何使用這一結果。由d易知，c1到c2的最短距離為35。由index2知，c1到c2最短路徑中c2之前的一個頂點是c6，c1到c6最短路徑中c6之前的一個頂點是c1，從而c1到c2的最短路徑是c1->c6->c2。

index2的結果不直觀，使用較繁瑣。你能改進程序，直接輸出最短路徑嗎？

例4

求下列有向網中u0到其它各頂點的最短路徑。

輸出結果為

d=[0,20,5,22,28,12]index1=[1,3,6,2,4,5]index2=[1,3,1,6,2,3]從而，u0到其它各頂點的最短距離分別為20,5,22,28,12；最短路徑分別為u0->u2->u1,u0->u2，u0->u2->u5->u3，u0->u2->u1->u4，u0->u2->u5。2.Floyd算法及Matlab程序2.1Floyd算法的基本思想

Floyd算法利用了動態(tài)規(guī)劃算法的基本思想，即若dik是頂點ui到uk的最短距離，dkj是頂點uk到uj的最短距離，則dij=dik+dkj是頂點ui到uj的最短距離。2.2Floyd算法的基本步驟設dij是頂點ui到uj的最短距離，wij是頂點ui到uj的權。

(1)輸入圖G的權矩陣W；

(2)更新dij。對所有i,j，若dij>dik+dkj，則令dij=dik+dkj；

(3)若dij<0，則存在一條含有頂點ui的負回路，停止；或k=n停止；否則轉(2)。2.3Floyd算法程序及實例

Floyd算法的程序分別見floyd.m

和n2shorf.m。

floyd中的輸入為鄰接矩陣，輸出為最小、最大標號頂點間的最短路徑與最短距離。

n2shorf.m中的輸入為鄰接矩陣和指定的兩個頂點，輸出為兩個頂點的最短路徑與最短距離。你能對程序n2shorf.m進行改進，使其能夠輸出所有頂點間的最短路徑和最短距離嗎？

例5

用floyd.m

和n2shorf.m求下圖中v0到v7的最短路徑和最短距離。

輸出結果為

P=[1258]u=11即v0到v7的最短路徑為v0->v1->v4->v7，最短距離為11。

例6

用floyd.m

和n2shorf.m求下圖中v1到v11的最短路徑和最短距離。

輸出結果為

P=[1259671011]u=16即v1到v11的最短路徑為v1->v2->v5->v9->

v6->v7->v10->v11，最短距離為16。3.作業(yè)與上機練習3.1改進Dijkstra

和Floyd算法的程序，使其能夠直接輸出所有最短路徑與最短距離；3.2用Dijkstra算法求v1到其它頂點的最短路徑和最短距離。3.3用Floyd算法求v1到v8的最短路徑和最短距離(無向邊表示雙向)。三、最小生成樹問題

引例在n個城市間建立通信網絡，至少要架設n-1條線路。如何選擇這n-1條線路，使得總造價最??？這是一個具有實際意義的問題，可以用圖論中的最小生成樹解決。本節(jié)主要介紹關于樹的若干概念、最小生成樹問題以及求解方法。本節(jié)討論的圖均為無向圖。1.樹的基本概念不包含圈的連通圖稱為樹。包含圖G所有頂點的極小連通子圖稱為G的生成樹。極小是指邊的數目極小，即若G有n個頂點，則生成樹有n-1條邊。例如，下列3個圖均為圖的生成樹：對于賦權無向連通圖即無向網，各邊權值總和稱為生成樹的權，權最小的生成樹稱為最小生成樹。2.Kruskal算法和Prim算法求最小生成樹的常用方法有Kruskal算法和Prim算法，程序見Krusf.m和Primf.m。例7

用Kruskal算法求下圖的最小生成樹。

注意:程序Krusf中的d采用的是權值矩陣的另一種表示方法——該矩陣每一列的三個數分別表示此列所對應邊的起點、終點和權值，即矩陣的列數即為邊數。

運行結果為

T=131144245756—最小生成樹的邊集合

c=19—最小生成樹的權和例8

用Prim算法求下圖的最小生成樹。結果為T=13453452最小生成樹的邊集合

c=3124對應邊的權3.作業(yè)與上機練習3.1分別用Kruskal算法和Prim算法求下圖的最小生成樹。3.26個城市間的航線距離如下表所示，據此確定最小生成樹。四、可行遍性問題哥尼斯堡七橋問題是圖論最早研究的問題，中國郵遞員問題和旅行商問題也是圖論中著名的問題。這些問題本質上都是圖論中的最優(yōu)環(huán)游問題。所謂環(huán)游或回路是指從圖中的一個頂點出發(fā)不重復地遍歷完所有的邊或頂點并回到起始頂點，也稱可行遍性問題。最優(yōu)環(huán)游是指賦權圖中具有最小權和的環(huán)游。中國郵遞員問題是最優(yōu)邊環(huán)游問題，而旅行商問題則是最優(yōu)頂點環(huán)游問題。本節(jié)簡要介紹Euler環(huán)游和Hamilton環(huán)游的概念以及求解兩種環(huán)游的Fleury算法和改良圈算法。1.Euler環(huán)游與Fleury算法經過圖G的每條邊至少一次的閉跡稱為圖G的環(huán)游。經過每條邊僅一次的環(huán)游稱為圖G的Euler環(huán)游。包含Euler環(huán)游的圖稱為Euler圖。

所謂Euler圖就是能不重復行遍所有邊再回到出發(fā)點的圖。哥尼斯堡七橋問題和一筆畫問題就是典型的判斷圖是否為Euler圖的問題。

對于賦權圖，有時需要尋找具有最小權的環(huán)游，稱為最優(yōu)環(huán)游。中國郵遞員問題就是最典型的最優(yōu)環(huán)游問題。顯然,若G是Euler圖,則G的任何Euler環(huán)游都是最優(yōu)環(huán)游，因為Euler環(huán)游是一條通過G的每條邊一次的環(huán)游。求解Euler環(huán)游問題可用Fleury算法,具體程序見Fleuf1.m。

例9

用Fleury算法判斷下圖是否為Euler圖，若是，請找出一條Euler環(huán)游。2.Hamilton環(huán)游及其求解方法經過圖G每個頂點僅一次的環(huán)游稱為Hamiltion

環(huán)游。包含Hamiltion

環(huán)游的圖稱為Hamiltion圖。

一名旅行售貨員想去訪問若干村，最后回到他的出發(fā)地。給定各村之間所需的旅行時間，應該怎樣計劃他的路線，使得這位售貨員能對每個村恰好訪問一次且總時間最短？這就是著名的旅行售貨員問題或貨郎擔問題(TSP)。旅行商問題其實就是尋找具有最小權的Hamiltion環(huán)游，稱為最優(yōu)圈。

TSP現已被證明是NP難問題，沒有多項式時間算法。這里給出一種求解TSP問題的近似算法——改良圈算法，具體程序見glf.m。

例10

給定(51,67),(37,84),(41,94),(2,99),(18,54),(4,50),(24,42),(25,38),(13,40),(7,64),(22,60),(25,62),(18,40),(41,26)，試用改良圈算法求通過這14個點的Hamiltion圈。3.作業(yè)與上機練習3.1判定下列兩圖是否為Euler圖，若是，則求其Euler環(huán)游。3.2給定(5,67),(37,8),(4,94),(200,99),(18,5),(4,50),(4,420),(250,381),(-3,40),(7,-64)，試用改良圈算法求通過這10個點的Hamiltion圈。五、網絡流問題網絡流問題是圖論中一類常見問題。運輸問題、指派問題、通信問題等均可轉化為網絡流問題。許多系統(tǒng)中都包含了流量，如公路系統(tǒng)中的車流，控制系統(tǒng)中的信息流，供水系統(tǒng)中的水流，金融系統(tǒng)中的現金流等。網絡流問題包括：網絡最大流、流量有界的最大最小流、最小費用最大流、流量有界的最小費用最大流等。本節(jié)主要介紹網絡流中的一些基本概念、網絡最大流、最小費用最大流及其算法。本節(jié)討論的為賦權有向圖，權不是表示邊的長度，而是表示邊的寬度，稱之為邊的容量。1.基本概念1.1網絡與流

本節(jié)中所說的網絡是指規(guī)定了起點和終點的有向賦權圖。所謂流可以理解為定義在邊上的一個函數。若這個函數滿足：

(1)非負性；

(2)不超過邊的容量；

(3)除起終點外,其他頂點的流入量等于流出量；則稱之為可行流。具有最大流量的可行流稱為網絡最大流，簡稱最大流。1.2割設Vs,Vt分別為網絡G(V,E)的起終點，則頂點集S和T稱為G的割，其中。割(S,T)中的前向弧<u,v>()的容量和稱為割的容量。

下面給出圖G的兩個割，容量分別為21和8。容量最小的割稱為最小割。

定理最大流的