運籌學 圖與網(wǎng)絡優(yōu)化

運籌學圖與網(wǎng)絡優(yōu)化第一頁，共一百三十一頁，編輯于2023年，星期五圖論概述圖論(GraphTheory)是運籌學中的一個重要分支，主要研究具有某種二元關系的離散系統(tǒng)的組合結(jié)構(gòu)和性質(zhì)。如，通信系統(tǒng)、交通運輸系統(tǒng)、信息網(wǎng)絡系統(tǒng)、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問題常用圖論模型來描述。第二頁，共一百三十一頁，編輯于2023年，星期五網(wǎng)絡規(guī)劃概述網(wǎng)絡規(guī)劃(NetworkProgramming)是圖論與線性規(guī)劃的交叉學科，具有廣泛的應用背景，比如，最短路問題、最小樹問題、最大流問題、最優(yōu)匹配問題等。第三頁，共一百三十一頁，編輯于2023年，星期五七橋問題七橋問題圖形第四頁，共一百三十一頁，編輯于2023年，星期五原理及方法

七橋問題是圖論中的著名問題。1736年，Euler巧妙地將此問題化為圖的不重復一筆畫問題，并證明了該問題不存在肯定回答。原因在于該圖形有頂點連接奇數(shù)條邊。第五頁，共一百三十一頁，編輯于2023年，星期五§10.1圖的基本概念一個圖(Graph)

定義為三元有序組V(G)是圖的頂點集合E(G)是圖的邊集合記Ψ

是關聯(lián)函數(shù)第六頁，共一百三十一頁，編輯于2023年，星期五圖的端點設G是一個圖(Graph)G=(V(G),E(G))，則稱e連接u和v，稱u和v是e的端點。若稱端點u，v與邊e是關聯(lián)的，稱兩個頂點u，v是鄰接的。第七頁，共一百三十一頁，編輯于2023年，星期五設G是一個圖，

圖10－３G的幾何實現(xiàn)第八頁，共一百三十一頁，編輯于2023年，星期五圖的幾何實現(xiàn)

一個圖可用一個幾何圖形表示,稱為圖的幾何實現(xiàn)，其中每個頂點用點表示，每條邊用連接端點的線表示。圖的幾何實現(xiàn)有助與我們直觀的了解圖的許多性質(zhì)。第九頁，共一百三十一頁，編輯于2023年，星期五說明一個圖的幾何實現(xiàn)并不是唯一的；表示頂點的點和表示邊的線的相對位置并不重要，重要的是圖形描繪出邊與頂點之間保持的相互關系。我們常常把一個圖的圖形當作這個抽象圖自身.并稱圖形的點為頂點，圖形的線為邊。圖論中大多數(shù)概念是根據(jù)圖的表示形式提出的，例如：頂點、邊、多重邊、環(huán)、路、圈、樹等。第十頁，共一百三十一頁，編輯于2023年，星期五幾何實現(xiàn)圖例在一個圖的幾何實現(xiàn)中，兩條邊的交點可能不是圖的頂點。例如下圖中，它共有4個頂點，6條邊；而e

3

與e

4的交點不是這個圖的頂點。第十一頁，共一百三十一頁，編輯于2023年，星期五平面圖一個圖稱為平面圖，如它有一個平面圖形，使得邊與邊僅在頂點相交。下圖就是一個平面圖。第十二頁，共一百三十一頁，編輯于2023年，星期五基本概念端點重合為一點的邊稱為環(huán)。連接同一對頂點的多條邊稱為多重邊。在右圖中，e5

是一個環(huán)，e1

與e2

是多重邊，v1和e1,e2,e3是關聯(lián)的，v1與v2,v3是鄰接的。第十三頁，共一百三十一頁，編輯于2023年，星期五鄰接矩陣設G是一個圖，G=(V(G),E(G))，定義圖G的鄰接矩陣A(G)=(aij)為m×m矩陣,

