1、第九章 圖論的數(shù)學(xué)模型在現(xiàn)實生活、生產(chǎn)中，經(jīng)常遇到研究事物之間關(guān)系的問題.我們可以用圖把各種關(guān)系形象而直觀地描繪出來.圖中的點表示要研究的離散對象，用邊表示對象間的關(guān)系，并利用圖的性質(zhì)和算法求解模型.這是研究離散問題的重要手段.本章將介紹數(shù)學(xué)上圖論的基本概念與最小樹、最短路、中國郵遞員問題、網(wǎng)絡(luò)最大流問題及相關(guān)的模型應(yīng)用.9.1 圖論的基本概念在實際生活當(dāng)中，我們常利用點與線的示意圖反映對象間的關(guān)系.例1 圖9.1是我國北京、上海等十個城市間的鐵路交通圖，反映了這十個城市間的鐵路分布情況.這里用點代表城市，用點和點之間的連線代表著兩個城市之間的鐵路線. 例2 有甲、乙、丙、丁、戊五個球隊，它們

2、之間比賽的情況，也可以用圖表示出來.已知甲隊和其它各隊都比賽過一次，乙隊和甲、丙隊比賽過，丙隊和乙、丁隊比賽過，丁隊和丙、戊隊比賽過，戊隊和甲、丁隊比賽過.為了反映這個情況，可以用點v1,v2,v3,v4,v5分別代表五個隊，兩隊之間比賽過，就在這兩個隊相應(yīng)點之間連一條線，這條線不過其它點，如圖9.2所示.如果我們要進一步反映比賽中的勝負關(guān)系，可以用一條帶箭頭的連線表示，如甲隊勝了乙隊，可以從v1引一條帶箭頭的連線到v2.如圖9.3反映了五個球隊比賽的勝負情況，可見v1三勝一負，v4三場球全負等等.綜上所述，圖論中的圖是由一些點及一些點間的連線組成的.它不同于通常意義的幾何圖形，它用點表示事物

3、，用點間有無連線表示事物之間的某種關(guān)系，以一種抽象的形式來表達確定的事物.由上例知，點間的連線有的不帶箭頭，有的帶箭頭.為了區(qū)別起見，前者稱為邊，后者稱為弧.如一個圖G是由點及邊所構(gòu)成的，則稱之為無向圖（也簡稱圖），記為G=(V , E) .式中V，E分別是G的點集合和邊集合.一條連接點vi,vjV的邊記為 vi,vj(或vj,vi).如圖9.4是一個無向圖.V= v1,v2,v3,v4，E=e1,e2,e3,e4,e5,e6,e7,其中 e1=v1,v2(或v2,v1). e2 =v1,v2 e3=v2,v3 e4=v3,v4 e5=v1,v4 e6=v1,v3 e7=v4,v4 . 如果一

4、個圖D式由點及弧所構(gòu)成的，則稱為有向圖，記為D=(V,A).式中V,A分別表示D的點集合和弧集合.一條方向從vi指向vj的弧記為（vi,vj）.如圖9.5是一個有向圖.V= v1,v2,v3,v4,v5. A=a1,a2,a3,a4,a5,a6.其中，a1=( v1,v2),a2=( v2, v1),a3=( v1, v3), a4=( v4 ,v2),a5=( v3, v4),a6=( v4, v5).下面再介紹一些常見名詞和記號.考慮無向圖G=(V , E).若邊e=u,v E,則稱u,v是e的端點，也稱u,v是相鄰的.稱e是點u（及點v）的關(guān)聯(lián)邊.若圖G中，某個邊的兩個端點相同，則稱e是

5、環(huán)（如圖9.7中的e7）.若兩個點之間有多于一條的邊，稱這些邊為多重邊（如圖9.4中的e1,e2）.一個無環(huán)、無多重邊的圖稱為簡單圖.一個無環(huán)，但允許有多重邊的圖稱為多重圖.以點v為端點的邊的個數(shù)稱為v的次，記為d(v).如圖9.4中d(v1)=4,d(v2)=3,d(v4)=4(環(huán)e7在計算d(v4)作兩次算).次為奇數(shù)的點，稱為奇點，否則稱為偶點.給定一個圖G=(V , E).一個點、邊交錯序列（,）,如果滿足=，（t=1,2,3, k-1）.則稱之為一條聯(lián)結(jié)鏈，的鏈，記為（, ）.鏈（, ）中，若=，則稱之為一個圈，記為（, ）.若鏈中（,）中，,都是不同的，則稱之為初等鏈；若圈中（,

