第七章圖與網(wǎng)絡(luò)理論1第1頁，課件共84頁，創(chuàng)作于2023年2月第一節(jié)圖的基本概念所謂圖，就是頂點和邊的集合，點的集合記為V={v1,v2…,

vn}，邊的集合記為E={e1,e2…,

em}，vi稱為圖的頂點，ej稱為圖的邊，若邊ej聯(lián)結(jié)vs和vt，則記為(vs,vt)，即ej=(vs,vt)。

則圖可以表示為：G=(V,E)，點代表被研究的事物，邊代表事物之間的聯(lián)系，因此，邊不能離開點而獨立存在，每條邊都有兩個端點。在畫圖時，頂點的位置、邊和長短形狀都是無關(guān)緊要的，只要兩個圖的頂點及邊是對應(yīng)相同的，則兩個圖相同。2第2頁，課件共84頁，創(chuàng)作于2023年2月有些圖的邊帶有方向，這樣的圖稱為有向圖。而邊不帶方向的圖稱為無向圖。圖7.7是一個無向圖。圖7.8是一個有向圖。v1v5v2v3v4e1e2e3e4e6e5e7圖7.7圖7.83第3頁，課件共84頁，創(chuàng)作于2023年2月在一個圖中，若e=(u,v)，則稱u,v是邊e的端點．并u,v稱相鄰．稱e是點u（v及點）的關(guān)聯(lián)邊。若邊ei,ej有一個公共的端點u，稱邊ei,ej相鄰。若邊e的兩個端點是同一頂點，則稱此邊為環(huán)。若兩頂點之間有多于一條的邊，則這些邊稱為多重邊。如圖7.7中，e7是環(huán)，e1,e2是多重邊。一個不含環(huán)和多重邊的圖稱為簡單圖。含有多重邊的圖稱為多重圖。我們這里所說的圖，如不特別指明，都是簡單圖。4第4頁，課件共84頁，創(chuàng)作于2023年2月以點v為端點的邊的條數(shù)稱為點v的度，記作d(v),如圖7.7中d(v1)=3,d(v3)=1。度為零的點稱為弧立點，度為1的點稱為懸掛點。懸掛點的邊稱為懸掛邊。度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。不難證明：在一個圖中，頂點度數(shù)的總和等于邊數(shù)的２倍，奇頂點的個數(shù)必為偶數(shù)。

鏈：由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列;如:v0

,e1,v1,e2,v2

,e3,v3

,…,vn-1,en

,vn;

v0,vn分別為鏈的起點和終點；

簡單鏈：鏈中所含的邊均不相同；

初等鏈：鏈中所含的點均不相同；圈：在鏈中，若v0=vn則稱該鏈為圈；連通圖：圖中任意兩點之間均至少有一條鏈相連

，5第5頁，課件共84頁，創(chuàng)作于2023年2月第二節(jié)樹樹是一類結(jié)構(gòu)簡單而又十分有用的圖。一個不含圈的連通圖稱為樹。設(shè)圖T=(V,E)，含有n個頂點，則下列命題是等價的。（1）T是樹。（2）T的任意兩頂點之間，有唯一的鏈相連。（3）T連通且有n－1條邊。（4）T無圈且有n－1條邊。（5）T無圈但添加一條邊得唯一一圈。（6）T連通但去掉一條邊則不連通。6第6頁，課件共84頁，創(chuàng)作于2023年2月給定圖G=(V,E)，若V’

V,E’

E，并且E’中的邊的端點都屬于V’

，則稱G’=(V’,E’)是G的一個子圖。特別地，若V’

=

