第11章最短路問(wèn)題1.問(wèn)題提出2.圖論基本概念3.最短路問(wèn)題求解算法4.建模實(shí)例第1頁(yè)§1問(wèn)題提出某學(xué)校行政部門u0經(jīng)常有些人到7個(gè)部門辦事，希望在現(xiàn)有道路網(wǎng)絡(luò)中確定他們行走路線，使他們到各部門旅程最短。圖中已經(jīng)標(biāo)明了部門到部門之間距離。第2頁(yè)§2圖論基本概念圖論是離散數(shù)學(xué)主要分支，在物理學(xué)、化學(xué)、系統(tǒng)控制、電力通訊、編碼理論、可靠性理論、科學(xué)管理、電子計(jì)算機(jī)等各個(gè)領(lǐng)域都含有極其廣泛應(yīng)用。圖論歷史能夠追溯到1736年，這一年發(fā)表了圖論第一篇論文，處理了著名哥尼斯堡（K?nigsberg）七橋問(wèn)題。第3頁(yè)K?nigsberg七橋問(wèn)題哥尼斯堡城中有七座橋?qū)⑵绽赘駹?Pregel)河中兩個(gè)島與河岸聯(lián)結(jié)起來(lái)，當(dāng)初人們熱衷于這么一個(gè)問(wèn)題：一個(gè)人能否從四塊陸地中任何一塊出發(fā)走過(guò)七座橋，每座橋恰走一次，最終回到起點(diǎn)？(a)ABCDABCD(b)第4頁(yè)圖論基本概念1.圖定義G=(V,E,ψ)頂點(diǎn)，邊，e與v連接，v與e關(guān)聯(lián)，相鄰，環(huán)，重邊，平面圖，完全圖（完備圖），二部圖（偶圖），子圖，生成圖。與一個(gè)頂點(diǎn)vi關(guān)聯(lián)邊數(shù)目稱為vi度（或次）。路、圈和連通有向圖、賦權(quán)圖第5頁(yè)圖論一個(gè)定理定理：∑d(v)=2|E|

v∈V證：因?yàn)槊恳粭l邊提供給點(diǎn)度為2，所以圖中全部點(diǎn)度數(shù)總和是邊數(shù)2倍。推論：在任何圖中，奇點(diǎn)個(gè)數(shù)為偶數(shù)。第6頁(yè)2.圖矩陣表示對(duì)于任意圖G，定義一個(gè)n×m階矩陣M=（mij）n×m(n為頂點(diǎn)數(shù)，m為邊數(shù))，其中mij是vi和ej相關(guān)聯(lián)次數(shù)（0,1或2等），該矩陣稱為G關(guān)聯(lián)矩陣。圖另一個(gè)表示形式是鄰接矩陣A=（aij）n×n，其中aij是連接ai和aj邊數(shù)目。第7頁(yè)圖矩陣表示關(guān)聯(lián)矩陣鄰接矩陣第8頁(yè)§3最短路問(wèn)題求解算法設(shè)G為賦權(quán)有向圖或無(wú)向圖，G邊上權(quán)均非負(fù)。1.DijkstraAlgorithm:求G中從頂點(diǎn)u0到其余頂點(diǎn)最短路。定義：對(duì)每個(gè)頂點(diǎn)v，定義兩個(gè)標(biāo)號(hào)l(v),z(v),其中l(wèi)(v)為從u0到v路長(zhǎng)；z(v)為v父親點(diǎn)（前一個(gè)點(diǎn)）。S：含有永久標(biāo)號(hào)頂集。算法過(guò)程就是在每一步改進(jìn)這兩個(gè)標(biāo)號(hào)，最終l(v)為u0到v最短路長(zhǎng)。輸入帶權(quán)鄰接矩陣（距離矩陣）w(u,v).第9頁(yè)最短路問(wèn)題求解算法DijkstraAlgorithmDijkstra算法所需時(shí)間與n2成正比。第10頁(yè)用Dijkstra求解最短路問(wèn)題例求從頂點(diǎn)u0到其余頂點(diǎn)最短路。解：先寫出距離矩陣（實(shí)際應(yīng)為對(duì)稱矩陣）第11頁(yè)Dijkstra算法迭代步驟以下迭代l(ui)次數(shù)u0u1u2u3u4u5u6u7

10∞∞∞∞∞∞∞221

8∞∞∞∞328∞∞10∞483∞10∞58610126710127912812最終標(biāo)識(shí)：l(v)021736912z(v)u0u0u0u5u1u4u3u4