6、）中,都是不同的，則稱之為初等圈；若鏈（圈）中含的邊均不相同，則稱之為簡單鏈（圈）.以后說到鏈（圈），除非特別交代，均指初等鏈（圈）.例如圖9.6中，（v1,v2,v3,v4,v5,v3,v6）是簡單鏈，但不是初等鏈.（v1,v2,v3,v4,v5）是一條初等鏈.（v1,v2,v3,v4,v1）是初等圈.（v4,v1,v2,v3,v5,v7,v6,v3,v4）是簡單圈，但不是初等圈.圖中不存在v1到v9的鏈.圖G中，若任何兩點之間，至少有一條鏈，則稱G是連通圖.否則稱不連通的圖.給定一個圖G=(V , E).若使V=及E，稱是G的支撐子圖.如圖9.7中，（b）是（a）的支撐子圖，而（c）不是.

7、設(shè)給有向圖D=(V,A) .從D中去掉弧上的箭頭，所得到的無向圖稱D的基礎(chǔ)圖.D中一條弧a=(u,v), u稱a的始點，v稱a的終點.稱弧是從u指向v的.設(shè)（,）是D中的點、弧交錯序列，在基礎(chǔ)圖中對應(yīng)一條鏈，稱為D的鏈.類似的定義D中圈.如（,）是D中一條鏈，且=（，）稱從到的一條路.若路中的第一個點和最后一個點相同，稱回路.如圖9.8（v1,v3,v4,v5）是從v1 到的v5路，（v1,v2,v4,v5）是鏈，不是路.（v1,v3,v4,v2,v1）是回路.注：對無向圖、鏈與路（圈與回路）這兩個概念是一致的.9.2 最小支撐樹與最短路9.2.1最小支撐樹（最小生成樹）及其算法.例1 已知有

8、五個城鎮(zhèn)，要再它們之間架電話線，要求任何兩個城鎮(zhèn)都可以互相通話.（允許通過其它城鎮(zhèn)），并且電話線的根數(shù)最少.用五個點v1,v2,v3,v4,v5代表五個城鎮(zhèn).如果在某兩個城鎮(zhèn)之間架設(shè)電話線，則在相應(yīng)兩個點之間連一條邊，這樣一個電話線網(wǎng)就可以用一個圖來表示.為了使任何兩個城鎮(zhèn)都可以通話，這樣的圖必須是連通的.其次，若圖中有圈，從圈上任去一邊，余下圖任連通，省去一根電話線.因而，滿足條件的電話線網(wǎng)對應(yīng)的圖必是連通、不含圈的圖.如圖9.9定義1. 一個無圈的連通圖稱樹.定義2. 設(shè)圖T=(V, )是G=(V , E)的支撐子圖，如果圖T=(V, )是一個樹，則稱T是G的支撐樹.定義3. 圖G=(V

9、, E)，G中每一條邊vi,vj，相應(yīng)地有一個數(shù)wij，則稱這樣的圖G為賦權(quán)圖. wij稱為邊vi,vj的權(quán).這里所說的“權(quán)”，是指與邊有關(guān)的數(shù)量指標.根據(jù)實際問題的需要，可以賦予它不同的含義，例如表示距離、時間、費用等.賦權(quán)圖不僅指出各點間的鄰接關(guān)系，同時也表示出各點間的數(shù)量關(guān)系.定義4. 設(shè)有連通圖G=(V , E)，對每一e=vi,vj有一非負權(quán)，w(e)= wij.如果T=(V, )是G的支撐樹，稱中所有邊權(quán)數(shù)之和為支撐樹T的權(quán)，記為w(T).即w(T)= wij.如果支撐樹T*的權(quán)w(T*)是所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹（簡稱最小樹）.既w(T*)=w(T).最小