aij是頂點vi與邊vj相鄰接的邊數(shù)。其中第十四頁，共一百三十一頁，編輯于2023年，星期五關聯(lián)矩陣設G是一個圖，G=(V(G),E(G))定義圖G的關聯(lián)矩陣M=(mij)為m×n矩陣；其中mij是頂點vi與邊ej相關聯(lián)的次數(shù)，取值可能為0、1、2。第十五頁，共一百三十一頁，編輯于2023年，星期五注圖的鄰接矩陣比它的關聯(lián)矩陣小的多，因而圖常常以其鄰接矩陣的形式存貯與計算機中。關聯(lián)矩陣和鄰接矩陣統(tǒng)稱圖的矩陣表示。第十六頁，共一百三十一頁，編輯于2023年，星期五頂點的度設G是一個圖，G=(V(G),E(G))，定義圖G的頂點v的度為與頂點v相關聯(lián)的邊數(shù)，記作d(v)

例稱度為奇數(shù)的頂點為奇點；稱度為偶數(shù)的頂點為偶點。第十七頁，共一百三十一頁，編輯于2023年，星期五例22222224+3+3+4=14=2×7第十八頁，共一百三十一頁，編輯于2023年，星期五關聯(lián)矩陣性質(zhì)圖G的關聯(lián)矩陣M=(mij)為m×n矩陣；則每行元素之和等于相應頂點的度；每列元素之和等于2。因此，圖G的關聯(lián)矩陣M所有元素之和既等于所有頂點的度之和，又等于邊數(shù)的2倍。定理設G是一個圖，則第十九頁，共一百三十一頁，編輯于2023年，星期五推論圖中奇點的數(shù)目為偶數(shù)。證明記第二十頁，共一百三十一頁，編輯于2023年，星期五簡單圖一個圖稱為簡單圖，如果它既沒有環(huán)也沒有多重邊。下圖是簡單圖。本書只限于討論有限簡單圖，即頂點集與邊集都是有限集的圖。u1u2u3u4f1f2f6f3f5f4只有一個頂點的圖稱為平凡圖；邊集是空集的圖稱為空圖。第二十一頁，共一百三十一頁，編輯于2023年，星期五同構(gòu)稱G和H是同構(gòu)的，記為，使得給定兩個圖如果存在兩個一一對應第二十二頁，共一百三十一頁，編輯于2023年，星期五同構(gòu)圖例圖G與圖H是同構(gòu)的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4第二十三頁，共一百三十一頁，編輯于2023年，星期五完全圖Kn完全圖是每一對不同頂點都恰有一邊的簡單圖；具有n個頂點的完全圖記為Kn.K5第二十四頁，共一百三十一頁，編輯于2023年，星期五二分圖二分圖是一個簡單圖，其頂點集合可分劃成兩個子集X與Y，使得每條邊的一個端點在X，另一個端點在Y;(X,Y)也稱為圖的二分劃。x1x2x3y1y2y3第二十五頁，共一百三十一頁，編輯于2023年，星期五完全二分圖完全二分圖是具有二分劃(X,Y)的二分圖，并且X的每個頂點與Y的每個頂點都相連；記為Km,n，其中K3,3第二十六頁，共一百三十一頁，編輯于2023年，星期五特殊圖例K5K3,3都是極小的非平面圖第二十七頁，共一百三十一頁，編輯于2023年，星期五子圖稱圖H是圖G的子圖，圖G及其基本圖稱H是G的支撐子圖，如果稱H是G的真子圖，若如果表示關聯(lián)函數(shù)記為在H的限制。第二十八頁，共一百三十一頁，編輯于2023年，星期五頂點導出子圖設W是圖G的一個非空頂點子集,以W為頂點集，以二端點均在W中的邊的全體為邊集的子圖稱為由W導出的G的子圖，簡稱導出子圖，記為G[W]。導出子圖G[V-w]記為G-W，即它是從G中刪除W中頂點以及與這些頂點相關聯(lián)的邊所得到的子圖。如果W僅含一個頂點v，則把簡記為。第二十九頁，共一百三十一頁，編輯于2023年，星期五邊導出子圖設F是圖G的非空邊子集，以F為邊集，以F中邊的端點全體為頂點集所構(gòu)成的子圖稱為由F導出的G的子圖，簡稱G的邊導出子圖。記為G[F]。記G-F表示以E(G)\F為邊集的G的支撐子圖，它是從G中刪除F中的邊所得到的子圖。如F={e}，則記。第三十頁，共一百三十一頁，編輯于2023年，星期五子圖圖例v1v2v3v4v5e1e3e2Gv1v2v3v4v5G的支撐子圖G-{e1,e

2,e

3}第三十一頁，共一百三十一頁，編輯于2023年，星期五子圖圖例2v2v3v4e2G-{v

1,v

5}v1v2v5G[v

1,v

2,v

5]v1v2v3v4e1e3e2G[e1,e

2,e

3]v1v2v3v4v5e1e3e2G第三十二頁，共一百三十一頁，編輯于2023年，星期五途徑頂點vk叫W的終點，頂點v0

