第七章圖與網(wǎng)絡(luò)理論1第一頁(yè)，共八十四頁(yè)，2022年，8月28日第一節(jié)圖的基本概念所謂圖，就是頂點(diǎn)和邊的集合，點(diǎn)的集合記為V={v1,v2…,

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

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

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

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

,e1,v1,e2,v2

,e3,v3

,…,vn-1,en

,vn;

v0,vn分別為鏈的起點(diǎn)和終點(diǎn)；

簡(jiǎn)單鏈：鏈中所含的邊均不相同；

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

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

V,E’

E，并且E’中的邊的端點(diǎn)都屬于V’

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

=

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

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

P(0,0)T(9,v1)T(3,v1)T(8,v1)16第十六頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.20v4v2v1v3v6v5v7v89838342567671094解

P(0,0)T(9,v1)T(7,v3)T(3,v1)T(8,v1)P(3,v1)17第十七頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第十八頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第十九頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十一頁(yè)，共八十四頁(yè)，2022年，8月28日例4求圖7.22中，v1到其它各點(diǎn)的最短路。圖7.22v4v2v1v3v6v5v7v8354263441517498Dijkstra算法同樣可用于求無向圖的最短路。22第二十二頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.22v4v2v1v3v6v5v7v8354263441517498解

P(0,0)T(3,v1)T(4,v1)T(2,v1)23第二十三頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十四頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十五頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十六頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十七頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十八頁(yè)，共八十四頁(yè)，2022年，8月28日?qǐng)D7.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第二十九頁(yè)，共八十四頁(yè)，2022年，8月28日二、逐次逼近法前面介紹的Dijkstra算法，只適用于權(quán)為非負(fù)的賦權(quán)圖中求最短路問題。逐次逼近法可用于存在負(fù)權(quán)，但無負(fù)有向回路的賦權(quán)圖的最短路問題。因?yàn)?，如果dj是從v1到vj的最短路的長(zhǎng)度，而這從條最短路的最后一條邊為(vk,vj)，則從v1到vj的最短路中，從v1到vk這一段，必然也是從v1到vk的最短路。若其長(zhǎng)度記為dk，lkj表示邊(vk,vj)的權(quán)，那么dj，dk和lkj應(yīng)滿足下列方程：30第三十頁(yè)，共八十四頁(yè)，2022年，8月28日逐次逼近法就是用迭代方法解這個(gè)方程。第一次逼近是找點(diǎn)v1到點(diǎn)vj由一條邊所組成的最短路，其長(zhǎng)記為dj(1)；第二次逼近是求從v1到點(diǎn)vj不多于兩條邊組成的最短路，其長(zhǎng)記為dj(2)；以此類推，第m次逼近是求從v1到vj不多于m條邊組成的最短路，其長(zhǎng)記為dj(m)。因?yàn)閳D中，不含負(fù)有向回路，所以從v1到vj的最短路上最多有n-1條邊。從而可知，最多做n-1次逼近就可求出從v1到vj的最短路。

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