第12頁(yè)最短路問(wèn)題求解算法2.FloydAlgorithm(1962):求任意兩點(diǎn)間最短路。D=（dij）n×n,dij是i到j(luò)最短路長(zhǎng)，P=（pij）n×n,pij是i到j(luò)最短路上中間節(jié)點(diǎn)最大號(hào)碼，pij=0，表示無(wú)中間節(jié)點(diǎn)，(1)賦初值：dij=wij,pij=0,k=1(2)更新dij,pij：對(duì)全部i,j，若dik+dkj<dij，則dij=dik+dkj,pij=k(3)若k=n，停頓；不然k=k+1,轉(zhuǎn)(2).第13頁(yè)FloydAlgorithm例已知距離矩陣為

求任意兩點(diǎn)之間最短路。第14頁(yè)FloydAlgorithm解：D(0)=W,P(0)=(0)n×n第15頁(yè)建模案例分析B題鋼管訂購(gòu)和運(yùn)輸?shù)?6頁(yè)第17頁(yè)B鋼管運(yùn)輸分析求解步驟1.用Floyd算法求出鐵道兩點(diǎn)間最短路長(zhǎng)，將路長(zhǎng)轉(zhuǎn)成費(fèi)用。2.與公路運(yùn)價(jià)組成矩陣D，再用Floyd求出S1,…,S7到A1,…,A15最短路，將購(gòu)置單價(jià)計(jì)入運(yùn)費(fèi)之中。第18頁(yè)第12章匹配與覆蓋及其應(yīng)用§1匹配與覆蓋1.基本概念定義1設(shè)若M邊互不相鄰，則稱M是G一個(gè)匹配。M邊稱為匹配邊，E\M邊稱為自由邊，若(u,v)∈M，則稱u（或v）是v（或u）配偶。若頂點(diǎn)v與M一條邊關(guān)聯(lián)，則稱v是M-飽和；不然稱為M-非飽和。若M使G中每個(gè)頂點(diǎn)都是M-飽和，稱M是G完美（理想）匹配。設(shè)M是G一個(gè)匹配，若不存在M'使|M'|>|M|，則稱M為G最大匹配。第19頁(yè)匹配與覆蓋顯然，完美匹配一定是最大匹配，反之不一定成立。(a)最大匹配(b)完美匹配第20頁(yè)匹配與覆蓋定義2設(shè)若G每條邊都與K一個(gè)頂點(diǎn)關(guān)聯(lián)，則稱K是圖G一個(gè)覆蓋。設(shè)K是G一個(gè)覆蓋，若不存在覆K'使|K'|<|K|，則稱K是一個(gè)最小覆蓋。第21頁(yè)匹配與覆蓋下列圖為居民小區(qū)，安裝消防設(shè)施，使每個(gè)相連街道都有消防設(shè)施可用。覆蓋：(v1,v2,v3,v4,v5)，(v1,v2,v3,v4)，(v2,v3,v4)，(v1,v3,v5)，而(v2,v3,v4)，(v1,v3,v5)是最小覆蓋。(c)居民小區(qū)v1v2v4v5v3第22頁(yè)2.性質(zhì)定義3設(shè)M是圖G=(V,E)匹配，GM交織路是指邊在E\M和M中交織出現(xiàn)路，M可擴(kuò)路（增廣路）是指其起點(diǎn)和終點(diǎn)都是M非飽和M交織路。定理1（Berge1957）設(shè)M是G一個(gè)匹配，則M是最大匹配充要條件是，G沒(méi)有M-增廣路。定理2設(shè)M是G匹配，K是覆蓋，則(1)|M|≤|K|(2)若|M*|=|K~|，則M*是最大匹配，K~是最小覆蓋。第23頁(yè)3.二部圖匹配定理3（K?nig,1931）若M*和K~分別是二部圖G最大匹配和最小覆蓋，則|M*|=|K~|定理4(Hall,1935)對(duì)二部圖G=(X,Y,E),G存在飽和X每個(gè)頂點(diǎn)匹配充要條件是：對(duì)任何SX,都有|N(S)|≥|S|，這里N(S)為與S頂點(diǎn)相鄰全部頂點(diǎn)集合。假如G中全部頂點(diǎn)度數(shù)都為k，則稱圖G是k正則。推論若G是k正則二部圖（k>0），則G有完美匹配。第24頁(yè)二部圖匹配例：假如一個(gè)鄉(xiāng)村里每位姑娘恰好認(rèn)識(shí)k位小伙子，而每個(gè)小伙子也恰好認(rèn)識(shí)k位姑娘，則每位姑娘能夠和她認(rèn)識(shí)一個(gè)小伙子結(jié)婚，而且每個(gè)小伙子也能和他認(rèn)識(shí)一位姑娘結(jié)婚。此即為“婚姻定理”。依據(jù)上面定理，Edmonds于1965年提出了以下匈牙利算法，處理了二部圖基數(shù)匹配問(wèn)題，步驟以下：第25頁(yè)二部圖匹配匈牙利算法：(1)設(shè)G=(X,Y,E)是二部圖，M是一個(gè)匹配；(2)若M飽和X每個(gè)頂點(diǎn)，則算法終止，M為最大匹配；不然，取M-非飽和點(diǎn)u∈X，令S={u},T=Φ;(3)若N(S)=T,因?yàn)閨T|=|S|-1，所以|N(S)|<|S|,算法終止，由定理4（Hall），不存在飽和X每個(gè)頂點(diǎn)匹配；不然取y∈N(S)\T;(4)若y是飽和，設(shè)yz∈M,用S∪{z}代替S，T∪{y}代替T，轉(zhuǎn)(3)（此時(shí)|T|=|S|-1仍成立）；不然設(shè)P是M增廣路P(u,y),并令M=MΔE(P)（對(duì)稱差），轉(zhuǎn)(2)第26頁(yè)二部圖基數(shù)匹配例x1x2x3x4x5y1y2y3y4y5第27頁(yè)二部圖基數(shù)匹配例x1x2x3x4x5y1y2y3y4y5第28頁(yè)4.二部圖賦權(quán)匹配G是完全二部圖，有兩個(gè)頂點(diǎn)集X={x1,x2,…,xn}，Y={y1,y2,…,yn}分別表示職員和工作，xi和yj之間用邊相連，其權(quán)為wij表示職員xi做yj工作時(shí)效率，對(duì)每人分配一件工作，使總效率最大。能夠用Kuhn-Munkres算法求賦權(quán)完全二部圖最正確匹配。第29頁(yè)二部圖賦權(quán)匹配定義：在G頂點(diǎn)集V=X∪Y上定義一個(gè)實(shí)值函數(shù)L，使得任何x∈X,y∈Y都有L(x)+L(y)≥w(x,y)其中w(x,y)是邊(x,y)上權(quán),稱函數(shù)L(v)為該二部圖一個(gè)可行頂點(diǎn)標(biāo)號(hào)。若用EL表示使上式等號(hào)成立那些邊集合，即EL={(x,y)|(x,y)∈E,L(x)+L(y)=w(x,y)}則稱以EL為邊集G生成子圖為G對(duì)應(yīng)于可行頂點(diǎn)標(biāo)號(hào)L相等子圖，記為GL.第30頁(yè)二部圖賦權(quán)匹配可行頂點(diǎn)標(biāo)號(hào)總是存在，如令第31頁(yè)二部圖賦權(quán)匹配定理：設(shè)L是G可行頂點(diǎn)標(biāo)號(hào)，若GL包含完美（基數(shù)）匹配M*，則M*是G最正確（最大權(quán)）匹配。由上述定理知，欲求二部圖最正確匹配，只需用匈牙利（Hungarian）算法求相等子圖GL完美匹配。若GL不存在完美匹配，Kuhn和Munkres給出了一個(gè)修改頂點(diǎn)標(biāo)號(hào)L算法，能夠使新相等子圖最大匹配擴(kuò)大，這么，最終使相等子圖含有完美匹配。第32頁(yè)二部圖賦權(quán)匹配Kuhn-Munkres算法：(1)設(shè)G=(X,Y,E)是二部圖，從任一可行頂點(diǎn)標(biāo)號(hào)L開(kāi)始，確定GL，并在GL中選取一個(gè)匹配M。(2)若X是飽和，則M是GL完美匹配，是G最正確匹配，算法終止；不然，在GL中取一個(gè)M-非飽和點(diǎn)u∈X，令S={u}，T=Φ；第33頁(yè)二部圖賦權(quán)匹配(3)若NGL(S)=T,則GL沒(méi)有完美匹配，計(jì)算給出可行頂點(diǎn)標(biāo)號(hào)L'，以L'代替L，以GL'代替GL。不然轉(zhuǎn)(4);(4)在NGL(S)\T中選擇一個(gè)頂點(diǎn)y,若y是M飽和，而且yz∈M,則用S∪{z}代替S，T∪{y}代替T，轉(zhuǎn)(3)；不然取GL中一條M增廣路P(u,y),并令M=MΔE(P)（對(duì)稱差），轉(zhuǎn)(2)第34頁(yè)賦權(quán)匹配例1五個(gè)人x1,x2,x3,x4,x5做五件工作y1,y2,y3,y4,y5，工作效率以以下矩陣所表示：