稱為W的起點，頂點vi

叫W的內(nèi)部頂點，整數(shù)k稱為W的長度。在簡單圖中，徑可由頂點序列表示。圖G的一個有限的點邊交錯序列稱為從v0到vk的途徑。其中vi與vi+1是邊ei的頂點;第三十三頁，共一百三十一頁，編輯于2023年，星期五路、鏈如果徑W的邊不相同，則稱W為一條鏈，如果W頂點互不相同，則稱W是一條路。鏈長是W中邊的個數(shù)k。記路長uvwxyabdefgh路：xcwhyeuav鏈：wcxdyhwbvgyc第三十四頁，共一百三十一頁，編輯于2023年，星期五圈(回路)如果途徑W的起點和終點相同且有正長度，則稱它是一個閉途徑；如果一條閉鏈的頂點互不相同，則稱它是一個圈（或回路）。稱一個圈是偶圈（奇圈），如果它的圈長是偶數(shù)（奇數(shù)）。圈：uavbwhyeuuvwxyabdefghc第三十五頁，共一百三十一頁，編輯于2023年，星期五定理一個圖是二分圖當且僅當圖中不存在奇圈。第三十六頁，共一百三十一頁，編輯于2023年，星期五Euler圈Euler圈是指過所有邊一次且恰好一次的閉途徑。Euler鏈是指過所有邊一次且恰好一次的鏈。Euler鏈:ydxcwheuavfygvbwuvwxyabdefghc第三十七頁，共一百三十一頁，編輯于2023年，星期五圖例下例給出了一個圖的徑，鏈和路。徑：uavfyfvgyhwbv鏈：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler鏈:ydxcwheuavfygvbwuvwxyabdefghc第三十八頁，共一百三十一頁，編輯于2023年，星期五Euler型定理定理2設G是連通圈，則G是Euler型的充要條件是G沒有奇次數(shù)的頂點。推論1設G是一個連通圖，則G有Euler鏈當且僅當G最多有兩個奇數(shù)次數(shù)的頂點。第三十九頁，共一百三十一頁，編輯于2023年，星期五連通性圖G稱為連通的，如果在G的任意兩個頂點u和v中存在一條(u,v)路。不連通圖至少有兩個連通分支。兩點頂點u和v等價當且僅當u和v中存在一條(u,v)路。ω表示G的連通分支數(shù)。第四十頁，共一百三十一頁，編輯于2023年，星期五§10.2樹樹（tree）是一個不包含圈的簡單連通圖。具有k個連通分支的不包含圈的圖稱為k--樹，或森林。第四十一頁，共一百三十一頁，編輯于2023年，星期五下圖列出了具有六個頂點的不同構(gòu)的樹。從中可以看出，圖中的每棵樹都只有5條邊，并且至少有2個頂點的次數(shù)是1。第四十二頁，共一百三十一頁，編輯于2023年，星期五性質(zhì)1設G是一棵樹，則：