圖7.25v1v2v3v4vsvt54142537847第四十七頁(yè)，共八十四頁(yè)，2022年，8月28日一、基本概念給定一個(gè)容量網(wǎng)絡(luò)G=(V,E,C)，所謂網(wǎng)絡(luò)G上的流，是指每條邊(vi,vj)上確定的一個(gè)數(shù)f(vi,vj)，簡(jiǎn)記為fij，稱集合f={fij}為網(wǎng)絡(luò)G上的一個(gè)流。如果網(wǎng)絡(luò)G表示一個(gè)輸油管道網(wǎng)，則cij表示管道輸油能力，而fij表示管道當(dāng)前的實(shí)際流量，因此應(yīng)有0fijcij，即管道中的流量不能超過該管道的最大通過能力（即管道的容量）。對(duì)網(wǎng)絡(luò)G上的中間點(diǎn)表示一個(gè)轉(zhuǎn)送泵站，因此對(duì)中間點(diǎn)運(yùn)出的總量與運(yùn)進(jìn)的總量應(yīng)當(dāng)相等。而對(duì)于發(fā)點(diǎn)的凈流出量和收點(diǎn)的凈流入量必相等，并且就是該運(yùn)輸方案的總輸送量。48第四十八頁(yè)，共八十四頁(yè)，2022年，8月28日容量網(wǎng)絡(luò)G=(V,E,C)中的一個(gè)流f={fij}滿足下列條件，稱f為可行流。（1）容量限制條件：對(duì)G中每條邊(vi,vj)，有0fijcij。（2）平衡條件：對(duì)于中間點(diǎn)vi，有（即流出量＝流入量）。對(duì)于收點(diǎn)vt與發(fā)點(diǎn)vs，有（即從vs的凈輸出量與vt的凈輸入量相等）。W稱為可行流f的流量?？尚辛骺偸谴嬖诘模?dāng)所有邊的流量fij=0時(shí)，就得到一個(gè)可行流，它的流量W=0。最大流問題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。49第四十九頁(yè)，共八十四頁(yè)，2022年，8月28日對(duì)于容量網(wǎng)絡(luò)G給定一個(gè)可行流f={fij}，當(dāng)fij=cij時(shí)，稱邊(vi,vj)為飽和邊，當(dāng)fij<cij時(shí)，稱邊(vi,vj)為非飽和邊，當(dāng)fij=0時(shí)，稱邊(vi,vj)為零流邊，當(dāng)fij>0時(shí)，稱邊(vi,vj)為非零流邊。設(shè)μ是網(wǎng)絡(luò)G中一條聯(lián)結(jié)發(fā)點(diǎn)vs和收點(diǎn)vt的鏈。我們規(guī)定μ的正方向從vs到vt，則鏈μ上的邊被分為兩類：一類是邊的方向與鏈的正方向一致，稱它們?yōu)榍跋蜻?，μ上上前向邊的全體記為μ+。另一類邊與鏈的正方向相反，稱它們?yōu)楹笙蜻叄躺虾笙蜻叺娜w記為μ-。50第五十頁(yè)，共八十四頁(yè)，2022年，8月28日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中，其邊上的兩個(gè)數(shù)字分別表示邊的容量和流量，即(cij,fij)。(v2,v5)為飽和邊，(vs,v1)為非飽和邊，并且(v2,v5)，(vs,v1)均為非零流邊，(v3,v5)是零流邊。51第五十一頁(yè)，共八十四頁(yè)，2022年，8月28日例如圖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第五十二頁(yè)，共八十四頁(yè)，2022年，8月28日設(shè)f是網(wǎng)絡(luò)G上的一個(gè)可行流，μ是從vs到vt的一條鏈，若對(duì)μ上的任意一條邊(vi,vj)有若(vi,vj)μ+，則0fij<cij，即μ+中每一邊是非飽和邊。若(vi,vj)μ-，則0<fijcij，即μ-中每一邊是非零流邊。則稱μ是一條增廣鏈。53第五十三頁(yè)，共八十四頁(yè)，2022年，8月28日例如圖7.26中，鏈μ={vs,v1,v2,v3,v5,vt}就是一條增廣鏈，因?yàn)棣?={(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第五十四頁(yè)，共八十四頁(yè)，2022年，8月28日對(duì)于給定的網(wǎng)絡(luò)G=(V,E,C)，設(shè)S,TV，并且ST=V，ST=，vs

S，vtT，以S中點(diǎn)為始點(diǎn)，以T中點(diǎn)為終點(diǎn)的邊的集合，稱為G的割集，記為(S,T)。割集(S,T)中所有邊的容量之和稱為割集(S,T)的容量，記為C(S,T)，即55第五十五頁(yè)，共八十四頁(yè)，2022年，8月28日例如圖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第五十六頁(yè)，共八十四頁(yè)，2022年，8月28日如果從網(wǎng)絡(luò)G中去掉割集(S,T)中的邊，從vs就沒有路可以到達(dá)vt。對(duì)于網(wǎng)絡(luò)G，它有許多割集，我們可以找到容量最小割集。而網(wǎng)絡(luò)G的最大流量一定不會(huì)超過容量最小割集的容量，稱網(wǎng)絡(luò)G中容量最小的割集為G的最小割集。如果把網(wǎng)絡(luò)G看成各種粗細(xì)不同的管道網(wǎng)，而最小割集就相當(dāng)于管道網(wǎng)中最細(xì)管道部分的總和。二、最大流最小割集定理由上面例子可知，如果找到網(wǎng)絡(luò)G的一個(gè)可行流，其流量等于網(wǎng)絡(luò)G的最小割集容量，則該可行流一定是最大流。下面最大流最小割集定理就是要說明這一點(diǎn)。57第五十七頁(yè)，共八十四頁(yè)，2022年，8月28日定理1可行流f*是最大流當(dāng)且僅當(dāng)G中不存在關(guān)于f*的增廣鏈。推論在任意一個(gè)容量網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。三、求最大流的標(biāo)號(hào)算法由上面定理1可知可行流f是否是最大流，關(guān)鍵看網(wǎng)絡(luò)G中是否存在關(guān)于可行流f的增廣鏈，定理1的證明過程為我們提供了尋找增廣鏈的方法及改進(jìn)可行流f的方法。如果在網(wǎng)絡(luò)G中存在關(guān)于可行流f的增廣鏈（從vs到vt），則可按定理1證明中所給的方法修改可行流f，得到一個(gè)新的可行流f‘，而f‘的流量大于f的流量。如果在G中不存在關(guān)于可行流f的增廣鏈，則可行流f就是最大流。尋找關(guān)于可行流f的增廣鏈可按下面介紹的標(biāo)號(hào)法來實(shí)現(xiàn)。58第五十八頁(yè)，共八十四頁(yè)，2022年，8月28日求網(wǎng)絡(luò)G的最大流的標(biāo)號(hào)法分為兩步，第1步是標(biāo)號(hào)過程，通過標(biāo)號(hào)尋找增廣鏈；第2步是調(diào)整過程，沿增廣鏈個(gè)性可行流f的流量。設(shè)f是網(wǎng)絡(luò)G上的可行流（初始可行流可取零流f={fij=0}）。1標(biāo)號(hào)過程（1）首先給發(fā)點(diǎn)vs標(biāo)號(hào)(0,+∞)。（2）選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn)vi，對(duì)所有與vi相鄰而沒有標(biāo)號(hào)的頂點(diǎn)vj按下列規(guī)則處理。（a）若(vi,vj)E，并且fij<cij，則給頂點(diǎn)vj以標(biāo)號(hào)(i,δj)，其中δj=min{δi,cij-fij}。（b）若(vj,vi)E，并且fij>0，則給頂點(diǎn)vj以標(biāo)號(hào)(i,δj)，其中δj=min{δi,cij-fji}。59第五十九頁(yè)，共八十四頁(yè)，2022年，8月28日重復(fù)過程（2），可能出現(xiàn)兩種結(jié)果，其一是終點(diǎn)vt得到標(biāo)號(hào)，說明存在一條增廣鏈，則轉(zhuǎn)到調(diào)整過程，其二是終點(diǎn)vt不能獲得標(biāo)號(hào)，說明不存在增廣鏈，這時(shí)可行流f即為最大流。2調(diào)整過程首先按終點(diǎn)vt及其它頂點(diǎn)的第一個(gè)標(biāo)號(hào)，用反向追蹤法在網(wǎng)絡(luò)中找出增廣鏈。例如設(shè)終點(diǎn)vt的第一個(gè)標(biāo)號(hào)為k，則(vk,vt)是增廣鏈上的邊，然后根據(jù)vk的第一個(gè)標(biāo)號(hào)，找到下一個(gè)頂點(diǎn)，即若vk的第一個(gè)標(biāo)號(hào)為j，則(vj,vk)（或者(vk,vj)）是增廣鏈上的邊，直到用此方法找到vs為止。這時(shí)就得到一條從vs到vt的增廣鏈μ。最后按下式修改可行流f。

60第六十頁(yè)，共八十四頁(yè)，2022年，8月28日調(diào)整結(jié)束后，去掉所有標(biāo)號(hào)，返回標(biāo)號(hào)過程重新進(jìn)行標(biāo)號(hào)過程。令61第六十一頁(yè)，共八十四頁(yè)，2022年，8月28日例10用標(biāo)號(hào)法求下圖中從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第六十二頁(yè)，共八十四頁(yè)，2022年，8月28日解（I）標(biāo)號(hào)過程（1）首先給發(fā)點(diǎn)vs標(biāo)以(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第六十三頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰的頂點(diǎn)v1，v2，因?yàn)?vs,v1)E，并且fs1=4<cs1=15，所以v1可以獲得標(biāo)號(hào)(vs,δ1)，其中δ1=min{+∞,

15-4}=11。因?yàn)?vs,v2)E，但fs2=cs2，所以v2不能標(biāo)號(hào)。(vs,11)64第六十四頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰且沒有標(biāo)號(hào)的頂點(diǎn)v2，v3，v4，因?yàn)?v2,v1)E，并且f21>0，所以v2可以獲得標(biāo)號(hào)(v1,δ2)，其中δ2=min{δ1,f21}=min{9,3}=3。因?yàn)?v1,v4)E，并且f14=0<c14=4，所以v4可以獲得標(biāo)號(hào)(v1,δ4)，其中δ4=min{9,

4-0}=4。因?yàn)?v1,v3)E，但f13=c13，所以v3不能標(biāo)號(hào)。(vs,11)(v1,3)(v1,4)65第六十五頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰且沒有標(biāo)號(hào)的頂點(diǎn)v3，因?yàn)?v2,v3)E，并且f23=1<c23=5，所以v3可以獲得標(biāo)號(hào)(v2,δ3)，其中δ3