一個(gè)人只能做一件工作，問(wèn)怎樣安排工作使總工作效率最高？（結(jié)果為14）第35頁(yè)二部圖賦權(quán)匹配例1x1x2x3x4x5y1y2y3y4y5第36頁(yè)賦權(quán)匹配例2五種原材料A、B、C、D、E都能夠用來(lái)生產(chǎn)a、b、c、d、e五種產(chǎn)品，成本以以下矩陣所表示：

一個(gè)材料只能生產(chǎn)一個(gè)產(chǎn)品，問(wèn)什么生產(chǎn)方案使成本最低（要求寫出求解過(guò)程）？（結(jié)果為30）第37頁(yè)§2建模案例鎖具裝箱問(wèn)題(94B)

某廠生產(chǎn)一個(gè)彈子鎖具，每個(gè)鎖具鑰匙有5個(gè)槽高度從{1,2,3,4,5,6}中任取一數(shù)。因?yàn)楣に囋?，制造鎖具對(duì)5個(gè)槽高度有兩個(gè)限制：最少有3個(gè)不一樣數(shù)；相鄰兩槽高度之差不能為5。滿足以上條件制造出來(lái)全部互不相同鎖具稱為一批。若4個(gè)相同，另一槽高度差為1，則可能互開(kāi)。其它情形不可能互開(kāi)。在原來(lái)一批鎖具中隨機(jī)取60個(gè)裝為一箱，成箱購(gòu)置用戶總埋怨購(gòu)得鎖含有互開(kāi)現(xiàn)象。怎樣裝箱（60個(gè)為一箱），怎樣給箱子以標(biāo)志，出售時(shí)怎樣利用這些標(biāo)志，使團(tuán)體用戶降低埋怨。第38頁(yè)第13章行遍歷問(wèn)題§1中國(guó)郵遞員問(wèn)題一、問(wèn)題提出一位郵遞員從郵局出發(fā)，帶著所管轄地域信件、報(bào)紙支投遞，投遞結(jié)束后回到郵局，為了投遞完全部郵件，當(dāng)然他必須經(jīng)過(guò)其所管轄每條街道最少一次，請(qǐng)為他設(shè)計(jì)一條路線，使行程盡可能短。

