運籌學(xué)-圖與網(wǎng)絡(luò)分析

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

ABCDA

BcDOR32可編輯ppt鐵路交通圖此圖是我國北京,上海等十個城市間的交通圖,反映了這十個城市間的鐵路分布情況.點表示城市,點間的連線表示兩個城市間的鐵路線.諸如此類問題還有電話線分布圖或煤氣管道分布圖等.北京濟(jì)南徐州青島南京上海連云港鄭州武漢天津OR33可編輯ppt球隊比賽圖五個球隊比賽,比過的兩個隊之間用連線相連，還沒有比賽的隊之間沒有連線v5v4v3v2v1OR34可編輯ppt6.1圖的基本概念圖是由點和線構(gòu)成的。點代表所研究的對象，線表示對象間的關(guān)系。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可編輯ppt例1.v7v1v2v3v4e1e2e3e4e5e6e7a9v1v2v3v4v5v6a1a2a8a4a3a5a6a7a10環(huán)：兩端點相同的邊。多重邊：若兩點之間有多于一條邊，則稱這些邊為多重邊。簡單圖：無環(huán)、無多重邊的圖。多重圖：無環(huán)，但允許有多重邊的圖。e7OR36可編輯ppt（2）次：以點u為端點的邊的條數(shù)，叫做點u的次。懸掛點：次為1的點叫做懸掛點；孤立點：次為0的點叫做孤立點；奇點：次為奇數(shù)則稱奇點；偶點：次為偶數(shù)則稱偶點?；径ɡ恚?、圖G=(V,E)中，所有點的次之和是邊數(shù)的兩倍，即2、任一圖中，奇點的個數(shù)為偶數(shù)。OR37可編輯ppt（3）鏈：點邊交替序列稱為鏈；圈：首尾相連的鏈稱為圈；初等鏈：鏈中各點均不同的鏈；初等圈：圈中各點均不同的圈；簡單鏈：鏈中邊均不同的鏈；簡單圈：圈中邊均不同的圈。（4）連通圖：任意兩點之間至少有一條鏈的圖。連通分圖：對不連通的圖，每一連通的部分稱為一個連通分圖。支撐子圖：對G=(V,E)，若G’=(V’,E’)，使V’＝V，E’包含于E，則G’是G的一個支撐子圖。賦權(quán)圖：在圖中，如果每一條邊（?。┒急毁x予一個權(quán)值wij，則稱圖G為賦權(quán)圖。（5）路：在有向圖中，如果鏈上每條弧的箭線方向與鏈行進(jìn)方向相同，則稱之為路?；芈罚菏孜蚕嘟拥穆贩Q回路OR38可編輯ppt6.2樹與最小生成樹1、樹的概念與性質(zhì)樹：無圈的連通圖稱為樹。定理：定量3：設(shè)圖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)是一個樹的充要條件是任意兩個頂點之間恰好有一條鏈。OR39可編輯ppt2、圖的支撐樹支撐樹：設(shè)T=(V,E’)是圖G=(V,E)的支撐子圖，如果T是一個樹，則稱T為G的支撐樹。定理7：圖G有支撐樹的充要條件是圖G是連通的。求支撐樹的方法：破圈法：即任取一個圈，從圈中去掉一條邊，對余下的圖重復(fù)這個步驟，直至圖中不含圈為止。避圈法：在圖中每次任取一條邊，與已經(jīng)取得的任何一些邊不夠成圈，重復(fù)這個過程，直到不能進(jìn)行為止。OR310可編輯ppt3、最小支撐樹最小支撐樹：當(dāng)一個連通圖的所有邊都被賦權(quán)，則取不同邊構(gòu)成的支撐樹具有不同的總權(quán)數(shù)，其中總權(quán)數(shù)最小的支撐樹稱為最小支撐樹。求最小支撐樹的方法：破圈法：在連通圖中任取一個圈，去掉一條權(quán)數(shù)最大的邊，在余下的圖中重復(fù)上述步驟，直至無圈為止。避圈法：將連通圖所有邊按權(quán)數(shù)從小到大排序，每次從未選的邊中選一條權(quán)數(shù)最小的邊，并使之與已選的邊不能構(gòu)成圈，直至得到最小支撐樹。OR311可編輯ppt避圈法的基本步驟P259第一步：令i＝1，E0＝空集。第二步：選一條邊ei∈E﹨Ei-1,使ei是使（V,Ei-1∪｛e｝）不含圈的所有邊e（e∈E﹨Ei-1）中權(quán)最小的邊。令Ei＝Ei-1∪｛ei｝,如果這樣的邊不存在，則T=(V,Ei-1)是最小樹。第三步：把i換成i＋1，轉(zhuǎn)入第2步。OR312可編輯ppt6.3最短路問題引例:單行線交通網(wǎng)：v1到v8使總費用最小的旅行路線。最短路問題的一般描述：對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）中，從始點到終點的權(quán)值最小的路稱為最短路。OR313可編輯ppt最短路算法Dijkstra算法：有向圖，wij≥0一般結(jié)論：Dijkstra算法基本思想:采用標(biāo)號法:P標(biāo)號和T標(biāo)號P標(biāo)號：已確定出最短路的節(jié)點(永久性標(biāo)號)。T標(biāo)號：未確定出最短路的節(jié)點，但表示其距離的上限(試探性標(biāo)號)。算法的每一步都把某一點的T標(biāo)號改為P標(biāo)號直至改完為止.Si：P標(biāo)號節(jié)點的集合。