V，則稱G’為G的支撐子圖。設(shè)T是圖G的一個支撐子圖，若T是一樹，則稱T是G的一個支撐樹。給定圖G=(V,E),對于G的每一條邊，可賦以一個實數(shù)w(e)，稱為邊e的權(quán)，圖G連同它邊上的權(quán)稱為賦權(quán)圖。賦權(quán)圖在圖論的應(yīng)用中經(jīng)常出現(xiàn)。根據(jù)實際問題的需要，權(quán)可以有不同的實際含義，它可以表示距離、流量、時間、費用等。7第7頁，課件共84頁，創(chuàng)作于2023年2月給定圖G=(V,E),設(shè)T=(V,E’)是G的一個支撐樹，定義樹T的權(quán)為即支撐樹T上所有邊的權(quán)的總和。圖G的最小支撐樹就是圖G中權(quán)最小的支撐樹。求圖G的最小支撐樹的方法是建立在求圖G的支撐樹基礎(chǔ)上，只需在求圖G的支撐樹的算法再加適當限制。因此，求最小支撐樹方法也有相應(yīng)的破圈法；避圈法。

8第8頁，課件共84頁，創(chuàng)作于2023年2月例2分別用破圈法，避圈法求圖7.17的最小支撐樹。圖7.17v1v5v2v3v42v6v7v834346236645859第9頁，課件共84頁，創(chuàng)作于2023年2月v1v5v2v3v42v6v7v83434623664585解破圈法10第10頁，課件共84頁，創(chuàng)作于2023年2月v1v5v2v3v42v6v7v83434623664585避圈法：11第11頁，課件共84頁，創(chuàng)作于2023年2月第三節(jié)最短路問題最短路問題，一般來說就是從給定的賦權(quán)圖中，尋找兩點之間權(quán)最小的鏈（鏈的權(quán)即鏈中所有邊的權(quán)之和）。許多優(yōu)化問題都需要求圖的最短路，如選址、管道鋪設(shè)、設(shè)備更新、整數(shù)規(guī)劃等問題。由于所求問題不同，需要使用不同的方法。下面我們介紹常用的算法。一、Dijkstra算法Dijkstra算法是求賦權(quán)有向圖中，某兩點之間最短路的算法。實際上，它可以求某一點到其它各點的最短路。它是Dijkstra于1959年提出。目前被認為是求非負權(quán)最短路的最好的算法。12第12頁，課件共84頁，創(chuàng)作于2023年2月Dijkstra算法的基本思想是基于以下原理：若vs,vl,…,vj是vs到vj的最短路，vi是此路中某一點，則vs,vl,…,vi必是從vs到vi的最短路。此算法的基本步驟是采用標號法，給圖G每一個頂點一個標號。標號分兩種：一種是T標號，一種是P標號。T標號也稱臨時標號，它表示從vs到這一點的最短路長度的一個上界，P標號也稱固定標號，它表示從vs到這一點的最短路的長度（這里最短路長度是指這條路上個邊權(quán)的和）。算法每一步都把某點的T標號改變?yōu)镻標號。當終點得到P標號，算法結(jié)束。若要求某點到其它各點的最短路，則最多經(jīng)過n-1步算法結(jié)束。13第13頁，課件共84頁，創(chuàng)作于2023年2月設(shè)lij表示邊(vi,vj)的權(quán)，則Dijkstra算法步驟如下：（1）給始點以P標號P（0,0），給其它各點vj以T標號T(dj,v1)，其中，dj=l1j，（若vj與v1不相鄰，則令l1j=+∞）。（2）在所有T標號點中，若vk的T標號最小，則把vk的T標號改為P標號。若最小的T標號不止一個，則可任取一個改為P標號。（3）修改所有T標號T(dj,vt)；dj=min{dj,dk+lkj},若dk+lkj<djvt=vk否則不變。（4）當終點或全部頂點都得到P標號，算法結(jié)束，否則返回（2）。14第14頁，課件共84頁，創(chuàng)作于2023年2月例3求圖7.20中，v1到v8的最短路。圖7.20v4v2v1v3v6v5v7v8983834256767109415第15頁，課件共84頁，創(chuàng)作于2023年2月圖7.20v4v2v1v3v6v5v7v89838342567671094解

P(0,0)T(9,v1)T(3,v1)T(8,v1)16第16頁，課件共84頁，創(chuàng)作于2023年2月圖7.20v4v2v1v3v6v5v7v89838342567671094解

