物流運(yùn)籌學(xué) 課件 第9章 物流路徑

Chapter9圖與網(wǎng)絡(luò)分析

(GraphTheoryandNetworkAnalysis)圖的基本概念與模型最短路問題網(wǎng)絡(luò)的最大流本章主要內(nèi)容：近代圖論的歷史可追溯到18世紀(jì)的七橋問題—穿過K?nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。圖的基本概念與模型K?nigsberg橋?qū)?yīng)的圖圖的基本概念與模型圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。圖的定義： 若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖G可以定義為點(diǎn)和邊的集合，記作：其中:V——點(diǎn)集E——邊集※

圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。圖的基本概念與模型(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示。圖的基本概念與模型定義:圖中的點(diǎn)用v表示，邊用e表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5

端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。圖的基本概念與模型

環(huán),多重邊,簡單圖如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間的邊多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無環(huán)、無多重邊的圖稱作簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的基本概念與模型

次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:

一個(gè)圖的次等于各點(diǎn)的次之和。圖的基本概念與模型

網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖G＝（V，E），對(duì)G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過能力(容量)等等。端點(diǎn)無序的賦權(quán)圖稱為無向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256圖的基本概念與模型

出次與入次

有向圖中，以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用d+(vi)表示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用表示d-(vi)；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次?！邢驁D中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。最短路問題問題描述： 就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路.

有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。這是解決網(wǎng)絡(luò)中某一點(diǎn)到其它點(diǎn)的最短路問題時(shí)目前認(rèn)為的最好方法。它的基本思想是：若某條線路是最短線路，則從這條線路的起點(diǎn)到該線路上的任何一個(gè)中間點(diǎn)的線路也必是最短線路。在這個(gè)問題中我們討論的是從網(wǎng)絡(luò)中的點(diǎn)1到其它各點(diǎn)的最短路。最短路問題Dijkstra標(biāo)號(hào)法：求網(wǎng)絡(luò)上的一點(diǎn)到其它點(diǎn)的最短路

狄克斯屈(Dijkstra)標(biāo)號(hào)算法的基本思路：若序列{vs,v1…..vn-1,vn}是從vs到vt間的最短路，則序列{vs,v1…..vn-1}必為從vs

到vn-1的最短路。

假定v1→v2→v3→v4是v1→v4的最短路，則v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5最短路問題計(jì)算方法①從點(diǎn)1出發(fā)，因L(1,1)=0，在點(diǎn)1處標(biāo)記②從點(diǎn)1出發(fā)，找相鄰點(diǎn)r使得邊L(1,r)權(quán)數(shù)（距離）最小，若L(1,r)

=

L(1,1)+d(1,r)

將標(biāo)于點(diǎn)r處。并將邊1r變紅。0L(1,r)③從已標(biāo)號(hào)的點(diǎn)出發(fā)，找與這些相鄰點(diǎn)最小權(quán)數(shù)（距離）者，若L(1,p)

=Min{L(1,r)+d(r,p)}，這里r為已標(biāo)號(hào)者下標(biāo)，p為未標(biāo)號(hào)下標(biāo)，則將標(biāo)于p處。并把(r,p)邊變紅。④重復(fù)上述步驟，直至全部的點(diǎn)都標(biāo)完。L(1,p)51275634255273135710①從點(diǎn)1出發(fā)，因L11=0，在點(diǎn)1處標(biāo)記

5127563425527313571051275634255273135710

從已標(biāo)號(hào)的點(diǎn)出發(fā)，找與這些相鄰點(diǎn)最小權(quán)數(shù)（距離）者，找到之后：標(biāo)號(hào)；邊變紅。51275634255273135710251275634255273135710③從已標(biāo)號(hào)的點(diǎn)出發(fā)，若L(1,p)

=Min{L(1,r)+d(r,p)}，這里r為已標(biāo)號(hào)者下標(biāo)，p為未標(biāo)號(hào)下標(biāo)，則將標(biāo)于p處。并把(r,p)邊變紅。251275634255273135710③從已標(biāo)號(hào)的點(diǎn)出發(fā)，若L(1,p)

=Min{L(1,r)+d(r,p)}，這里r為已標(biāo)號(hào)者下標(biāo)，p為未標(biāo)號(hào)下標(biāo)，則將標(biāo)于p處。并把(r,p)邊變紅。2351275634255273135710④重復(fù)上述步驟，直至全部的點(diǎn)都標(biāo)完。2351275634255273135710④重復(fù)上述步驟，直至全部的點(diǎn)都標(biāo)完。23451275634255273135710④重復(fù)上述步驟，直至全部的點(diǎn)都標(biāo)完。23451275634255273135710④重復(fù)上述步驟，直至全部的點(diǎn)都標(biāo)完。234751275634255273135710234751275634255273135710234785127563425527313571023478512756342552731357102347813512756342552731357102347813對(duì)有向圖同樣可以用標(biāo)號(hào)算法：例如圖，有一批貨物要從v1運(yùn)到v9，弧旁數(shù)字表示該段路長，求最短運(yùn)輸路線。v1v9v8v7v6v5v4v3v23333342.55222140最短路問題v1v9v8v7v6v5v4v3v23333342.552221403v1v9v8v7v6v5v4v3v23333342.552221403v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v23333342.55222140346756v1v9v8v7v6v5v4v3v23333342.552221403467568.5v1v9v8v7v6v5v4v3v23333342.552221403467568.59v1v9v8v7v6v5v4v3v23333342.552221403467568.59最短路問題Dijkstra標(biāo)號(hào)法僅僅適用于線路的權(quán)數(shù)的情況，對(duì)于<0時(shí)就要使用Floyd標(biāo)號(hào)法進(jìn)行求解，二者的標(biāo)號(hào)過程基本相同例

如右圖所示中按dijkstra算法可得P(v1)=5為從vs→v1的最短路長顯然是錯(cuò)誤的，從vs→v2→v1路長只有3。v2vsv15-58最短路問題最短路問題的應(yīng)用：例9-2電信公司準(zhǔn)備準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。v1（甲地）1517624431065v2v7(乙地)v3v4v5v6解：這是一個(gè)求無向圖的最短路的問題。最短路問題例9-3設(shè)備更新問題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價(jià)格表年份12345年初價(jià)格1111121213最短路問題設(shè)備維修費(fèi)如下表使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用5681118解：將問題轉(zhuǎn)化為最短路問題，如下圖：用vi表示“第i年年初購進(jìn)一臺(tái)新設(shè)備”,?。╲i,vj）表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6最短路問題把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723v1v2v3v4v5v6162230415916223041312317181723v1v2v3v4v5v6161617171859223041223041233123v1v2v3v4v5v616161717185922304122304123312301622304153

最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條：v1→v3→v6和v1→v4→v6例一、從A

地到D

地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114最短路徑問題(多階段動(dòng)態(tài)決策法）AB1B2C1C2C3D24333321114DC1C2C3AB1B2C1C2C3D24333321114DC1C2C3B1B2AB1B2C1C2C3D24333321114DC1C2C3B1B2AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D

路長為6練習(xí)1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18求從A到G的最短路徑3求從A到E的最短路徑路線為A→B2→C1→D1→E

，最短路徑為19AB2B1B3C1C3D1D2EC25214112610104312111396581052練習(xí)2：1網(wǎng)絡(luò)的最大流如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問題。網(wǎng)絡(luò)的最大流基本概念：1.容量網(wǎng)絡(luò)：對(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)(也稱源點(diǎn)，記為s)和一個(gè)收點(diǎn)(也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為中間點(diǎn)。s①②③④t4844122679網(wǎng)絡(luò)的最大流2.網(wǎng)絡(luò)的最大流

是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量。3.流與可行流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧(vi,vj)上的負(fù)載量記為fij。若fij=0，稱為零流。滿足以下條件的一組流稱為可行流。

容量限制條件：容量網(wǎng)絡(luò)上所有的弧滿足：0≤fij≤cij

中間點(diǎn)流量守恒條件：

若以v(f)表示網(wǎng)絡(luò)中從s→t的流量，則有：網(wǎng)絡(luò)的最大流結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流也是可行流）網(wǎng)絡(luò)最大流問題： 指滿足容量限制條件和中間點(diǎn)平衡的條件下，使v(f)值達(dá)到最大。網(wǎng)絡(luò)的最大流

割與割集割是指把容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使s→t的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用表示。如下圖中，AA′將網(wǎng)絡(luò)上的點(diǎn)分割成兩個(gè)集合。并有，稱弧的集合{(v1,v3),(v2,v4)}是一個(gè)割，且的容量為18。網(wǎng)絡(luò)的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AA’BB’v1v3v4v2v5vtvsww624374317988V=(vs,v3)=(v1,v2,v4,v5,vt)為G的割集割集E'的容量=14v1v3v4v2v5vtvsww624374317988其中V=(vs,v1,v3,v4)=(v2,v5,vt)為G的割集(v1,v2),(v3,v4),(v3,v6)的容量和為割集E'的容量=13網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流其中割集容量最小的稱為網(wǎng)絡(luò)G的最小割集容量(最小割)定理1：（流量—割集定理）設(shè)f為網(wǎng)絡(luò)G=（V,E,C）的任一可行流，S是任一割集，則有W(f)≤定理2：(最大流-最小割定理)任一個(gè)網(wǎng)絡(luò)G中，從vi到vj的最大流的流量等于分離vi，vj的最小割的容量網(wǎng)絡(luò)的最大流增廣鏈 在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所有指向?yàn)閟→t的弧，稱為前向弧，記作P+,存在f<c；所有指向?yàn)閠→s的弧，稱為后向弧，記做P－，若f>0，則稱這樣的鏈為增廣鏈。例如下圖中，s→v2→v1→v3→v4→t。定理3

網(wǎng)絡(luò)G中的流f

是最大流當(dāng)且僅當(dāng)G中不包含任何增廣鏈網(wǎng)絡(luò)的最大流●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)網(wǎng)絡(luò)的最大流求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法：[基本思想]