v2

2

6

7

v1

3

v5

6v3

1

1

v4第39頁(yè)中國(guó)郵遞員問(wèn)題這就是中國(guó)郵遞員問(wèn)題原始模型，是我國(guó)管梅谷教授于1962年首先提出。用圖論語(yǔ)言來(lái)敘述，中國(guó)郵遞員問(wèn)題就是在連通賦權(quán)圖G上求一個(gè)回路（未必是簡(jiǎn)單），過(guò)每邊最少一次，并使回路權(quán)最小。第40頁(yè)二、歐拉圖與Fleury算法定義設(shè)G=(V,E)是連通無(wú)向圖(1)經(jīng)過(guò)G每邊最少一次閉通路稱為（巡回）回路。(2)經(jīng)過(guò)G每邊恰好一次回路稱為Euler回路。(3)存在Euler回路圖稱為Euler圖。(4)過(guò)每邊恰好一次（路）鏈稱為Euler鏈。Euler回路、Euler鏈能夠形象地描述為“一筆畫問(wèn)題”。定理1連通圖G是Euler圖，當(dāng)且僅當(dāng)G中無(wú)奇度頂點(diǎn)。第41頁(yè)歐拉圖與Fleury算法Fleury算法：(1)任取一個(gè)v0∈V，令W=v0.(2)設(shè)鏈W=v0e1v1e2…eivi已選定，則從E\{e1,e2,…,ei}中選取一條與ei相鄰邊ei+1，除非已無(wú)選擇余地，不然不要選G\{e1,e2,…,ei}橋。(3)直到(2)不能進(jìn)行為止，算法終止時(shí)得到是Euler回路。第42頁(yè)三、奇偶點(diǎn)圖上作業(yè)法與Edmonds算法假如G不是連通Euler圖，則G中含有奇度頂點(diǎn)（但奇度頂點(diǎn)個(gè)數(shù)為偶數(shù)），此時(shí)圖G一條郵遞路線必定在一些街著上重復(fù)走了一次或?qū)掖?，它等價(jià)于在這些邊上加一條或多條重復(fù)邊，使新圖G'不含奇度頂點(diǎn)，而且所加邊總權(quán)為最小。設(shè)E1表示全部新增加邊集合，它是圖G邊集一個(gè)子集。怎樣求權(quán)最小新增邊集E1呢？第43頁(yè)奇偶點(diǎn)圖上作業(yè)法定理2E1為權(quán)最小新增邊集，當(dāng)且僅當(dāng)以下條件滿足：(1)E1中沒(méi)有重復(fù)出現(xiàn)邊；(2)在G每個(gè)回路上，屬于E1邊權(quán)和不超出該回路邊和二分之一。依據(jù)定理能夠從某一可行新增邊集開(kāi)始，進(jìn)行調(diào)整，最終得到最優(yōu)解。這種方法稱為“奇偶點(diǎn)圖上作業(yè)法”。第44頁(yè)奇偶點(diǎn)圖上作業(yè)法“奇偶點(diǎn)圖上作業(yè)法”對(duì)回路不太多圖是可行。當(dāng)回路很多時(shí)（如“田”字形圖形就有13個(gè)回路），要檢驗(yàn)全部回路是難以做到。Edmonds在1965年提出了一個(gè)有效方法，使中國(guó)郵遞員問(wèn)題得到了很好處理。第45頁(yè)Edmonds算法(1)依據(jù)給定圖G，結(jié)構(gòu)一個(gè)新圖G*，G*中頂點(diǎn)就是G中全部奇度頂點(diǎn)，并將G*中任意兩頂點(diǎn)都相連，此時(shí)G*是一個(gè)完全圖，G*中邊權(quán)等于G中頂點(diǎn)與間最短距離。(2)在G*中找一個(gè)最小權(quán)完美匹配M（M是G*中含有以下性質(zhì)一個(gè)邊集：G*中每個(gè)點(diǎn)恰與M中一條邊關(guān)聯(lián)，且M權(quán)最小）。(3)在G中將相互匹配奇度頂點(diǎn)用最短路徑相連，由此得到G最小新增邊集。第46頁(yè)Edmonds算法下面用Edmonds算法求解上圖中國(guó)郵遞員問(wèn)題。依據(jù)圖中奇度頂點(diǎn)v1,v2,v3,v5結(jié)構(gòu)一個(gè)完全圖G*，以下列圖。求G*最小權(quán)完美匹配M，得M={（v1,v2）,（v3,v5）}，其權(quán)為2+5=7，在G中加入（v1,v2）和（v3,v4,v1,v5）兩條最短路，使G變?yōu)镋uler圖，其權(quán)值為26+7=33。