P(0,0)T(9,v1)T(7,v3)T(3,v1)T(8,v1)P(3,v1)17第17頁，課件共84頁，創(chuàng)作于2023年2月圖7.20v4v2v1v3v6v5v7v89838342567671094解

P(0,0)T(9,v1)T(7,v3)T(8,v1)P(3,v1)P(7,v3)T(14,v6)T(16,v6)18第18頁，課件共84頁，創(chuàng)作于2023年2月圖7.20v4v2v1v3v6v5v7v89838342567671094解

P(0,0)T(9,v1)T(8,v1)P(3,v1)P(7,v3)T(14,v6)P(9,v1)P(8,v1)T(17,v2)T(16,v6)19第19頁，課件共84頁，創(chuàng)作于2023年2月圖7.20v4v2v1v3v6v5v7v89838342567671094解

P(0,0)P(3,v1)P(17,v2)P(7,v3)T(14,v6)P(9,v1)P(8,v1)T(17,v2)T(16,v6)P(14,v6)P(16,v6)20第20頁，課件共84頁，創(chuàng)作于2023年2月圖7.20v4v2v1v3v6v5v7v89838342567671094解

P(0,0)P(3,v1)P(17,v2)P(7,v3)P(9,v1)P(8,v1)P(14,v6)P(16,v6)21第21頁，課件共84頁，創(chuàng)作于2023年2月例4求圖7.22中，v1到其它各點的最短路。圖7.22v4v2v1v3v6v5v7v8354263441517498Dijkstra算法同樣可用于求無向圖的最短路。22第22頁，課件共84頁，創(chuàng)作于2023年2月圖7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)T(3,v1)T(4,v1)T(2,v1)23第23頁，課件共84頁，創(chuàng)作于2023年2月圖7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)T(3,v1)T(4,v1)T(2,v1)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)24第24頁，課件共84頁，創(chuàng)作于2023年2月圖7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)P(3,v4)T(6,v3)25第25頁，課件共84頁，創(chuàng)作于2023年2月圖7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)P(2,v1)T(7,v4)P(3,v1)T(8,v2)P(3,v4)T(6,v3)P(6,v3)T(7,v6)T(15,v6)26第26頁，課件共84頁，創(chuàng)作于2023年2月圖7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)P(2,v1)T(7,v4)P(3,v1)P(3,v4)P(6,v3)T(7,v6)P(7,v6)T(15,v6)T(11,v5)P(7,v4)27第27頁，課件共84頁，創(chuàng)作于2023年2月圖7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)P(2,v1)P(3,v1)P(3,v4)P(6,v3)P(7,v6)T(11,v5)P(7,v4)P(11,v5)28第28頁，課件共84頁，創(chuàng)作于2023年2月圖7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)P(2,v1)P(3,v1)P(3,v4)P(6,v3)P(7,v6)P(7,v4)P(11,v5)29第29頁，課件共84頁，創(chuàng)作于2023年2月二、逐次逼近法前面介紹的Dijkstra算法，只適用于權(quán)為非負的賦權(quán)圖中求最短路問題。逐次逼近法可用于存在負權(quán)，但無負有向回路的賦權(quán)圖的最短路問題。因為，如果dj是從v1到vj的最短路的長度，而這從條最短路的最后一條邊為(vk,vj)，則從v1到vj的最短路中，從v1到vk這一段，必然也是從v1到vk的最短路。若其長度記為dk，lkj表示邊(vk,vj)的權(quán)，那么dj，dk和lkj應(yīng)滿足下列方程：30第30頁，課件共84頁，創(chuàng)作于2023年2月逐次逼近法就是用迭代方法解這個方程。第一次逼近是找點v1到點vj由一條邊所組成的最短路，其長記為dj(1)；第二次逼近是求從v1到點vj不多于兩條邊組成的最短路，其長記為dj(2)；以此類推，第m次逼近是求從v1到vj不多于m條邊組成的最短路，其長記為dj(m)。因為圖中，不含負有向回路，所以從v1到vj的最短路上最多有n-1條邊。從而可知，最多做n-1次逼近就可求出從v1到vj的最短路。