由一個(gè)流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個(gè)增流過程，直至不存在增廣鏈。[基本方法]找出第一個(gè)可行流，（例如所有弧的流量fij=0。）用標(biāo)號(hào)的方法找一條增廣鏈

首先給發(fā)點(diǎn)s標(biāo)號(hào)(∞),標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。選擇一個(gè)點(diǎn)vi已標(biāo)號(hào)

并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查：網(wǎng)絡(luò)的最大流

如果弧的起點(diǎn)為vi，并且有fij<Cij，則給vj標(biāo)號(hào)為(Cij－fij)

如果弧的方向指向vi，并且有fji>0，則vj標(biāo)號(hào)(fji)(3)重復(fù)第(2)步，可能出現(xiàn)兩種結(jié)局：

標(biāo)號(hào)過程中斷，t無法標(biāo)號(hào)，說明網(wǎng)絡(luò)中不存在增廣鏈，目前流量為最大流。同時(shí)可以確定最小割集，記已標(biāo)號(hào)的點(diǎn)集為V,未標(biāo)號(hào)的點(diǎn)集合為V′,(V,V′)為網(wǎng)絡(luò)的最小割。

t得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從s到t得由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第(4)步網(wǎng)絡(luò)的最大流(4)修改流量。設(shè)原圖可行流為f，令得到網(wǎng)絡(luò)上一個(gè)新的可行流f’。(5)擦除圖上所有標(biāo)號(hào)，重復(fù)(1)-(4)步，直到圖中找不到任何增廣鏈，計(jì)算結(jié)束。網(wǎng)絡(luò)的最大流例用標(biāo)號(hào)算法求下圖中s→t的最大流量，并找出最小割?！駍tv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)網(wǎng)絡(luò)的最大流解：(1)先給s標(biāo)號(hào)(∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(∞)網(wǎng)絡(luò)的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)(2)檢查與s點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因fs1<cs1，故對(duì)v1標(biāo)號(hào)=min{∞,cs1-fs1}=1,(1)網(wǎng)絡(luò)的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(6)(∞)(1)(2)檢查與v1點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f13<c13，故對(duì)v3標(biāo)號(hào)=min{1,c13-f13}=min{1,6}=1(1)網(wǎng)絡(luò)的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(1)(1)(3)檢查與v3點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f3t<c3t，故對(duì)vt標(biāo)號(hào)=min{1,c3t-f3t}=min{1,1}=1(1)找到一條增廣鏈s→v1→v3→t網(wǎng)絡(luò)的最大流(4)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?！駍tv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)網(wǎng)絡(luò)的最大流(5)擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。●stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)網(wǎng)絡(luò)的最大流(5)擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(2)ε(2)=min{∞,2}=2(2)ε(1)=min{2,3}=2ε(3)=min{2,5}=2(2)(1)ε(4)=min{2,1}=1(1)ε(t)=min{1,2}=1網(wǎng)絡(luò)的最大流(6)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?！駍tv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(2)(2)(2)(1)(1)網(wǎng)絡(luò)的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(∞)(2)(2)(2)(1)(1)(7)擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。網(wǎng)絡(luò)的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(∞)(1)(1)(1)(7)擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過程，尋找另外的增廣鏈。ε(2)=min{∞,1}=1ε(1)=min{1,2}=1ε(3)=min{1,4}=1網(wǎng)絡(luò)的最大流例求下圖s→t的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●解:(1)在已知可行流的基礎(chǔ)上，通過標(biāo)號(hào)尋找增廣鏈。(∞)ε(2)=min{∞,6}=6(6)ε(3)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增廣鏈s→v2→v3→t網(wǎng)絡(luò)的最大流(2)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●(∞)(6)(2)(2)網(wǎng)絡(luò)的最大流(3)擦除原標(biāo)號(hào)，重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(6)(2)(2)網(wǎng)絡(luò)的最大流(4)重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)ε(2)=min{∞,4}=4(4)(1)ε(5)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增廣鏈：s→v2→v5→v3→t網(wǎng)絡(luò)的最大流(5)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(4)(1)(1)(1)網(wǎng)絡(luò)的最大流(6)擦除原標(biāo)號(hào)stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(4)(1)(1)(1)網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)ε(5)=min{∞,1}=1ε(3)=min{1,1}=1ε(t)=min{1,2}=1(7)重新搜尋增廣鏈。存在增廣鏈：s→v5→v3→t網(wǎng)絡(luò)的最大流(8)調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(9)擦除原標(biāo)號(hào)網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(10)重新標(biāo)號(hào)，搜索增廣鏈(∞)ε(1)=min{∞,1}=1(1)ε(5)=min{1,1}=1(1)ε(4)=min{1,1}=1(1)ε(t)=min{1,1}=1(1)存在增廣鏈：s→v1→v5→v4→t網(wǎng)絡(luò)的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(1)(11)調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流網(wǎng)絡(luò)的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(1)(1)(1)(1)(11)擦除標(biāo)號(hào)，在新的可行流上重新標(biāo)號(hào)。網(wǎng)絡(luò)的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(11)擦除標(biāo)號(hào)，在新的可行流上重新標(biāo)號(hào)。(3)ε(2)=min{∞,3}=1無法標(biāo)號(hào)，不存在增廣鏈，此可行流已為最大流。最大流量為14。vsv2v3v1v4v5vtv6(5,0)(3,0)(4,0)(3,0)(2,0)(5,0)(3,0)(4,0)(5,0)(3,0)(2,0)ffvsv2v3v1v4v5vtv6(5,0)(3,0)(4,0)(3,0)(2,0)(5,0)(3,0)(4,0)(5,0)(3,0)(2,0)ff解：從零流開始，尋找增廣鏈vs→v1→v4→vt