OR314可編輯pptDijkstra算法的基本步驟：1:給vs以P標(biāo)號,P(vs)=0,其余各點均給T標(biāo)號,T(vi)=+∞2:若vj點為剛得到P標(biāo)號的點,考慮這樣的點vj,(vi,vj)∈E,且vj為T標(biāo)號.3:對vj的T標(biāo)號進(jìn)行如下更改:4:比較所有具有T標(biāo)號的點,把最小者改為P標(biāo)號.當(dāng)存在兩個以上最小值時,可同時改為P標(biāo)號.若全部改為P標(biāo)號,則停止.否則轉(zhuǎn)回(2).OR315可編輯ppt用Dijkstra算法求圖中v1到v8的最短路OR316可編輯ppt最短路問題的算法：Bellman算法適用范圍：有向圖，且圖中有wij﹤0。假設(shè)前提：任意兩點vi,vj之間都有一條弧。（若無，則添加一條虛擬的弧，且其權(quán)值為＋∞。）公式來源分析：OR317可編輯ppt基本思路：用逐次逼近來求網(wǎng)絡(luò)中的最短路：每次求出從始點到網(wǎng)絡(luò)中其余各點有限制的最短路。若第一次逼近即得最短路，則限制其最短路只有一條弧，其路長記為；若第二次逼近即得最短路，則限制其最短路不超過兩條弧，其路長記為；依此類推，第k次逼近得最短路，則限制其不超過k條弧。一般的，最多逼近n-1次即得到最短路。OR318可編輯ppt為了求得公式的解可以運用以下公式：令：OR319可編輯ppt基本步驟：1、令，其中，若v1與vj間沒弧，則記w1j=+∞。2、當(dāng)計算到第k步時，若有成立，則停止計算。即為從v1到各點的最短路。OR320可編輯ppt舉例：求v1到各點的最短路OR321可編輯ppt計算過程見下表：025-30-2406400-3047203-10025-3020-3611020-36615020-3361410020-336910020-336910OR322可編輯ppt當(dāng)計算到第六步時，計算結(jié)果與第五步相同，則表中第六列的數(shù)字分別表示點v1到其它各點的最短路。尋找最短路徑的方法：反向追蹤法。OR323可編輯pptOR324可編輯ppt6.4最大流問題1、掌握可行流、增廣鏈、截集、截量等基本概念2、掌握基本定理8及其證明3、掌握求最大流的標(biāo)號法OR325可編輯ppt引例：如下輸水網(wǎng)絡(luò)，南水北調(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)OR326可編輯ppt最大流問題的基本概念1、容量網(wǎng)絡(luò)如果有向連通網(wǎng)絡(luò)圖D=(V,A)的每一條?。╲i，vj）上都被賦予一個非負(fù)數(shù)，以表示通過該弧的最大通行能力，稱為弧的容量，則稱這樣的網(wǎng)絡(luò)為容量網(wǎng)絡(luò)，記作D=(V,A,C)。OR327可編輯ppt2、流在D=(V,A,C)中，如果實際通過每一弧（vi，vj）的流量是fij，則稱集合f=｛fij｝為網(wǎng)絡(luò)D=(V,A,C)上的一個流。OR328可編輯ppt3、可行流對給定的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，可認(rèn)為fij＝0。OR329可編輯ppt4、最大流使得從網(wǎng)絡(luò)發(fā)點到收點得總流量（W）達(dá)到最大得可行流f=｛fij｝稱為最大流。最大流問題就是求一個流f=｛fij｝使其流量達(dá)到最大，并且滿足：注意：尋求網(wǎng)絡(luò)中的最大流就相當(dāng)于求線性規(guī)劃模型的最優(yōu)解。OR330可編輯ppt5.截集、截量、最小截量截量：截集（，）中所有弧的容量之和稱為該截集的截量，記為c（，）.最小截集：在D=(V,A,C)的所有截集中，截量最小的截集稱為最小截集，記為()。OR331可編輯ppt注意：容量網(wǎng)絡(luò)圖D的截集不是唯一的，截集個數(shù)是有限的。如果在圖D中把任何一個截集中的弧丟掉，那么從發(fā)點就不能通往收點。所以，截集是從發(fā)點到收點的必經(jīng)之道。從而，有任何一個可行流的流量都不會超過任意截集的截量。OR332可編輯ppt6、增廣鏈在容量網(wǎng)絡(luò)D=(V,A,C)中，若為網(wǎng)絡(luò)中從vs到vt的一條鏈，給鏈定方向為從vs到vt，上與同方向的弧稱為前向弧，與反方向的弧稱為后向弧，前向弧和后向弧的集合分別用和來表示。設(shè)是一個可行流，如果滿足：則稱為從vs到vt的（關(guān)于f的）增廣鏈。OR333可編輯ppt增廣鏈的實際意義：沿著這條鏈從vs到vt輸送的流，還有潛力可挖，只需按照定理證明中的調(diào)整方法，就可以把流量提高；調(diào)整后的流，在各點仍滿足平衡條件及容量限制條件，即仍為可行流。這樣，就得到了一個尋求最大流的方法：從一個可行流開始，尋求關(guān)于這個可行流的增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個新的可行流，其流量比原來的可行流要大，重復(fù)這個過程，直到不存在關(guān)于該流的增廣鏈時就的得到了最大流。OR334可編輯ppt7、最大流量最小截量定理定理8：可行流是最大流的充要條件是不存在從vs到vt的關(guān)于的增廣鏈。重要結(jié)論：任一容量網(wǎng)絡(luò)D=(V,A,C)中，最大流的流量等于最小截集的截量?？尚辛鱢是最大流的充分必要條件是不存在從到可行流f是最大流的充分必要條件是不存在從到可行流f是最大流的充分必要條件是不存在從OR335可編輯ppt定理8可行流是最大流的充要條件是不存在從vs到vt的關(guān)于的增廣鏈證明：先證明：若可行流是最大流，則中不存在關(guān)于的增廣鏈。若是最大流，設(shè)D是的增廣鏈。令：由增廣鏈的定義可知，令：

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

如何找增廣鏈？如何調(diào)整？設(shè)已有一個可行流f（若網(wǎng)絡(luò)中沒有給定f，則可以設(shè)f是零可行流），通過標(biāo)號過程來找到增廣鏈，通過調(diào)整過程來對增廣鏈上的流量進(jìn)行調(diào)整。第一步標(biāo)號過程，通