31第31頁，課件共84頁，創(chuàng)作于2023年2月逐次逼近法步驟如下：(1)首先令dj(1)=l1j(j=1,2,…,n)，若v1與vj之間無邊時，lij=+∞，而ljj=0；(3)若對所有的j，有dj(m)=dj(m-1)，則計算結(jié)束，dj(m)(j=1,2,…,n)即為v1到其它各點的最短路的長度，否則返回（2）。32第32頁，課件共84頁，創(chuàng)作于2023年2月例4求下圖中，v1到其它各點的最短路。v1139538362v6v5v3v4v233第33頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞34第34頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞035第35頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0236第36頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0225②37第37頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0225②10②38第38頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0225②10②9③39第39頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞40第40頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞025108③10⑤41第41頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞025108③10⑤025108③9⑤42第42頁，課件共84頁，創(chuàng)作于2023年2月v1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞025108③10⑤025108③9⑤025108943第43頁，課件共84頁，創(chuàng)作于2023年2月例5求圖7.24中，v1到其它各點的最短路。圖7.24v1v2v3v4v5v6v7v834-14-22545-3-2-435444第44頁，課件共84頁，創(chuàng)作于2023年2月jilijdj(1)dj(2)dj(3)dj(4)dj(5)dj(6)v1v2v3v4v5v6v7v8v1034000000v20-1-24333333v305422222v4204511111v50-2375555v6045333v7-3-40597777v801087745第45頁，課件共84頁，創(chuàng)作于2023年2月第四節(jié)最大流問題給定一個有向圖G=(V,E)，每條邊(vi,vj)給定一個非負數(shù)cij稱為邊(vi,vj)容量。假設(shè)G中只有一個入度為零的點vs稱為發(fā)點，只有一個出度為零的點vt稱為收點，其余點稱為中間點，這樣的有向圖稱為容量網(wǎng)絡(luò)，記為G=(V,E,C)。46第46頁，課件共84頁，創(chuàng)作于2023年2月例如圖7.25就是一個容量網(wǎng)絡(luò)。如果vs表示油田，vt表示煉油廠，圖7.25表示從油田到煉油廠的輸油管道網(wǎng)。邊上的數(shù)字表示該管道的最大輸油能力，中間點表示輸油泵站。現(xiàn)在要問如何安排各管道輸油量，才能使從vs到vt輸油量最大？這就是本節(jié)所要介紹的最大流問題。

圖7.25v1v2v3v4vsvt54142537847第47頁，課件共84頁，創(chuàng)作于2023年2月一、基本概念給定一個容量網(wǎng)絡(luò)G=(V,E,C)，所謂網(wǎng)絡(luò)G上的流，是指每條邊(vi,vj)上確定的一個數(shù)f(vi,vj)，簡記為fij，稱集合f={fij}為網(wǎng)絡(luò)G上的一個流。如果網(wǎng)絡(luò)G表示一個輸油管道網(wǎng)，則cij表示管道輸油能力，而fij表示管道當前的實際流量，因此應(yīng)有0

fij

cij，即管道中的流量不能超過該管道的最大通過能力（即管道的容量）。對網(wǎng)絡(luò)G上的中間點表示一個轉(zhuǎn)送泵站，因此對中間點運出的總量與運進的總量應(yīng)當相等。而對于發(fā)點的凈流出量和收點的凈流入量必相等，并且就是該運輸方案的總輸送量。48第48頁，課件共84頁，創(chuàng)作于2023年2月容量網(wǎng)絡(luò)G=(V,E,C)中的一個流f={fij}滿足下列條件，稱f為可行流。（1）容量限制條件：對G中每條邊(vi,vj)，有0

fij