10、支撐樹有其廣泛的應(yīng)用，如例1，支撐樹有多種，如給出各城鎮(zhèn)間的道路長度，我們則應(yīng)選用造價最低的電話線網(wǎng).這個問題就是賦權(quán)圖上的最小樹問題.下邊就是介紹求最小樹的算法.方法一、（避圈法）該算法是1956年由Kruskal（克魯斯凱爾）提出.步驟如下：設(shè)G為由m個節(jié)點構(gòu)成的連通賦權(quán)圖.(1)先把G中所有邊按權(quán)數(shù)大小由小到大重新排列，并取權(quán)數(shù)最小的一條邊取為T中的邊.(2)從剩下的邊中按（1）中排列取下一條邊.若該邊與前已取進T中的邊形成某個回路，則舍去該邊；否則把該邊取進T中.重復(fù)步驟（2），直至有m-1條邊取進T中為止，則這m-1條邊就組成G的最小支撐樹.例2 （如圖9.10） 8個城市v0,v1

11、,v7之間有一個公路網(wǎng)，公路為圖中的邊，邊上的權(quán)數(shù)表示公路的長度，現(xiàn)要沿公路架設(shè)電話線，要求如何架設(shè)，使電話線總長最小.解：這個問題就是求圖9.10上的最小樹.先按各邊權(quán)數(shù)由小到大排列.為e1=v0,v1, e2=v2,v3, e3=v1,v2, e4=v0,v2，e5=v5,v6, e6=v3,v4，e7=v1,v3，e8=v4,v5，e9=v4,v7，e10=v0,v5， 頂點數(shù)m=8. 由Kruskal法的步驟，順次試將e1,e2,e3,e4,e5,e6,e7,e8,e9取進T中（舍去e4和e7），于是最小支撐樹T= e1,e2,e3,e5,e6,e8,e9.如圖9.11.方法二、（破圈

12、法）任取一圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）.在余下的圖中，重復(fù)這個步驟，一直得到一個不含圈的圖為止，這時的圖便是最小樹.用破圈法解上題，任取一圈，比如（v1,v0,v6,v1），邊v6,v0最大，于是去掉；取圈（v1,v0,v2,v1），邊v0,v2與v1,v2都為2，任去一邊v0,v2.如此下去，得到一個不含圈的圖.即為最小樹.9.2.2 最短路問題及Dijkstra(迪杰斯特拉)算法.一個典型的最短路問題如下：例3. 8個城市之間v0,v1,v7之間有一個公路網(wǎng)（如圖9.12）.每條公路為圖中的邊，邊上的權(quán)數(shù)表示通過該公路所需的時間

13、.你在城市v0,從v0到v7應(yīng)該選擇什么路徑，所需時間最少？即求d(v0,v7) (表示從v0到v7的最短路徑的和)目前公認解決最短路的最佳算法是由Dijkstra提出的.這個算法不僅得到從v0到v7的最短路，還會得到由v0出發(fā)到其它各點的最短路.Dijkstra法的基本思想是從v0出發(fā)，逐步向外探尋最短路.執(zhí)行過程中，與每個點對應(yīng)，記尋下一個數(shù)（稱為這個點的標號），它或者表示從v0到該點的最短路的權(quán)（稱為P標號），或者是從v0到該點的最短路權(quán)的上界（稱為T標號）.方法的每一步是去修改T標號，并且把T標號點改為具有P標號的點，從而使G中具P標號的頂點數(shù)多一個.這樣，經(jīng)過p1步（p是圖中點的個數(shù)

14、），就可求出從v0到各點的最短路.在敘述Dijkstra算法之前，以例3為例說明一下這個方法的思想.例3中，v0出發(fā)，wij0.故有d(v0 ,v0)=0.這時v0是具有P標號的點.考察從v0出發(fā)的三條邊，v0,v1, v0,v2 ,v0,v3.從v0出發(fā)，沿v0,v1到達v1,需時間d(v0 ,v1)+w01=2；如從v0出發(fā)，沿v0,v2到達v2,需時間d(v0 ,v0)+w02=8；類似的，沿v0,v3到v3,需時間d(v0 ,v0)+w03=1.因min d(v0 ,v0)+w01, d(v0 ,v2)+w02, d(v0 ,v0)+w03=1.可斷言，從v0出發(fā)到v3的最短路需時間1