G中任意兩點均有唯一的路連接。2G的邊數(shù)等于頂點數(shù)減1，即3若G不是平凡圖，則G至少有兩個次數(shù)為1的頂點。第四十三頁，共一百三十一頁，編輯于2023年，星期五定理1設G是一個簡單圖，，則下列六個命題是等價的。G是一棵樹。無圈且m=n-1。 G連通且m=n-1。G連通并且每條邊都是割邊。G中任意兩點都有唯一的路相連。G無圈，但在任意一對不相鄰的頂點之間加連一條邊，則構(gòu)成唯一的一個圈。第四十四頁，共一百三十一頁，編輯于2023年，星期五支撐樹圖G的支撐樹是G的支撐子圖，并且是一棵樹。每個連通圖都有支撐樹支撐樹也稱為連通圖的極小連通支撐子圖。很顯然，一個連通圖只要本身不是一棵樹，它的支撐樹就不止一個。第四十五頁，共一百三十一頁，編輯于2023年，星期五定理定理4設T1

和T2

是G的兩個支撐樹，令則T1

經(jīng)過k次迭代后可得到T2。定理2設G是一個連通圖，T是G的一棵支撐樹，e是G的一條不屬于T的邊，則T+e含有G的唯一圈。定理3設T是連通圖G的一棵支撐樹，e是T的任意一條邊，則：T（1）不包含G的割集（2）包含G的唯一的割集。第四十六頁，共一百三十一頁，編輯于2023年，星期五最小樹定理5設T是G的一個支撐樹，則T是G的最小樹的充分必要條件為對任意邊設G是一個賦權(quán)圖，T為G的一個支撐樹。定義T的權(quán)為：G中權(quán)最小的支撐樹稱為G的最小樹。第四十七頁，共一百三十一頁，編輯于2023年，星期五定理6設T是G的支撐樹，則T是G的最小樹的充分必要條件為對任意邊，其中為G的唯一割集。第四十八頁，共一百三十一頁，編輯于2023年，星期五最小樹算法-1-貪心算法Kruskal在1965年提出一種求最小樹的所謂貪心算法。算法步驟如下Step0把邊按權(quán)的大小從小到大排列得：置Step1若，則停，此時G[S]即為所求的最小樹；否則，轉(zhuǎn)向Step2。Step2如果G[S+{ej}]不構(gòu)成回路，則令轉(zhuǎn)向Step1；否則，令j=j+1轉(zhuǎn)向Step2。第四十九頁，共一百三十一頁，編輯于2023年，星期五算例圖7-18展示了利用Kruskal算法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v5v312244342圖7-18第五十頁，共一百三十一頁，編輯于2023年，星期五v1v2v4v5v312244342v1v2v4v5v312244342圖7-18-1第五十一頁，共一百三十一頁，編輯于2023年，星期五評注Kruskal算法的總計算量為，有效性不太好。求最小樹的一個好的算法是Dijkstra于1959年提出的，算法的實質(zhì)是在圖的個獨立割集中，取每個割集的一條極小邊來構(gòu)成最小樹。第五十二頁，共一百三十一頁，編輯于2023年，星期五最小樹算法-2-Dijkstra算法Step0置Step1取置Step2若，則停止；否則，置，返回Step1第五十三頁，共一百三十一頁，編輯于2023年，星期五算例2圖7-19展示了利用Dijkstra算法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v5v312244342圖7-19第五十四頁，共一百三十一頁，編輯于2023年，星期五利用Dijkstra算法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v5v312244342圖7-19-1第五十五頁，共一百三十一頁，編輯于2023年，星期五破圈法是Dijkstra算法的對偶算法。最適合于圖上作業(yè)。尤其是當圖的頂點數(shù)和邊數(shù)比較大時，可以在各個局部進行。

Step1若G不含圈，則停止；否則在G中找一個圈C，取圈C的一條邊e

，滿足最小樹算法-3-破圈法Step2：置G=G-e，返回Step1。