min{δ2,

c23-f23

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

。(vs,11)(v1,3)(v1,4)(v2,3)66第六十六頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰且沒有標(biāo)號(hào)的頂點(diǎn)為vt，并且vt也與已標(biāo)號(hào)的頂點(diǎn)v4相鄰，所以vt既可以以v3為基礎(chǔ)獲得標(biāo)號(hào)(v3,δt)，也可以以v4為基礎(chǔ)獲得標(biāo)號(hào)(v4,δt’)。但為減少迭代次數(shù)，應(yīng)選擇δ1與δt’兩者較大的給vt標(biāo)號(hào)。因?yàn)棣膖=min{δ3,c3t-f3t}=min{3,3}=3,δt’=min{δ4,c4t-f4t}=min{4,5}=4，所以vt的標(biāo)號(hào)應(yīng)?。╲4,4）。(v4,4)67第六十七頁(yè)，共八十四頁(yè)，2022年，8月28日

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的第一個(gè)標(biāo)號(hào)為v4，得到頂點(diǎn)v4，由v4的第一個(gè)標(biāo)號(hào)為v1，得到頂點(diǎn)v1，由v1的第一個(gè)標(biāo)號(hào)為vs，得到頂點(diǎn)vs，由此得到關(guān)于可行流f的增廣鏈μ={vs,v1,v4

,vt}，其中(vs,v1),(v1,v4),(v4,vt)為前向邊。68第六十八頁(yè)，共八十四頁(yè)，2022年，8月28日

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第六十九頁(yè)，共八十四頁(yè)，2022年，8月28日