cij。（2）平衡條件：對于中間點vi，有（即流出量＝流入量）。對于收點vt與發(fā)點vs，有（即從vs的凈輸出量與vt的凈輸入量相等）。W稱為可行流f的流量。可行流總是存在的，當所有邊的流量fij=0時，就得到一個可行流，它的流量W=0。最大流問題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。49第49頁，課件共84頁，創(chuàng)作于2023年2月對于容量網(wǎng)絡(luò)G給定一個可行流f={fij}，當fij=cij時，稱邊(vi,vj)為飽和邊，當fij<cij時，稱邊(vi,vj)為非飽和邊，當fij=0時，稱邊(vi,vj)為零流邊，當fij>0時，稱邊(vi,vj)為非零流邊。設(shè)μ是網(wǎng)絡(luò)G中一條聯(lián)結(jié)發(fā)點vs和收點vt的鏈。我們規(guī)定μ的正方向從vs到vt，則鏈μ上的邊被分為兩類：一類是邊的方向與鏈的正方向一致，稱它們?yōu)榍跋蜻?，μ上上前向邊的全體記為μ+。另一類邊與鏈的正方向相反，稱它們?yōu)楹笙蜻叄躺虾笙蜻叺娜w記為μ-。50第50頁，課件共84頁，創(chuàng)作于2023年2月v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)圖7.26例如，在圖7.26中，其邊上的兩個數(shù)字分別表示邊的容量和流量，即(cij,fij)。(v2,v5)為飽和邊，(vs,v1)為非飽和邊，并且(v2,v5)，(vs,v1)均為非零流邊，(v3,v5)是零流邊。51第51頁，課件共84頁，創(chuàng)作于2023年2月例如圖7.26中，在聯(lián)結(jié)vs和vt的鏈μ={vs,v1,v2

,v5,vt}中，(vs,v1)，(v2,v5)，(v5,vt)為前向邊，(v1,v2)為后向邊。即μ+={(vs,v1)，(v2,v5)，(v5,vt)}，μ-={(v1,v2)}。v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)圖7.2652第52頁，課件共84頁，創(chuàng)作于2023年2月設(shè)f是網(wǎng)絡(luò)G上的一個可行流，μ是從vs到vt的一條鏈，若對μ上的任意一條邊(vi,vj)有若(vi,vj)

μ+，則0fij<cij，即μ+中每一邊是非飽和邊。若(vi,vj)μ-，則0<fij

cij，即μ-中每一邊是非零流邊。則稱μ是一條增廣鏈。53第53頁，課件共84頁，創(chuàng)作于2023年2月例如圖7.26中，鏈μ={vs,v1,v2,v3,v5,vt}就是一條增廣鏈，因為μ+={(vs,v1)，(v2,v3)，(v3,v5)，(v5,vt)}中的邊均為非飽和邊，而μ-={(v1,v2)}中的邊為非零流邊。v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)圖7.2654第54頁，課件共84頁，創(chuàng)作于2023年2月對于給定的網(wǎng)絡(luò)G=(V,E,C)，設(shè)S,T

V，并且S

T=V，S

T=，vs

S，vt

T，以S中點為始點，以T中點為終點的邊的集合，稱為G的割集，記為(S,T)。割集(S,T)中所有邊的容量之和稱為割集(S,T)的容量，記為C(S,T)，即55第55頁，課件共84頁，創(chuàng)作于2023年2月例如圖7.26中,設(shè)S1={vs}，T

1={v1,v2,v3,v4,v5,vt}，則(S1,T1)={(vs,v1)，(vs,v2)}，其容量為C(S1,T1)=22。設(shè)S2={vs,v1}，T