15、.即d(v0 ,v3)=1.最短路（v0,v3）.這時因為從v0到v3的任一條路，如不是（v0,v3），則必先從v0沿v0,v1到達v1，或沿v0,v2到達v2.但如此，此時已需時間2或8，不管再如何從v1或v2到達v3,所需時間不會比1少.因而推知d(v0 ,v3)=1.這樣使v3具有P標號.現(xiàn)在考察從v0,v3指向余點的邊.由上已知，從v0出發(fā)，沿v0,v1到達v1,需時間為2；如從v0出發(fā)，沿v0,v2到達v2,需時間為8；從v3出發(fā)，沿v3,v2到達v2,需時間d(v0 ,v3)+w32=8，從v3出發(fā)，沿v3,v6到達v6,需時間d(v0 ,v3)+w36=10.因min d(v0

16、,v0)+w01, d(v0 ,v2)+w02, d(v0 ,v3)+w32, d(v0 ,v3)+w36= d(v0 ,v0)+w01=2,基于同樣的理由，從v0到v1的最短路是：（v0 ,v1），即d(v0 ,v1)=2.又使v1變成具有P標號的點.如此重復(fù)，直到求出v0到v7的最短路.下面給出Dijkstra的一般步驟：用P，T表示某點的P標號、T標號，Si表示第步時，具P標號的點集.1. （=0）令S0=vs 對于vvs,T(v)=+.2. 如果Si=V (V表示圖中所有點的集合),算法終止，這時考察對每個vSi, d(vs,v)=P(v)；否則，進入3.3. 考察每個使vk,vjE

17、且vjSi的點.如果T(vj)P(vk)+wkj,則把 T(vj)改為P(vk)+wkj；否則，轉(zhuǎn)入4.4. 令T()=T(vj).把的T標號變?yōu)镻標號，P()=T();令Si+1=Si+,轉(zhuǎn)入2；現(xiàn)用該法求例3，v0到 v7的最短路.1 vs=v0,S0=v0.P(v0)=0.2 v0,v1E, v1S0, P(v0)+w01T(v1), T(v1)修改為P(v0)+w01=2.同理 T(v2)修改為P(v0)+w02=8; T(v3)修改為P(v0)+w03=1.3 在所有T標號中，T(v3)最小.于是令P(v3)=1.S1=v0,v3.=1.2. T(v6)=P(v3+w36)=10.

18、3. 在所有標號中，T(v1)=2最小，令P(v1)=2. S2=v0,v1,v3.=2. 2. T(v4)=P(v1)+w14=3. 3. 在所有標號中，T(v4)=3最小，令P(v4)=3.S3= v0,v1,v3,v4.=3. 2. T(v7)=12, T(v5)=6. 3. 在所有標號中，T(v5)=6最小，令P(v5)=6.S4= v0,v1,v3,v4,v5.=4. 2. T(v2)=7.3. 在所有標號中，T(v2)=7最小，令P(v2)=7.S5= v0,v1,v2,v3,v4,v5.=5. 2. T(v6)=9. 3. 在所有標號中，T(v6)=9最小，令P(v6)=9.S6

19、= v0,v1,v2,v3,v4,v5,v6.=6. 2. T(v7)=12. 3. 在所有標號中，T(v7)=12最小，令P(v7)=12.S7= v0,v1,v2,v3,v4,v5,v6,v7.=7.因為S7=V，所以終止.從v0到v7的最短路d(v0,v7)=P(v7)=12.路徑為（v0,v1,v4,v7）或（v0,v1,v4,v5,v7）或（v0,v1,v4,v2,v6,v7）.9.3 中國郵遞員問題一名郵遞員帶著要分發(fā)的郵件出發(fā)，經(jīng)過要分發(fā)的每條街道，送完郵件后又返回郵局.如何設(shè)計送件路線，以盡可能少的行程來完成送郵件的任務(wù).這類問題是由我國的管梅谷教授于1962年提出，國際上稱為

20、中國郵遞員問題.若要把它抽象為圖論的語言，就是在一個連通的賦權(quán)圖中，尋找一個圈，過每邊至少一次，使圈的總權(quán)最小.為了解決這個問題，我們先了解一下有關(guān)一筆畫的問題.給定一個連通多重圖G，若存在一條鏈，過每邊一次，其僅一次，則稱鏈為歐拉鏈.若存在一個簡單圈，過每邊一次，稱歐拉圈.一個圖有歐拉圈，則稱為歐拉圖.顯然，一個圖若能一筆畫出，此圖必是歐拉圈或含有歐拉鏈.定理1 連通多重圖G是歐拉圖當(dāng)且僅當(dāng)G中無奇點.（證略）有了以上知識，我們就可知，如果郵遞員負責(zé)的范圍，街道圖如無奇點，就可從郵局出發(fā)，走每條街道一次，且僅一次，回到郵局.這樣的路程最優(yōu).而對于有奇點的街道，就必須在某些街道重復(fù)一次或多次.