利用破圈法求圖7-19的最小樹的過程如圖7-20所示。第五十六頁，共一百三十一頁，編輯于2023年，星期五算例3圖7-20展示了利用破圈法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v5v312244342圖7-20第五十七頁，共一百三十一頁，編輯于2023年，星期五v1v2v4v5v312244342v1v2v4v5v312244342圖7-20-1第五十八頁，共一百三十一頁，編輯于2023年，星期五評注上述算法都可以在圖上進行。為了便于計算機計算，下面介紹Dijkstra的表上算法。給定一個賦權(quán)圖G，可以相應地定義一個鄰接矩陣A=(wij)，其中wij是連接頂點vi和vj的權(quán);若vivj不是G的邊，則令wij

等于無窮大。第五十九頁，共一百三十一頁，編輯于2023年，星期五Step0：畫掉第一列的所有元素（例如打上×），并在第一行的每個元素下面畫一橫線。Step1：在畫橫線的元素中找一個最小的wij

，用圓圈起來，把第j列其他元素畫掉，并把第j行沒有畫掉的元素畫上橫線。Step2：如果還有沒有圈起來和沒有畫掉的元素，則返回Step1；否則，結(jié)束。這時圈起來的元素代表最小樹的邊，所有圈起來的元素之和就是最小樹的權(quán)。最小樹算法-4-表上作業(yè)法第六十頁，共一百三十一頁，編輯于2023年，星期五算例用表上作業(yè)法求圖7-19的最小樹的過程為：最小對的權(quán)=1+2+3+2=8。v1v2v4v5v312244342第六十一頁，共一百三十一頁，編輯于2023年，星期五第六十二頁，共一百三十一頁，編輯于2023年，星期五最小連接問題作為最小樹的應用問題之一是所謂的連接問題：欲建造一個連接若干城鎮(zhèn)（礦區(qū)或工業(yè)區(qū)）的鐵路網(wǎng)，給定城鎮(zhèn)i和j之間直通線路的造價為cij，試設計一個總造價最小的鐵路運輸圖。把每個城鎮(zhèn)看作是具有權(quán)cij的賦權(quán)圖G的一個頂點。顯然連接問題可以表述成：在賦權(quán)圖G中，求出具有最小權(quán)的支撐樹。第六十三頁，共一百三十一頁，編輯于2023年，星期五§10.3最短路問題Dijkstra算法求任意兩點的最短路算法-Floyd算法求帶負權(quán)網(wǎng)絡圖的最短路的算法用線性規(guī)劃求最短路第六十四頁，共一百三十一頁，編輯于2023年，星期五賦權(quán)圖給定賦權(quán)圖的一個子圖H，定義H的權(quán)為H的所有邊權(quán)的總和。對圖G的每條邊e，賦予一實數(shù)ω(e)，稱為邊e的權(quán)，可得一賦權(quán)圖。SDBTCEA712244731555第六十五頁，共一百三十一頁，編輯于2023年，星期五賦權(quán)圖中一條路的權(quán)稱為路長。在一個賦權(quán)圖G上，給定兩個頂點u和v，所謂u和

v最短路是指所有連接頂點u和v

的路中路長最短的路；u和v最短路的路長也稱為u和v的距離。SDBTCEA712244731555如何求從u到v的最短路的長？第六十六頁，共一百三十一頁，編輯于2023年，星期五Dijkstra算法的基本思想：(1)u0u1P設S是V的真子集，如果是從u0

到的最短路，則，并且P的段是最短的路，所以第六十七頁，共一百三十一頁，編輯于2023年，星期五算法標號令dij表示連接頂點vi與頂點vj邊上的權(quán)，即(1)公式（1）是Dijkstra算法的基礎。第六十八頁，共一百三十一頁，編輯于2023年，星期五定義結(jié)點vj

的標號為始點的標號為[0,--],表明這個點前面沒有點。結(jié)點vj