2={v2,v3,v4,v5,vt}則(S2,T2)={(vs,v2)，(v1,v4)}，其容量為C(S2,T2)=20。v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)圖7.2656第56頁，課件共84頁，創(chuàng)作于2023年2月如果從網(wǎng)絡(luò)G中去掉割集(S,T)中的邊，從vs就沒有路可以到達vt。對于網(wǎng)絡(luò)G，它有許多割集，我們可以找到容量最小割集。而網(wǎng)絡(luò)G的最大流量一定不會超過容量最小割集的容量，稱網(wǎng)絡(luò)G中容量最小的割集為G的最小割集。如果把網(wǎng)絡(luò)G看成各種粗細不同的管道網(wǎng)，而最小割集就相當于管道網(wǎng)中最細管道部分的總和。二、最大流最小割集定理由上面例子可知，如果找到網(wǎng)絡(luò)G的一個可行流，其流量等于網(wǎng)絡(luò)G的最小割集容量，則該可行流一定是最大流。下面最大流最小割集定理就是要說明這一點。57第57頁，課件共84頁，創(chuàng)作于2023年2月定理1可行流f*是最大流當且僅當G中不存在關(guān)于f*的增廣鏈。推論在任意一個容量網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。三、求最大流的標號算法由上面定理1可知可行流f是否是最大流，關(guān)鍵看網(wǎng)絡(luò)G中是否存在關(guān)于可行流f的增廣鏈，定理1的證明過程為我們提供了尋找增廣鏈的方法及改進可行流f的方法。如果在網(wǎng)絡(luò)G中存在關(guān)于可行流f的增廣鏈（從vs到vt），則可按定理1證明中所給的方法修改可行流f，得到一個新的可行流f‘，而f‘的流量大于f的流量。如果在G中不存在關(guān)于可行流f的增廣鏈，則可行流f就是最大流。尋找關(guān)于可行流f的增廣鏈可按下面介紹的標號法來實現(xiàn)。58第58頁，課件共84頁，創(chuàng)作于2023年2月求網(wǎng)絡(luò)G的最大流的標號法分為兩步，第1步是標號過程，通過標號尋找增廣鏈；第2步是調(diào)整過程，沿增廣鏈個性可行流f的流量。設(shè)f是網(wǎng)絡(luò)G上的可行流（初始可行流可取零流f={fij=0}）。1標號過程（1）首先給發(fā)點vs標號(0,+∞)。（2）選擇一個已標號的頂點vi，對所有與vi相鄰而沒有標號的頂點vj按下列規(guī)則處理。（a）若(vi,vj)

E，并且fij<cij，則給頂點vj以標號(i,δj)，其中δj=min{δi,cij-fij}。（b）若(vj,vi)E，并且fij>0，則給頂點vj以標號(i,δj)，其中δj=min{δi,cij-fji}。59第59頁，課件共84頁，創(chuàng)作于2023年2月重復(fù)過程（2），可能出現(xiàn)兩種結(jié)果，其一是終點vt得到標號，說明存在一條增廣鏈，則轉(zhuǎn)到調(diào)整過程，其二是終點vt不能獲得標號，說明不存在增廣鏈，這時可行流f即為最大流。2調(diào)整過程首先按終點vt及其它頂點的第一個標號，用反向追蹤法在網(wǎng)絡(luò)中找出增廣鏈。例如設(shè)終點vt的第一個標號為k，則(vk,vt)是增廣鏈上的邊，然后根據(jù)vk的第一個標號，找到下一個頂點，即若vk的第一個標號為j，則(vj,vk)（或者(vk,vj)）是增廣鏈上的邊，直到用此方法找到vs為止。這時就得到一條從vs到vt的增廣鏈μ。最后按下式修改可行流f。

60第60頁，課件共84頁，創(chuàng)作于2023年2月調(diào)整結(jié)束后，去掉所有標號，返回標號過程重新進行標號過程。令61第61頁，課件共84頁，創(chuàng)作于2023年2月例10用標號法求下圖中從vs到vt的最大流。

vsvt

v4

v2

v3

v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)62第62頁，課件共84頁，創(chuàng)作于2023年2月解（I）標號過程（1）首先給發(fā)點vs標以(0,+∞).

vsvt

v4

v2

v3

v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)63第63頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)（2）檢查與vs相鄰的頂點v1，v2，因為(vs,v1)

E，并且fs1=4<cs1=15，所以v1可以獲得標號(vs,δ1)，其中δ1=min{+∞,

15-4}=11。因為(vs,v2)E，但fs2=cs2，所以v2不能標號。(vs,11)64第64頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)（3）檢查與v1相鄰且沒有標號的頂點v2，v3，v4，因為(v2,v1)

E，并且f21>0，所以v2可以獲得標號(v1,δ2)，其中δ2=min{δ1,f21}=min{9,3}=3。因為(v1,v4)