21、如圖9.13的街道圖中，若v1是郵局，郵遞員可按路線：v1v2v3v4v1v6v5v4v1(總權(quán)12)，也可按路線：v1v2v3v4v1v6v5v4v5v6v1(總權(quán)16).按第一條路線，在邊v1,v4上重復(fù)一次.而第二條路線，在v5,v4v6,v5v6,v1重復(fù)一次.如果在某條路線中，邊vi,vj重復(fù)幾次，我們在圖vi,vj之間增加幾條邊，每條邊的權(quán)和原來的權(quán)相等.新增加的邊稱重復(fù)邊.這條路線是相應(yīng)新圖的歐拉圈，如圖9.14（a）和（b）. 顯然，兩條路線的總路程差等于相應(yīng)重邊權(quán)的差.因而，原問題可以敘述為在一個有奇點的圖中，增加重復(fù)邊，使新圖不含奇點，且重復(fù)邊總權(quán)最小.我們把新圖不含奇點而

22、增加重復(fù)邊的方案，稱為可行方案.使總權(quán)最小的可行方案稱為最優(yōu)方案.方法分兩步：一、 可行方案的確定方法.因為在任一圖中，奇點個數(shù)必為偶數(shù).所以圖中有奇點，就可以配成對.又因圖連通，故每對奇點間必有一條鏈.我們把這條鏈的所有邊作為重復(fù)邊加到圖中，可見新圖必?zé)o奇點，成為可行方案.例1 圖9.15中的街道圖，有v2,v4,v6,v8 四個奇點，我們以v2,v4為一對，v6,v8為一對. 在圖9.15中，連v2與v4的鏈中任一條，例取（v2,v1,v8,v7,v6,v5,v4）,并加上相應(yīng)的重復(fù)邊 .同樣任取v6與v8間的鏈（v8, v1,v2,v3,v4,v5,v6）,并加上相應(yīng)的重復(fù)邊，得圖9.1

23、6.這個圖，沒有奇點.故已是歐拉圖.總權(quán)為2w12+w23+w34+2w45+2w56+w67+w78+2w18=51二、 調(diào)整可行方案，使重復(fù)邊總長下降.（a）在最優(yōu)方案中，圖的每一條邊最多有一條重復(fù)邊.一般情況下，若vi,vj上有兩條以上重復(fù)邊，去掉偶數(shù)條.例如圖9.16 v1,v2有兩條重復(fù)邊，都去掉，圖仍無奇點.但總長度下降，仍是可行方案.對其它重復(fù)邊也是如此.得圖9.17. （b） 在最優(yōu)方案中，圖中每個圈上重復(fù)邊的權(quán)不大于該圈總權(quán)的一半. 我們看到，如圖中某圈重復(fù)邊去掉，給原來沒有的加上，圖中仍無奇點.因而，如某圈重復(fù)邊總權(quán)數(shù)大于該圈一半，用上面的方法調(diào)整，總權(quán)下降. 例如圖9.1

24、7中，圈（v2,v3,v4,v9,v2）總長24，重復(fù)邊總權(quán)數(shù)14，大于總數(shù)的一半，作一次調(diào)整.以v2,v9,v4,v9上的重復(fù)邊代替v2,v3,v3,v4上的，重復(fù)邊總權(quán)下降至10.如圖9.18三、 判斷最優(yōu)方案標準從上分析知，（a）與（b）是最優(yōu)方案必須滿足的，反之可行方案滿足了（a）、（b）,則一定最優(yōu)以此為標準，對可行方案檢查，若滿足（a）、（b），則最優(yōu)；若不滿足，則相應(yīng)調(diào)整，直至滿足.檢查圖9.18，圈（v1,v2,v9,v6,v7,v8,v1）,重復(fù)邊總權(quán)13，圈總權(quán)24，不滿足.調(diào)整得圖9.19.檢查圖9.19，（a）、（b）均滿足，于是得最優(yōu)方案.9.4 網(wǎng)絡(luò)最大流問題在實際

