OPERATIONSRESE運籌學OR31第六章圖與網(wǎng)絡分析ABCDE引論:哥尼斯堡七橋問題

ABCDA

BcDOR32鐵路交通圖此圖是我國北京,上海等十個城市間的交通圖,反映了這十個城市間的鐵路分布情況.點表示城市,點間的連線表示兩個城市間的鐵路線.諸如此類問題還有電話線分布圖或煤氣管道分布圖等.北京濟南徐州青島南京上海連云港鄭州武漢天津OR336.1圖的基本概念圖是由點和線構(gòu)成的。點代表所研究的對象，線表示對象間的關系。1、圖的分類：無向圖，有向圖無向圖：由點和邊所組成的圖。表示為G=(V,E).有向圖：由點和弧所組成的圖。表示為D=(V,A)點的集合用V表示，V={vi}2、圖上的基本概念：（1）邊：圖中不帶箭頭的連線叫做邊(edge)，邊的集合記為E={ej

}，一條邊可以用兩點[vi,vj

]表示,ej=[vi,vj].弧：圖中帶箭頭的連線叫做弧(arc),弧的集合記為A，A={ak

},一條弧也是用兩點表示，ak=[vi,vj

],弧有方向：vi為始點，vj為終點OR35例1.v7v1v2v3v4e1e2e3e4e5e6e7a9v1v2v3v4v5v6a1a2a8a4a3a5a6a7a10環(huán)：兩端點相同的邊。多重邊：若兩點之間有多于一條邊，則稱這些邊為多重邊。簡單圖：無環(huán)、無多重邊的圖。多重圖：無環(huán)，但允許有多重邊的圖。e7OR36（2）次：以點u為端點的邊的條數(shù)，叫做點u的次。懸掛點：次為1的點叫做懸掛點；孤立點：次為0的點叫做孤立點；奇點：次為奇數(shù)則稱奇點；偶點：次為偶數(shù)則稱偶點?；径ɡ恚?、圖G=(V,E)中，所有點的次之和是邊數(shù)的兩倍，即2、任一圖中，奇點的個數(shù)為偶數(shù)。OR376.2樹與最小生成樹1、樹的概念與性質(zhì)樹：無圈的連通圖稱為樹。定理：定量3：設圖G=（V,E)是一個樹，p(G)≥2,則G中至少有兩個懸掛點。定量4：圖G=（V,E)是一個樹的充要條件是G不含圈，且恰有p－1條邊。定量5：圖G=（V,E)是一個樹的充要條件是G是連通圖，并且q(G)=p(G)-1.定量6：圖G=（V,E)是一個樹的充要條件是任意兩個頂點之間恰好有一條鏈。OR392、圖的支撐樹支撐樹：設T=(V,E’)是圖G=(V,E)的支撐子圖，如果T是一個樹，則稱T為G的支撐樹。定理7：圖G有支撐樹的充要條件是圖G是連通的。求支撐樹的方法：破圈法：即任取一個圈，從圈中去掉一條邊，對余下的圖重復這個步驟，直至圖中不含圈為止。避圈法：在圖中每次任取一條邊，與已經(jīng)取得的任何一些邊不夠成圈，重復這個過程，直到不能進行為止。OR3103、最小支撐樹最小支撐樹：當一個連通圖的所有邊都被賦權，則取不同邊構(gòu)成的支撐樹具有不同的總權數(shù)，其中總權數(shù)最小的支撐樹稱為最小支撐樹。求最小支撐樹的方法：破圈法：在連通圖中任取一個圈，去掉一條權數(shù)最大的邊，在余下的圖中重復上述步驟，直至無圈為止。避圈法：將連通圖所有邊按權數(shù)從小到大排序，每次從未選的邊中選一條權數(shù)最小的邊，并使之與已選的邊不能構(gòu)成圈，直至得到最小支撐樹。OR3116.3最短路問題引例:單行線交通網(wǎng)：v1到v8使總費用最小的旅行路線。最短路問題的一般描述：對D=（V，A），a=（vi，vj），w（a）=wij，P是vs到vt的路，定義路P的權是P中所有弧的權的和，記為w（P），則最短路問題為：V2(v1,6）路P0的權稱為從vs到vt的距離，記為：d（vs，vt）最短路：賦權有向圖D=（V，A）中，從始點到終點的權值最小的路稱為最短路。OR313最短路算法Dijkstra算法：有向圖，wij≥0一般結(jié)論：Dijkstra算法基本思想:采用標號法:P標號和T標號P標號：已確定出最短路的節(jié)點(永久性標號)。T標號：未確定出最短路的節(jié)點，但表示其距離的上限(試探性標號)。算法的每一步都把某一點的T標號改為P標號直至改完為止.Si：P標號節(jié)點的集合。

OR314Dijkstra算法的基本步驟：1:給vs以P標號,P(vs)=0,其余各點均給T標號,T(vi)=+∞2:若vj點為剛得到P標號的點,考慮這樣的點vj,(vi,vj)∈E,且vj為T標號.3:對vj的T標號進行如下更改:4:比較所有具有T標號的點,把最小者改為P標號.當存在兩個以上最小值時,可同時改為P標號.若全部改為P標號,則停止.否則轉(zhuǎn)回(2).OR315最短路問題的算法：Bellman算法適用范圍：有向圖，且圖中有wij﹤0。假設前提：任意兩點vi,vj之間都有一條弧。（若無，則添加一條虛擬的弧，且其權值為＋∞。）公式來源分析：OR317基本思路：用逐次逼近來求網(wǎng)絡中的最短路：每次求出從始點到網(wǎng)絡中其余各點有限制的最短路。若第一次逼近即得最短路，則限制其最短路只有一條弧，其路長記為；若第二次逼近即得最短路，則限制其最短路不超過兩條弧，其路長記為；依此類推，第k次逼近得最短路，則限制其不超過k條弧。一般的，最多逼近n-1次即得到最短路。OR318為了求得公式的解可以運用以下公式：令：OR319舉例：求v1到各點的最短路OR321計算過程見下表：025-30-2406400-3047203-10025-3020-3611020-36615020-3361410020-336910020-336910OR322當計算到第六步時，計算結(jié)果與第五步相同，則表中第六列的數(shù)字分別表示點v1到其它各點的最短路。尋找最短路徑的方法：反向追蹤法。OR3236.4最大流問題1、掌握可行流、增廣鏈、截集、截量等基本概念2、掌握基本定理8及其證明3、掌握求最大流的標號法OR325引例：如下輸水網(wǎng)絡，南水北調(diào)工程，從vs到vt送水，弧旁數(shù)字前者為管道容量，后者為現(xiàn)行流量，如何調(diào)運輸水最多？vsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)OR3263、可行流對給定的D=(V,A,C)，把滿足下列兩個條件1），2）的流稱為可行流。1）容量限制條件:對D中的每一條弧（vi，vj），有0≤fij≤cij;2）平衡條件:對中間點vi，流入量等于流出量,即;