v2

2

4

5

v1

2v3

3

5

v5

v2

2

6

7

v1

3

v5

6v3

1

1

v4第47頁(yè)§2推銷員問(wèn)題一、問(wèn)題提出一旅行售貨員需要到鄰近50個(gè)村鎮(zhèn)推銷他商品，最終回到出發(fā)點(diǎn)。問(wèn)怎樣安排旅行路線使總行程最短？旅行售貨員問(wèn)題（TravelingSalesmanProblem）是NP-完備問(wèn)題。第48頁(yè)推銷員問(wèn)題二、Hamilton圖定義1設(shè)G=(V,E)是連通無(wú)向圖(1)經(jīng)過(guò)G每個(gè)頂點(diǎn)恰好一次路徑，稱為G一條Hamilton路徑，簡(jiǎn)稱H路徑。(2)經(jīng)過(guò)G每個(gè)頂點(diǎn)恰好一次圈，稱為GHamilton圈，簡(jiǎn)稱H圈。(3)含Hamilton圈圖稱為Hamilton圖，簡(jiǎn)稱H圖。第49頁(yè)推銷員問(wèn)題上述旅行售貨員問(wèn)題中頂點(diǎn)表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)路，邊上權(quán)表示距離（時(shí)間、費(fèi)用），于是TSP就成為在賦權(quán)圖中尋找一條經(jīng)過(guò)每個(gè)頂點(diǎn)最少一次最短閉通路問(wèn)題。定義2在賦權(quán)圖G=(V,E)中(1)權(quán)最小Hamilton圈，稱為最正確H圈。(2)經(jīng)過(guò)每個(gè)頂點(diǎn)最少一次權(quán)最小閉通路稱為最正確推銷員回路。第50頁(yè)推銷員問(wèn)題普通情況，最正確Hamilton圈不一定是最正確推銷員回路，反之也不一定。（p213）但有以下定理。定理1設(shè)G=(V,E)是賦權(quán)圖，若對(duì)任意x,y,z∈V,z≠x,z≠y,都有w(x,y)≤w(x,z)+w(z,y),則圖G最正確H圈也是最正確推銷員回路。第51頁(yè)推銷員問(wèn)題能夠用G中任意兩點(diǎn)最短距離結(jié)構(gòu)一個(gè)完全圖G',則有定理2賦權(quán)圖G最正確推銷員回路權(quán)與G'最正確H圈權(quán)相同。故在賦權(quán)圖中尋求最正確推銷員回路問(wèn)題就可轉(zhuǎn)化為在一個(gè)完全賦權(quán)圖G'中尋求最正確H圈問(wèn)題。第52頁(yè)推銷員問(wèn)題三、TSP近似算法二邊逐次修正法，模擬退火法，彈性網(wǎng)法等第53頁(yè)§3建模案例最正確災(zāi)情巡視路線（98B）下列圖為某縣鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊數(shù)字為該路段公里數(shù)。