25、問題當(dāng)中，有許多關(guān)于網(wǎng)絡(luò)流量得問題.如運輸網(wǎng)絡(luò)中的車量流、電路網(wǎng)絡(luò)中的電流，通訊網(wǎng)絡(luò)中的信息流，水管網(wǎng)絡(luò)中的水流等等.先看一實例，如圖9.20，是一個石油輸送管網(wǎng)，頂點表示石油的轉(zhuǎn)送站，各條弧表示石油輸送的管道，以及石油的流動方向.由 于歷史原因，各管道的半徑不同，即輸送能力不同.問應(yīng)該如何安排管道內(nèi)的實際流量，使充分利用管網(wǎng)而達到最大流量.圖9.20，要求通過石油管網(wǎng)，從v1運送v6至，弧邊的數(shù)字代表了這條管道的最大運輸能力.圖9.21給出了一個方案，弧旁的數(shù)字代表實際每條管道的流量，這要求每條管道的流量不超過最大的流量，又要盡可能使總流量大，很明顯這個方案還不是最優(yōu)，那么應(yīng)如何調(diào)整，最大輸

26、送量是多少？下面就來研究類似的問題，找到一個一般的解決方法.定義1. 給定一個有向圖D=(V, A)在V中指定一點，稱發(fā)點，記vs.另一點稱收點，記vt.其余稱中間點.對于每條弧（vi,vj）A，對應(yīng)cij0稱弧的容量.這樣的D叫作網(wǎng)絡(luò)，記D=(V,A,C).所謂網(wǎng)上的流，指弧（vi,vj）上的實際流量，記fij.如例1圖9.20中，v1是發(fā)點，v6是收點，其余是中間點.弧旁的數(shù)字是cij.圖9.21的運輸方案，即是網(wǎng)上的一個流，每條弧上的實際通過量就是流量，即f12=5，f24=2，f34=1等.在運輸網(wǎng)絡(luò)中，可以看到兩個明顯的要求：一是每個弧上的流量不超過弧的容量；二是中間點的流量為零.由

27、于中間點只起轉(zhuǎn)運作用，流入多少，流出多少.易見發(fā)點的凈流出量與收點的凈流入量相等，也是方案的總輸送量.定義2 滿足下述條件的流f稱可行流：1） 容量限制條件：對每個?。╲i,vj）A, 0fijcij.2） 平衡條件：對于中間點，流出量=流入量.即對每個(s , t ) 有fijfji=0 對于發(fā)點，記fsjfjs = v(f)對于收點，記ftifit = -v(f)式中v(f) 稱為這可行流的流量，即發(fā)點的凈輸出量（或收點的凈輸入量）.可行流總是存在的.比如令所有弧的流量fij=0,就是一個可行流（稱零流）.其流量v(f)=0.最大流問題就是求一個流fij使其流量v(f)達到最大，并滿足：

28、0fijcij （vi,vj）A (9.4.1) fij +fji = (9.4.2)我們可看到最大流問題是一個特殊的線性規(guī)劃問題.即求一組fij,在滿足(9.4.1)和(9.4.2)條件下，使v(f)最大.但我們將會利用圖的特點，解決這個問題.先來認識一下增廣鏈.給一個可行流f=fij.網(wǎng)絡(luò)中fij=cij的弧稱飽和弧，使fijcij的弧稱非飽和弧.把fij=0的弧稱為零流弧，fij0的弧稱為非零流弧.如圖9.21 中，（v5,v4）是飽和弧，其余為非飽和弧；所有弧是非零流弧.若是網(wǎng)絡(luò)中連vs到vt的鏈，定義鏈的方向是vs到vt，則鏈上的弧分為兩類：一類弧方向與鏈一致，稱前向弧.全體前項弧記

29、+；另一類與鏈方向相反，稱后向弧. 全體前項弧記-.如圖9.21中，鏈=（v1,v2,v3,v4,v5,v6）中. +=(v1,v2), (v2,v3), (v3,v4), (v5,v6); - =(v5,v4).定義3 設(shè)f是可行流，是vs到vt的一條鏈，若滿足下列條件，稱為增廣鏈：在?。╲i,vj）+上，0fijcij，即+中每一弧是非飽和弧.在?。╲i,vj）-上，0fijcij，即-中每一弧是非零流弧.圖9.21中，鏈=（v1,v2,v3,v4,v5,v6）就是增廣鏈.設(shè)S,TV, ST=，我們把始點在S，終點在T的所有弧構(gòu)成的集合，記為（S,T）.定義4 網(wǎng)絡(luò)D=(V,A,C)，若點