E，并且f14=0<c14=4，所以v4可以獲得標號(v1,δ4)，其中δ4=min{9,

4-0}=4。因為(v1,v3)E，但f13=c13，所以v3不能標號。(vs,11)(v1,3)(v1,4)65第65頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)（4）檢查與v2相鄰且沒有標號的頂點v3，因為(v2,v3)

E，并且f23=1<c23=5，所以v3可以獲得標號(v2,δ3)，其中δ3

min{δ2,

c23-f23

}=min{3,5-1}=3

。(vs,11)(v1,3)(v1,4)(v2,3)66第66頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)（5）由于與v3相鄰且沒有標號的頂點為vt，并且vt也與已標號的頂點v4相鄰，所以vt既可以以v3為基礎(chǔ)獲得標號(v3,δt)，也可以以v4為基礎(chǔ)獲得標號(v4,δt’)。但為減少迭代次數(shù)，應(yīng)選擇δ1與δt’兩者較大的給vt標號。因為δt=min{δ3,c3t-f3t}=min{3,3}=3,δt’=min{δ4,c4t-f4t}=min{4,5}=4，所以vt的標號應(yīng)?。╲4,4）。(v4,4)67第67頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)(v4,4)（II）調(diào)整過程由于vt的第一個標號為v4，得到頂點v4，由v4的第一個標號為v1，得到頂點v1，由v1的第一個標號為vs，得到頂點vs，由此得到關(guān)于可行流f的增廣鏈μ={vs,v1,v4

,vt}，其中(vs,v1),(v1,v4),(v4,vt)為前向邊。68第68頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)(v4,4)（II）調(diào)整過程由于δt=4，所以調(diào)整量為4，即增廣鏈μ上的前向邊流量加4。69第69頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)重新開始標號過程，

（I）標號過程（1）首先給發(fā)點vs標以(0,+∞).

70第70頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,7)（2）檢查與vs相鄰的頂點v1，v2，因為(vs,v1)

E，并且fs1=8<cs1=15，所以v1可以獲得標號(vs,δ1)，其中δ1=min{+∞,

15-8}=7。因為(vs,v2)E，但fs2=cs2，所以v2不能標號。71第71頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,9)(v1,3)（3）檢查與v1相鄰且沒有標號的頂點v2，v3，v4，因為(v2,v1)

E，并且f21>0，所以v2可以獲得標號(v1,δ2)，其中δ2=min{δ1,f21}=min{9,3}=3。因為(v1,v3)E，但f13=c13，所以v3不能標號。因為(v1,v4)

E，并且f14=c14，所以v4不能標號。72第72頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,11)(v1,3)(v2,1)(v2,3)（5）檢查與v2相鄰且沒有標號的頂點v3，v4，因為(v2,v3)

E，并且f23=1<c23=5，所以v3可以獲得標號(v2,δ3)，其中δ3=min{δ2,

c23-f23}=min{3,4}=3。因為(v2,v4)

E，并且f24=5<c24=6，所以v4可以獲得標號(v2,δ4)，其中δ4

=min{δ2,

c23-f23}=min{3,

6-5}=1。73第73頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,7)(v1,3)(v2,1)(v2,3)(v3,3)（5）由于與v3相鄰且沒有標號的頂點為vt，并且vt也與已標號的頂點v4相鄰，所以vt既可以以v3為基礎(chǔ)獲得標號(v3,δt)，也可以以v4為基礎(chǔ)獲得標號(v4,δt’)。但為減少迭代次數(shù)，應(yīng)選擇δ1與δt’兩者較大的給vt標號。因為δt=min{δ3,c3t-f3t}=min{3,3}=3,δt’=min{δ4,c4t-f4t}=min{1,1}=1，所以vt的標號應(yīng)?。╲3,3）。74第74頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)(v4,4)75第75頁，課件共84頁，創(chuàng)作于2023年2月

vsvt

v4

v2

v3

v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,7)(v1,3)(v2,1)(v2,3)(v3,3)（II）調(diào)整過程由于vt的第一個標號為v3，得到頂點v3，由v3的第一個標號為v2，得到頂點v2，由v2的第一