的標號分為兩種：臨時性標號和永久性標號。如果找到一條更短的路，臨時性標號即被修改，如果找不到一條更短的路，臨時性標號即被改為永久性標號。第六十九頁，共一百三十一頁，編輯于2023年，星期五Step0令始點的標號為[0,--].令i=1

Stepi

(a)對于由結(jié)點i可達的還沒有永久性標號的結(jié)點j，計算其臨時性標號[li+dij,i]（dij>0）.如果j

已經(jīng)通過另一個結(jié)點k標號為[lj,k]且li+dij<lj,則用[li+dij,i]取代[lj,k]。(b)如果所有的結(jié)點都是永久性標號，停止。否則選擇最小的臨時性標號[lr,s]。令i=r

，返回Stepi.第七十頁，共一百三十一頁，編輯于2023年，星期五計算實例求連接S、T的最短路SDBTCEA712244731555第七十一頁，共一百三十一頁，編輯于2023年，星期五SDBTCEA7122447315550第七十二頁，共一百三十一頁，編輯于2023年，星期五SDBTCEA71224473155505，s4，s2，s2，s第七十三頁，共一百三十一頁，編輯于2023年，星期五SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s第七十四頁，共一百三十一頁，編輯于2023年，星期五SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C第七十五頁，共一百三十一頁，編輯于2023年，星期五SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B第七十六頁，共一百三十一頁，編輯于2023年，星期五SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E第七十七頁，共一百三十一頁，編輯于2023年，星期五lST

=13;S-T最短路為SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第七十八頁，共一百三十一頁，編輯于2023年，星期五實例評述Dijkstra算法不僅找到了所求最短路，而且找到了從S點到其他所有頂點的最短路；這些最短路構(gòu)成了圖的一個連通無圈的支撐子圖，即圖的一個支撐樹。SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第七十九頁，共一百三十一頁，編輯于2023年，星期五注:Dijkstra算法只適用于所有wij≥0的情形，當賦權(quán)有向圖中存在負權(quán)時，算法失效。如v1v2v312-3用Dijkstra算法可以得出從v1到v2的最短路的權(quán)是1，但實際上從v1到v2的最短路是（v1，v3

，v2），權(quán)是-1。第八十頁，共一百三十一頁，編輯于2023年，星期五下面介紹具有負權(quán)賦權(quán)有向圖D的最短路的算法。不妨假設從任一點vi到任一點vj都有一條?。ㄈ绻贒中，（vi，vj

）A，則添加弧（vi，vj

）令wij=+∞）。顯然，從vs到任一點vj的最短路總是從vs出發(fā)到某個點vi，再沿（vi，vj）到vj的，由前面的結(jié)論可知，從vs到vi的這條路必定是從vs到vi的最短路，所以d（vs，vj）必滿足如下方程：第八十一頁，共一百三十一頁，編輯于2023年，星期五第八十二頁，共一百三十一頁，編輯于2023年，星期五6-1-3-283-52-111-1217-3-5例：求v1到各點的最短路。第八十三頁，共一百三十一頁，編輯于2023年，星期五wijv1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v610-17-1-1-1v7-1-305-5-5v8-5066第八十四頁，共一百三十一頁，編輯于2023年，星期五

例一個連接11個城鎮(zhèn)的交通圖以及城市u與v之間的一條最短路。（粗線表示）uv第八十五頁，共一百三十一頁，編輯于2023年，星期五uv第八十六頁，共一百三十一頁，編輯于2023年，星期五求任意兩點的最短路算法-Floyd算法這種算法用一個n階方陣來表示一個n-結(jié)點網(wǎng)絡.矩陣中的(i,j)-元dij

表示從i

到j邊上的權(quán),即第八十七頁，共一百三十一頁，編輯于2023年，星期五ijkFloyd’salgorithm的基本思想：給定結(jié)點i,j

和k

，若有如下三角形，且，則從i經(jīng)過k到j

比直接到j所經(jīng)過路線短。此時用i→k→j