最小容量min{5，5，4}=4(5,4)(5,4)(4,4)vs→v1→v5→vt

最小容量min{1，3，3}=1(5,5)(3,1)(3,1)vs→v2→v5→vt

最小容量min{4，3，2}=2(4,2)(3,2)(3,3)vs→v2→v6→vt

最小容量min{2，2，5}=2(4,4)(2,2)(5,2)vs→v3→v6→vt

最小容量min{3，2，3}=2(3,2)(2,2)(5,4)∴網(wǎng)絡(luò)最大流量=11，流量安排如上圖vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)從任一可行流開始尋找最大流，采用標(biāo)號(hào)法尋找增廣鏈(

,+∞)解：先給發(fā)點(diǎn)標(biāo)號(hào)，即：vs標(biāo)（

，+∞

）(vs，v1)fs1=cs1=5(vs，v2)

fs2=2<cs2=4δs2=2

所以給v2標(biāo)號(hào)(+vs，2)(vs，v3)

fs3=2<cs3=3δs3=1

所以給v3標(biāo)號(hào)(+vs，1)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(

,+∞)(+vs,2)(+vs,1)(v2，v5)f25=0<c25=3δ25=min[3,2]

所以給v5標(biāo)號(hào)(+v2，2)(v2，v6)

f26=2=c26(v3，v6)

f36=2=c36vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(

,+∞)(+vs,2)(+vs,1)(+v2,2)(v5，vt)f5t=3=c5t(v5，v1)

f15=3>0δ51=min[3,2]=2

所以給v1標(biāo)號(hào)(-v5，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(

,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(v1，v4)f14=2<c24=5δ51=min[3,2]=2

所以給v2標(biāo)號(hào)(+v1，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(

,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(v4，vt)f4t=2<c4t=4δ4t=min[2,2]=2

所以給vt標(biāo)號(hào)(+v4，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(

,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)存在一條從vs到vt的可增廣鏈δ=2調(diào)整流量vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(

,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)(4,4)(3,2)(3,1)(5,4)(4,4)(vs，v1)fs1=cs1=5(vs，v2)

fs2=4=cs2=4(vs，v3)

fs3=2<cs3=3δs3=1

所以給v3標(biāo)號(hào)(+vs，1)vsv2v3v1v4v5vtv6(5,5)