今年夏天該縣遭受水災(zāi)。為考查災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，率領(lǐng)相關(guān)部門責(zé)任人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地路線。

若分三組（路）巡視，試設(shè)計(jì)總旅程最短且各組盡可能均衡巡視路線。

假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度v=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，最少應(yīng)分幾組；給出這種分組下你認(rèn)為最正確巡視路線。

在上述關(guān)于T,t和v假定下，假如巡視人員足夠多，完成巡視最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視要求下，你認(rèn)為最正確巡視路線。

若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和v改變對(duì)最正確巡視路線影響。

第54頁(yè)第55頁(yè)第14章網(wǎng)絡(luò)流問(wèn)題

1．

最大流問(wèn)題E油田有

一個(gè)石油運(yùn)輸管網(wǎng)，Vs是石油產(chǎn)品產(chǎn)地，Vt是石油銷地，邊旁數(shù)子為單位時(shí)間允許最大輸油量（單位：桶/分鐘）。問(wèn)題是決定從Vs到Vt單位時(shí)間最大輸入油量。vsv1v2v3v4vt332224141第56頁(yè)第14章網(wǎng)絡(luò)流問(wèn)題

概念發(fā)點(diǎn)（source），收點(diǎn)（sink），中間點(diǎn)，C為定義在aij上容量函數(shù)，其值cij為弧aij容量。vsv1v2v3v4vt332224141第57頁(yè)最大流問(wèn)題

網(wǎng)絡(luò)N上流量指定義在弧集合A上一個(gè)函數(shù)f，記fij=f(aij)若流f還滿足(1)

容量限制條件0≤fij≤cij(2)

流量守恒條件∑fij-∑fji=0i≠s,t則稱f為可行流。第58頁(yè)最大流問(wèn)題一個(gè)網(wǎng)絡(luò)可行流總是存在，如令全部弧流量fij=0，就得到一個(gè)流，其流量val(f)=0，并稱該可行流為零流。確定E油田從Vs到Vt最大輸油量，

也就是在全部可行流方案中確定一個(gè)使流量到達(dá)最大方案。第59頁(yè)最大流問(wèn)題最大流問(wèn)題普通形式為第60頁(yè)2.最大流基本定理定義：在網(wǎng)絡(luò)Ｎ中，若點(diǎn)集Ｖ被剖分為兩個(gè)非空集合，使得，則把弧集稱為Ｎ中割。稱為割容量。

第61頁(yè)最大流基本定理輕易證實(shí)：任何一個(gè)可行流f流量都不會(huì)超出任一割容量，即尤其若有一可行流f和割，使上式等號(hào)成立，則f必為最大流，而必為最小割。第62頁(yè)可增路設(shè)f是網(wǎng)絡(luò)N一個(gè)可行流，對(duì)于N中每條路P，在其上定義一個(gè)非負(fù)函數(shù)：若δ(P)=0,則稱路P是f飽和；δ(P)>0,則稱路P是f非飽和，稱P為可增路（增廣路）

第63頁(yè)最大流基本定理網(wǎng)絡(luò)中f可增路P存在意味著f不是最大流?？裳刂鳳增加一個(gè)值為δ(P)附加流量，得到由

所定義新可行流f’，val(f’)=val(f)+