代替i→j最好.------三角形運算第八十八頁，共一百三十一頁，編輯于2023年，星期五第八十九頁，共一百三十一頁，編輯于2023年，星期五12453354615101234512345－310∞∞3－∞5∞10∞－615∞56－4∞∞∞4－1234512345－23451－34512－45123－51234－第九十頁，共一百三十一頁，編輯于2023年，星期五1234512345－310∞∞3－∞5∞10∞－615∞56－4∞∞∞4－1234512345－23451－34512－45123－51234－1234512345－310∞∞3－135∞1013－615∞56－4∞∞∞4－1234512345－23451－14511－45123－51234－第九十一頁，共一百三十一頁，編輯于2023年，星期五1234512345－310∞∞3－135∞1013－615∞56－4∞∞∞4－1234512345－23451－14511－45123－51234－12345－3108∞3－135∞1013－615856－4∞∞∞4－1234512345－23251－14511－45223－51234－12345第九十二頁，共一百三十一頁，編輯于2023年，星期五12345－3108∞3－135∞1013－615856－4∞∞∞4－1234512345－23251－14511－45223－51234－12345－3108253－135281013－615856－4∞∞∞4－1234512345－23231－14311－45223－51234－1234512345第九十三頁，共一百三十一頁，編輯于2023年，星期五12345－3108253－135281013－615856－4∞∞∞4－1234512345－23231－14311－45223－51234－1234512345－3108123－11591011－610856－4129104－1234512345－23241－44414－44223－54444－12345第九十四頁，共一百三十一頁，編輯于2023年，星期五12345－3108123－11591011－610856－4129104－1234512345－23241－44414－44223－54444－1234512453354615101→2→4→5第九十五頁，共一百三十一頁，編輯于2023年，星期五用線性規(guī)劃求最短路124531001550106030求從1到2的最短路20第九十六頁，共一百三十一頁，編輯于2023年，星期五§10.4網(wǎng)絡最大流問題第九十七頁，共一百三十一頁，編輯于2023年，星期五vsv1v3v4v2vt322223111網(wǎng)絡流圖設D=(V,A,W)

是一個有向網(wǎng)絡。vs是網(wǎng)絡的源點，vt是網(wǎng)絡的匯點。弧上的數(shù)字是允許通過的最大流量。第九十八頁，共一百三十一頁，編輯于2023年，星期五可行流設f是定義在弧集A上的一個函數(shù)，如果對所有弧

a

成立并且對所有中間頂點

v

成立其中，f+(v)是流出v

的流量，f

-(v)是流入v的流量。則稱f

是網(wǎng)絡D上的一個可行流。2,1vsv1v3v4v2vt3,12,12,22,13,21,01,01,1---容量限制----守恒條件第九十九頁，共一百三十一頁，編輯于2023年，星期五流值對于源點vs和匯點vt

，流出源點vs的流量等于流入?yún)R點vt的流量，稱之為流

f

的值，記為valf

。即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1valf=3第一百頁，共一百三十一頁，編輯于2023年，星期五最大流網(wǎng)絡最大流是指給定網(wǎng)絡上的流值最大的一個可行流。尋找給定網(wǎng)絡的最大流及其有效算法是網(wǎng)絡規(guī)劃的一個重要問題。Ford與Fulkerson在1957年提出一個求解網(wǎng)絡最大流問題的算法，稱為Ford—Fulkerson算法。第一百零一頁，共一百三十一頁，編輯于2023年，星期五割集設S是網(wǎng)絡的頂點子集，且割集的容量定義為最小割是指容量最小的割。定義D的一個割集，簡稱割為vsv1v3v4v2vt322223111第一百零二頁，共一百三十一頁，編輯于2023年，星期五定理1對于網(wǎng)絡的任意流f和割成立證明由定義可知第一百零三頁，共一百三十一頁，編輯于2023年，星期五推論1對于網(wǎng)絡的任意流f

和割，成立vsv1v3v4v2vt322223111第一百零四頁，共一百三十一頁，編輯于2023年，星期五注：推論2的逆命題也成立，即推論中的等式永遠成立。稱為最大流最小割定理，是網(wǎng)絡理論的一個重要定理。則f