vsvt

v4

v2

v3

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

（I）標(biāo)號(hào)過程（1）首先給發(fā)點(diǎn)vs標(biāo)以(0,+∞).

70第七十頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰的頂點(diǎn)v1，v2，因?yàn)?vs,v1)E，并且fs1=8<cs1=15，所以v1可以獲得標(biāo)號(hào)(vs,δ1)，其中δ1=min{+∞,

15-8}=7。因?yàn)?vs,v2)E，但fs2=cs2，所以v2不能標(biāo)號(hào)。71第七十一頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰且沒有標(biāo)號(hào)的頂點(diǎn)v2，v3，v4，因?yàn)?v2,v1)E，并且f21>0，所以v2可以獲得標(biāo)號(hào)(v1,δ2)，其中δ2=min{δ1,f21}=min{9,3}=3。因?yàn)?v1,v3)E，但f13=c13，所以v3不能標(biāo)號(hào)。因?yàn)?v1,v4)E，并且f14=c14，所以v4不能標(biāo)號(hào)。72第七十二頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰且沒有標(biāo)號(hào)的頂點(diǎn)v3，v4，因?yàn)?v2,v3)E，并且f23=1<c23=5，所以v3可以獲得標(biāo)號(hào)(v2,δ3)，其中δ3=min{δ2,

c23-f23}=min{3,4}=3。因?yàn)?v2,v4)E，并且f24=5<c24=6，所以v4可以獲得標(biāo)號(hào)(v2,δ4)，其中δ4

=min{δ2,

c23-f23}=min{3,

6-5}=1。73第七十三頁(yè)，共八十四頁(yè)，2022年，8月28日

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相鄰且沒有標(biāo)號(hào)的頂點(diǎn)為vt，并且vt也與已標(biāo)號(hào)的頂點(diǎn)v4相鄰，所以vt既可以以v3為基礎(chǔ)獲得標(biāo)號(hào)(v3,δt)，也可以以v4為基礎(chǔ)獲得標(biāo)號(hào)(v4,δt’)。但為減少迭代次數(shù)，應(yīng)選擇δ1與δt’兩者較大的給vt標(biāo)號(hào)。因?yàn)棣膖=min{δ3,c3t-f3t}=min{3,3}=3,δt’=min{δ4,c4t-f4t}=min{1,1}=1，所以vt的標(biāo)號(hào)應(yīng)?。╲3,3）。74第七十四頁(yè)，共八十四頁(yè)，2022年，8月28日

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第七十五頁(yè)，共八十四頁(yè)，2022年，8月28日

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的第一個(gè)標(biāo)號(hào)為v3，得到頂點(diǎn)v3，由v3的第一個(gè)標(biāo)號(hào)為v2，得到頂點(diǎn)v2，由v2的第一個(gè)