30、集V被剖分為兩個非空集合V1和，使vsV1, vt,則把弧集（V1, ）稱為是截集.顯然，若把某一截集（V1, ）的弧從網(wǎng)絡(luò)中丟去，則從vs到vt不存在路.所以，直觀上講截集是從vs到vt的必經(jīng)之道.定義5 給一截集（V1, ），把截集中所有弧容量之和稱為這個截集的容量（簡稱為截量）.記為c(V1, ) 即c(V1, )=不難證明，任何一個可行流的流量v(f)都不會超過任一截集的容量.即v(f) c(V1, ).顯然，若對于一可行流f*，網(wǎng)絡(luò)中的截集（V1*, *），使f*=c(V1*, *),則f*是最大流，而(V1*, *)必定是D的所有截集中，容量最小的一個，即最小截集.因此任一網(wǎng)絡(luò)D中

31、，從vs到vt的最大流量等于最小截集的容量.我們可以利用增廣鏈來求得這個最大流.這個方法的思想是：先給定一個可行流f，在D中尋找增廣鏈，在這條鏈上改變流量，得到流量增大的新的可行流.如再找不到增廣鏈，則已達到最大流.實際計算中，我們采用最大流標號法（Ford, Fulkerson）從一個可行流出發(fā)（若網(wǎng)絡(luò)中無可行流f，則可用零流），經(jīng)過標號過程和調(diào)整過程.1） 標號過程.在這個過程中，網(wǎng)絡(luò)中的點或者是標號點（又分為已檢查和未檢查兩種），或者是未標號點.每個標號點的標號分兩部分：第一標號表明它的標號從哪一點得到的，以便找增廣鏈；第二個標號，是為確定增廣鏈的調(diào)整量.標號過程開始，總先給vs標上（0

32、，+），這時vs是標號而未檢查的點，其余都是未標號點.一般地，取一個標號而未檢查的點vi，對一切未標號點vj：(1) 若在弧（vi,vj）上，fijcij，則給vj標號（vi, l(vj)）.這里l(vj)=min l(vi), cij-fij.這時點vj成為標號未檢查點.(2) 若在?。╲j,vi）上，fji0，則給vj標號（-vi, l(vj)）.這里l(vj)=min l(vi), fji.這時點vj成為標號未檢查點.于是vi成為標號而已檢查的點.重復(fù)上述步驟，一旦vt被標上號，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整過程.若所有標號都已經(jīng)查過，而標號過程進行不下去，算法結(jié)束，可行流已