是最大流，K是最小割。如果成立推論2

設f是網(wǎng)絡的一個可行流，

是網(wǎng)絡的一個割，第一百零五頁，共一百三十一頁，編輯于2023年，星期五鏈、正向弧、反向弧設P是網(wǎng)絡D的一條鏈，則P中的弧可分為兩類：正向弧—弧的方向與P的走向一致；記為P+。反向弧—弧的方向與P的走向相反;記為P-。網(wǎng)絡D的連接源點vs和匯點vt的路。vsv1v3v4v2vt322223111第一百零六頁，共一百三十一頁，編輯于2023年，星期五增廣鏈設P是網(wǎng)絡D的一條連接源點vs和匯點vt的鏈，f

是網(wǎng)絡D上的一個可行流.如果P的每一正向弧都是不飽和弧，而P的每一反向弧的流量都為正；則稱P是網(wǎng)絡D的關于可行流f

的一條可增廣鏈。簡稱增廣鏈。可增廣鏈上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,21,01,11,0第一百零七頁，共一百三十一頁，編輯于2023年，星期五定理2設f

是網(wǎng)絡D上的一個可行流，則f

是一個最大流當且僅當網(wǎng)絡D不存在f

的增廣鏈。證明（必要性）設f

是一個最大流，假如D中存在f

的增廣鏈P,則可以得到一個流值更大的流f

1,使得構(gòu)造過程如下：其中第一百零八頁，共一百三十一頁，編輯于2023年，星期五證明充分性設網(wǎng)絡D不存在f

的增廣鏈。定義S如下：從而是D的割集，進而可得

中的弧都是飽和弧，而中的弧都是0流弧，否則將產(chǎn)生網(wǎng)絡D

的一條增廣鏈。因此，f的流值等于割集

的割量，所以，

f是一個最大流。第一百零九頁，共一百三十一頁，編輯于2023年，星期五定理3在任何網(wǎng)絡流圖中，最大流的值等于最小割的容量。（最大流最小割定理）第一百一十頁，共一百三十一頁，編輯于2023年，星期五Ford—Fulkerson算法Ford—Fulkerson算法的基本思想是從任意一個可行流出發(fā)，尋找流的增廣鏈，并在這條增廣鏈上調(diào)整流值，進而得到一個新可行流，依次進行下去，直到一個最大流為止。定理的證明過程蘊涵著最大流算法第一百一十一頁，共一百三十一頁，編輯于2023年，星期五算例求下面網(wǎng)絡的最大流vsv1v3v4v2vt852879665圖4.23第一百一十二頁，共一百三十一頁，編輯于2023年，星期五初始0流先給網(wǎng)絡賦一個初始0流f0

圖4.2-1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0第一百一十三頁，共一百三十一頁，編輯于2023年，星期五(+vs,8)(+vs,2)(-,∞)尋找增廣鏈1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0第一百一十四頁，共一百三十一頁，編輯于2023年，星期五vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,∞)(+v1,5)(+v3,2)尋找增廣鏈2第一百一十五頁，共一百三十一頁，編輯于2023年，星期五vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,∞)(+v1,5)(+v3,2)(+v2,5)尋找增廣鏈3第一百一十六頁，共一百三十一頁，編輯于2023年，星期五尋找增廣鏈4找到流f0

的增廣鏈P0=vsv1v2vt.vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,∞)(+v1,5)(+v3,2)(+v2,5)增量θ=5.第一百一十七頁，共一百三十一頁，編輯于2023年，星期五調(diào)整流值2調(diào)整流值得流值為5的新可行流f

1

，vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0第一百一十八頁，共一百三十一頁，編輯于2023年，星期五vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,∞)第一百一十九頁，共一百三十一頁，編輯于2023年，星期五vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,∞)(+v3,2)(+v3,2)第一百二十頁，共一百三十一頁，編輯于2023年，星期五vs