對發(fā)點vs，有;

對收點vt，有.是可行流的流量，是發(fā)點的凈輸出量，是收點的凈入量。注意：任一D=(V,A,C)都存在可行流。如零流就是一個可行流。如果D=(V,A,C)中沒有給出弧上的流量fij，可認為fij＝0。OR3294、最大流使得從網(wǎng)絡發(fā)點到收點得總流量（W）達到最大得可行流f=｛fij｝稱為最大流。最大流問題就是求一個流f=｛fij｝使其流量達到最大，并且滿足：注意：尋求網(wǎng)絡中的最大流就相當于求線性規(guī)劃模型的最優(yōu)解。OR3305.截集、截量、最小截量截量：截集（，）中所有弧的容量之和稱為該截集的截量，記為c（，）.最小截集：在D=(V,A,C)的所有截集中，截量最小的截集稱為最小截集，記為()。OR331注意：容量網(wǎng)絡圖D的截集不是唯一的，截集個數(shù)是有限的。如果在圖D中把任何一個截集中的弧丟掉，那么從發(fā)點就不能通往收點。所以，截集是從發(fā)點到收點的必經(jīng)之道。從而，有任何一個可行流的流量都不會超過任意截集的截量。OR3326、增廣鏈在容量網(wǎng)絡D=(V,A,C)中，若為網(wǎng)絡中從vs到vt的一條鏈，給鏈定方向為從vs到vt，上與同方向的弧稱為前向弧，與反方向的弧稱為后向弧，前向弧和后向弧的集合分別用和來表示。設是一個可行流，如果滿足：則稱為從vs到vt的（關于f的）增廣鏈。OR333增廣鏈的實際意義：沿著這條鏈從vs到vt輸送的流，還有潛力可挖，只需按照定理證明中的調(diào)整方法，就可以把流量提高；調(diào)整后的流，在各點仍滿足平衡條件及容量限制條件，即仍為可行流。這樣，就得到了一個尋求最大流的方法：從一個可行流開始，尋求關于這個可行流的增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個新的可行流，其流量比原來的可行流要大，重復這個過程，直到不存在關于該流的增廣鏈時就的得到了最大流。OR3347、最大流量最小截量定理定理8：可行流是最大流的充要條件是不存在從vs到vt的關于的增廣鏈。重要結(jié)論：任一容量網(wǎng)絡D=(V,A,C)中，最大流的流量等于最小截集的截量?？尚辛鱢是最大流的充分必要條件是不存在從到可行流f是最大流的充分必要條件是不存在從到可行流f是最大流的充分必要條件是不存在從OR335定理8可行流是最大流的充要條件是不存在從vs到vt的關于的增廣鏈證明：先證明：若可行流是最大流，則中不存在關于的增廣鏈。若是最大流，設D是的增廣鏈。令：由增廣鏈的定義可知，令：

不難驗證該流是一個可行流，且其最大流量比原流大。則，證明原可行流不是最大流，與假設矛盾。OR336再證明：若D中不存在關于的增廣鏈，則該流是最大流。利用下面的方法來定義V1:OR337求最大流的方法：標號法方法很簡單：首先找到一條增廣鏈，沿此進行最大可能調(diào)整，再找增廣鏈，再調(diào)整，直到?jīng)]有增廣鏈為止。

如何找增廣鏈？如何調(diào)整？設已有一個可行流f（若網(wǎng)絡中沒有給定f，則可以設f是零可行流），通過標號過程來找到增廣鏈，通過調(diào)整過程來對增廣鏈上的流量進行調(diào)整。第一步標號過程，通過標號來尋找可增廣鏈；第二步調(diào)整過程，沿可增廣鏈調(diào)整f，以增加流量。OR338標號法的基本方法介紹1.標號過程在這個過程中，網(wǎng)絡中的每個標號點的標號由兩個