33、是最大流.2） 調(diào)整過程.首先按vt及其它點的第一個標號，利用“反向追蹤”的辦法，找出增廣鏈.例如設(shè)vt的第一個標號為vk(或-vk)，則弧(vk,vt)(或(vt,vk)是上的弧.接下來檢查vk的第一個標號，若為vi(或-vi)，則弧(vi,vk)(或(vk,vi)是上的弧.再檢查vi的第一個標號，依次下去，直到vs為止.這時被找出的弧就構(gòu)成了增廣鏈.令調(diào)整量是l(vt),即vt的第二個標號.令去掉所有的標號，對新的可行流=.重新進入標號過程.例1. 用標號法求圖9.22所示網(wǎng)絡(luò)的最大流.弧旁的數(shù)是（cij,fij）.解：（一）標號過程.（1） 首先給vs標上（0，+）.（2） 檢查vs,在

34、弧（vs,v2）上，fs2=cs2=3不滿足標號條件.弧（vs,v1）上，fs1cs1=5.則v1的標號為（vs, l(v1)）其中l(wèi)(v1)=min l(vs), cs1-fs1=min+,5-1=4.（3） 檢查v1，在?。╲1,v3）上，f13=c13=2不滿足標號條件. 在?。╲2,v1）上，f21=10.則v2的標號為（-v1, l(v2)）其中l(wèi)(v2)=min l(v1),f21=min4, 1=1.（4） 檢查v2, ?。╲2,v4）上，f24c24.則v4的標號為（v2, l(v4)）其中l(wèi)(v4)=min l(v2), c24-f24=min1,4-3=1. 在弧（v3,v

35、2）上，f32=10.則v3的標號為（-v2, l(v3)）其中l(wèi)(v3)=min l(v2),f32=1.（5） 在v3,v4中任選一個進行檢查.例如，?。╲3,vt）上，f3tc3t.則vt的標號為（v3, l(vt)）其中l(wèi)(vt)=min l(v3), c3t-f3t=1.因vt有了標號，故轉(zhuǎn)入調(diào)整過程.（二）調(diào)整過程.按點的第一個標號找到一條增廣鏈，如圖9.23中粗線所示.易見+=(vs,v1), (v3,vt), -=(v2,v1),(v3,v2).按=1在上調(diào)整f.+：fs1+=1+1=2. f3t+=1+1=2.-：f21-=1-1=0. f3t-=1-1=0.其余fij不變.

36、調(diào)整后得如圖9.24所示可行流，對這個可行流進入標號過程，尋找增廣鏈.開始給vs標上（0，+）.于是檢查vs,給v1標以（vs,3）.檢查v1,弧（v1,v3）上，f13=c13;弧（v2,v1）,f21=0均不符合條件.標號過程無法進行下去，算法結(jié)束.這是可行流（圖9.24）即為所求最大流.最大流量為v(f)=fs1+fs2=f4t+f3t=5.與此同時可找到最小截集（V1, ），其中V1為標號點的集合, 為未標號點集合.弧集合（V1, ），即為最小截集.上例中，V1=vs,v1, =v2,v3,v4,vt.于是（V1, ）=（vs,v2），（v1,v3）是最小截集，它的容量必也是5.由上述

37、可見，用標號法找增廣鏈以求最大流的結(jié)果，同時得到一個最小截集.最小截集的容量的大小影響總流量的提高.因此要提高流量，必須先考慮改善最小截集中各弧的容量，提高它們的通過能力.另一方面，最小截集中的弧的通過能力被降低，就會使總的輸送量減少.閱讀材料哥尼斯堡七橋問題這是歷史上一個有名的數(shù)學(xué)難題.此問題在1736年被Euler解決之前一直使這個普魯士城鎮(zhèn)中的居民很感興趣.18世紀，普魯士的哥尼斯堡鎮(zhèn)的普雷格爾河上有七座橋，這七座橋?qū)⒑拥膬砂杜c河中的兩個島嶼連接起來，如圖9.25所示.A f c d e D Ca b B g 圖9.25 Cc g A d e D b a f B圖9.26假設(shè)兩塊島嶼用A

38、和B表示，a,b,c,d,e,f,g表示七座橋（圖9.25）.問題：（1）一個人能否經(jīng)過每座橋恰好一次？（2）能否恰好經(jīng)過每座橋一次并且最后能回到原出發(fā)點？歐拉解決七橋問題采用了“數(shù)學(xué)模型”法.建模：既然島嶼與陸地?zé)o非是橋梁的連接地點，那么就不妨把4處地點縮?。ǔ橄螅┏?個點，并把7座橋表示（抽象）成7條邊，便得到了七橋問題的模擬圖（圖9.26），這樣當(dāng)然并沒有改變問題的實質(zhì)，于是人們企圖一次無重復(fù)地走過7座橋的問題等價于一筆畫出上述圖形的問題（每條邊必須且經(jīng)過一次），此外，圖9.26就是七橋問題的數(shù)學(xué)模型.Euler解決七橋問題是先考慮一般化問題：如果給定任意一個河道圖與任意多座橋，可否判斷每座橋能否恰好走過一次呢？一般化的問題就是要有一個一般化的解法，才有更實際的意義，考察一筆畫的結(jié)構(gòu)特征，有個起點和終點（若起點和終點重合時即為Euler圖）.除起點與終點處，一筆畫中出現(xiàn)的交點處總是一進一出的，故交點的度數(shù)（相連的邊的數(shù)目和）為偶數(shù)，由此Euler給出了一般結(jié)論：1） 連接奇數(shù)個橋的陸地僅有一個或超過兩個以上，不能實現(xiàn)一筆畫.2）連接奇數(shù)個橋的陸地僅有兩個時，則從兩者任意一塊陸地出發(fā)，可以實現(xiàn)一筆畫而停在另一陸地.3）每個陸地都連接有偶數(shù)個橋時，則從任意陸地出發(fā)，都能實現(xiàn)一筆畫而回到出發(fā)點.對于模擬圖，顯然圖必須是連通的，當(dāng)且僅當(dāng)圖為歐拉圖