運(yùn)籌學(xué)-圖與網(wǎng)絡(luò)分析課件

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

ABCDA

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

}，一條邊可以用兩點(diǎn)[vi,vj

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

},一條弧也是用兩點(diǎn)表示，ak=[vi,vj

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

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

對發(fā)點(diǎn)vs，有;

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

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

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