運(yùn)籌學(xué)課件第8章-圖與網(wǎng)絡(luò)分析

運(yùn)籌學(xué)課件第8章-圖與網(wǎng)絡(luò)分析第一頁，共60頁。第8章圖與網(wǎng)絡(luò)分析第二頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

引言

十八世紀(jì)的哥尼斯堡城中流過一條河（普雷.格爾河），河上有7座橋連接著河的兩岸和河中的兩個小島。當(dāng)時那里的人們熱衷于這樣一個游戲：一個游者怎樣才能一次連續(xù)走過這7座橋，回到原出發(fā)點(diǎn)，而每座橋只允許走一次。沒有人想出走法，又無法說明走法不存在，這就是著名的“哥尼斯堡7橋”難題。ABCD第三頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

引言“哥尼斯堡7橋”難題最終在1736年由數(shù)學(xué)家Euler的一篇論文給予了完滿的解決，這是圖論的第一篇論文。在后來的兩百年間圖論的發(fā)展是緩慢的，直到1936年匈牙利數(shù)學(xué)家O.K?nig寫出了圖論的第一本專著《有限圖與無限圖的理論》。在圖論的發(fā)展過程中還有兩位著名科學(xué)家值得一提，他們是克?；舴蚝蛣P萊?？讼；舴蛟谘芯侩娋W(wǎng)絡(luò)時對圖的獨(dú)立回路理論作出了重要的貢獻(xiàn)，而化學(xué)家凱萊在對碳?xì)浠衔锏耐之悩?gòu)體的數(shù)量進(jìn)行計數(shù)時推動了圖論中樹的計數(shù)問題的研究。圖論的歷史上最具有傳奇色彩的問題也許要數(shù)著名的“四色猜想”了——?dú)v史上許許多多數(shù)學(xué)猜想之一。它描述對一張地圖著色的問題，曾經(jīng)有一位數(shù)學(xué)家這樣說：“對于這個問題，一位數(shù)學(xué)家可以用不到五分鐘的時間向馬路上任何一位行人講述清楚它，然后，兩人都明白這一問題，但是，兩人都無能為力。”幸運(yùn)的是在1970‘s終于由美國的兩位數(shù)學(xué)家借助大型計算機(jī)將其證明了。第四頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念

圖論與網(wǎng)絡(luò)分析理論所研究的問題十分廣泛，內(nèi)容極其豐富。正如一位數(shù)學(xué)家所說：“可以說，圖論為任何一個包含了某種二元關(guān)系的系統(tǒng)提供了一種分析和描述的模型。”下面我們來看一個案例——

國慶大假期間旅游非?；鸨瑱C(jī)票早已訂購一空。成都一家旅行社由于信譽(yù)好、服務(wù)好，所策劃的國慶首都游的行情看好，要求參加的游客眾多，游客甚至不惜多花機(jī)票錢暫轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急電傳他在全國各地的辦事處要求協(xié)助解決此問題。很快，各辦事處將其已訂購機(jī)票的情況傳到了總社。根據(jù)此資料，總社要作出計劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機(jī)。下面是各辦事處已訂購機(jī)票的詳細(xì)情況表：第五頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念各辦事處已訂購機(jī)票情況表成都重慶武漢上海西安鄭州沈陽昆明廣州北京成都重慶武漢上海西安鄭州沈陽昆明廣州北京105158121030106152510158861481881082610第六頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念

將此問題通過圖的模型描述：下圖中，點(diǎn)——各城市，帶箭頭連線——從箭尾城市到箭頭城市已訂購有機(jī)票，帶箭頭連線旁的數(shù)字——機(jī)票數(shù)量。成重武昆上廣西鄭沈京8鄭州辦事處已訂有的到北京的機(jī)票數(shù)量。第七頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念一、圖及其分類和術(shù)語

1、圖論中所研究的圖并非幾何學(xué)中的圖，也不是繪畫中的圖。在這里我們所關(guān)心的僅僅是圖中有多少個點(diǎn)，點(diǎn)與點(diǎn)之間有無線來連接，也就是說我們研究的是某個系統(tǒng)中的元素——點(diǎn)，以及這些元素之間的某種關(guān)系——連線。定義：圖——一個圖G是一個有序二元組（V，E），記為G=（V，E）其中（1）V是一個有限非空的集合，其元素稱為G的點(diǎn)或頂點(diǎn)，而稱V為G的點(diǎn)集V={v1，v2，···，vn}；（2）E是V中元素的無序?qū)?vi，vj)所構(gòu)成的一個集合，其元素稱為G的邊，一般表示為e=(vi，vj)，而稱E是G的邊集。邊（無向邊）——沒有方向的連線?。ㄓ邢蜻叄獛в蟹较虻倪B線無向圖——有向圖——簡單圖——多重圖——完全圖——二部圖（偶圖，雙圖）——第八頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念子圖——真子圖——生成子圖——點(diǎn)生成子圖——邊生成子圖——點(diǎn)的次——奇次點(diǎn)——偶次點(diǎn)——鏈——圈——路——回路——賦權(quán)圖——2、連通圖在眾多各類圖中有一類在實(shí)際應(yīng)用中占有重要地位的圖連通圖——在圖中，任意兩點(diǎn)間至少存在著一條鏈連通圖不連通圖第九頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念3、圖與矩陣在圖與網(wǎng)絡(luò)分析的應(yīng)用中，將面臨一個問題——如何分析、計算一個較大型的網(wǎng)絡(luò)，這當(dāng)然需借助快速的計算工具——計算機(jī)。那么，如何將一個圖表示在計算機(jī)中，或者，如何在計算機(jī)中存儲一個圖呢？現(xiàn)在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有——鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。鄰接矩陣——對于圖G=（V，E），|V|=n，|E|=m，有nn階方矩陣A=（aij）nn，其中

aij=k當(dāng)且僅當(dāng)vi與vj之間有條邊時

0其它第十頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念鄰接矩陣A=（aij）nn=0100100010101000010010020000011011100001000100100001110000201000v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8第十一頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

圖與網(wǎng)絡(luò)的基本概念關(guān)聯(lián)矩陣——對于圖G=（V，E），|V|=n，|E|=m，有mn階矩陣M=（mij）mn，其中

mij=2當(dāng)且僅當(dāng)

vi是邊ej

的兩個端點(diǎn)1當(dāng)且僅當(dāng)

vi是邊ej

的一個端點(diǎn)例——0其它v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8M=（mij）=101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12第十二頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最小樹問題二、樹（Tree）和最小樹樹是圖論中一類重要的圖，實(shí)際中有很多系統(tǒng)的結(jié)構(gòu)都是樹。樹——連通且不含圈的圖，簡記為T。下面的說法是等價的：T是一個樹。T無圈，且m=n-1。T連通，且m=n-1。T無圈，但每加一條新的邊即出現(xiàn)唯一一個圈。T連通，但每舍去一條邊就不連通。T中任意兩點(diǎn)，有唯一的一條鏈相連。T是邊數(shù)最少的連通圖。圖的生成樹——若G圖的一個點(diǎn)生成子圖是一個樹，則稱此樹是G圖的一個生成樹。樹的權(quán)——若Tk是加權(quán)圖G的一棵樹，則樹T的全部邊的權(quán)之和稱為樹Tk的權(quán)，記為（Tk

）=（e）；eTk最小樹——T*是加權(quán)圖G的一棵最小樹，即（T*）=min{(Tk)}k第十三頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最小樹問題破圈法，避圈法求生成樹：圖G生成樹T生成樹T第十四頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最小樹問題破圈法，避圈法求最小生成樹：圖G生成樹T生成樹T15424531344215121231211212312112第十五頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最短路問題三、路（Path）和最短路最短路問題是網(wǎng)絡(luò)分析中應(yīng)用最廣泛的問題之一。盡管前面介紹了用動態(tài)規(guī)劃方法求解，但有時卻較困難，此時圖論的方法卻十分有效。最短路問題的一般描述：G=（V，E）是連通圖，圖中各邊（vi，vj）有權(quán)l(xiāng)ij（=表示vi，vj間無邊），vs

、vt為圖中任意兩指定點(diǎn)，求一條路

μ，使其是從vs到vt的所有路中最短（路中各邊的權(quán)之和最小）的一條路。即L（

μ）=minlij（vi，vj）

μ第十六頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最短路問題E.W.Dijkstra算法（標(biāo)號算法）算法基本思路分析：（逐步向外搜索）52165828997221210∞∞∞∞∞∞∞∞X（P標(biāo)號）Y（T標(biāo)號）起點(diǎn)到該點(diǎn)的最短距離起點(diǎn)到該點(diǎn)的最短距離的上界2527511121210575667991010633第十七頁，共60頁。人、狼、羊、草渡河游戲一個人帶著一條狼、一只羊、一筐白菜過河蛤由于船太小，人一次只能帶一樣?xùn)|西乘船過河。狼和羊、羊和白菜不能單獨(dú)留在同岸，否則羊或白菜會被吃掉。人——M（Man），狼——W（Wolf），羊——G（Goat），草——H（Hay）。點(diǎn)——vi

表示河岸的狀態(tài)，邊——ek

表示由狀態(tài)vi

經(jīng)一次渡河到狀態(tài)vj

，權(quán)——邊ek上的權(quán)定為1。我們可以得到下面的加權(quán)有向圖：第十八頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最短路問題v1，u1=（M，W，G，H）；v2，u2=（M，W，G）；v3，u3=（M，W，H）；v4，u4=（M，G，H）；v5，u5=（M，G）。此游戲轉(zhuǎn)化為在下面的二部圖中求從v1到u1的最短路問題。v1v2v3v4v5u5u4u3u2u1第十九頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最短路問題

在E.W.Dijkstra算法中必須滿足一個條件——在圖G中所有邊的權(quán)l(xiāng)ij≥0。若在圖G中存在有負(fù)權(quán)邊（當(dāng)然，這種情形只針對有向圖而言）時必須對E.W.Dijkstra算法加以修改——稱為修改的E.W.Dijkstra算法。第二十頁，共60頁。2、情況二：wij≤0設(shè)從V1到Vj(j=1,2,…,t)的最短路長為P1jV1到Vj無任何中間點(diǎn)P1j（1）=wijV1到Vj中間最多經(jīng)過一個點(diǎn)

P1j（2）=min{P1j（1）+wij}V1到Vj中間最多經(jīng)過兩個點(diǎn)

P1j（3）=min{P1j（2）+wij}…….V1到Vj中間最多經(jīng)過t-2個點(diǎn)

P1j（t-1）=min{P1j（t-2）+wij}終止原則：1）當(dāng)P1j（k）=P1j（k+1）可停止，最短路P1j*=P1j（k）2）當(dāng)P1j（t-1）=P1j（t-2）時，再多迭代一次P1j（t），若P1j（t）

=P1j（t-1），則原問題無解，存在負(fù)回路。第二十一頁，共60頁。

例：求下圖所示有向圖中從v1到各點(diǎn)的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第二十二頁，共60頁。

wijd(t)(v1,vj)v1v2v3v4v5v6v7v8v1v2v3

v4v5v6v7v8025-30-2406400-30720320t=1t=2t=3t=4t=5t=6025-3020-3611020-36615020-3361410020-336910020-336910說明：表中空格處為+。4第二十三頁，共60頁。例設(shè)備更新問題制訂一設(shè)備更新問題，使得總費(fèi)用最小

第1年第2年第3年第4年第5年購買費(fèi)1314161924

使用年數(shù)0-11-22-33-44-5

維修費(fèi)810131827

[解]設(shè)以vi(i=1,2,3,4,5)表示“第i年初購進(jìn)一臺新設(shè)備”這種狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi,

vj)表示“第i年初購置的一臺設(shè)備一直使用到第j年初”這一方案，以wij表示這一方案所需購置費(fèi)和維護(hù)費(fèi)之和。第二十四頁，共60頁。v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31,V1)(44,V1)(62,V1)(78,V3)第二十五頁，共60頁。這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就可歸結(jié)為從圖中找出一條從v1到v6的最短路問題。用Dijkstra標(biāo)號法，求得最短路為

v1v3v6

即第一年初購置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費(fèi)用最少，為78。第二十六頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

距離矩陣摹乘法Dijkstra算法比較簡單，但是，對于含有負(fù)權(quán)弧的網(wǎng)絡(luò)可能失效。這時，應(yīng)對算法加以修改，即所謂“修改的Dijkstra算法”。下面，介紹一種算法——距離矩陣摹乘法，它適用于任何網(wǎng)絡(luò)的最短路問題。例如——v1v3v4v2v6v534233-24411-16333第二十七頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

距離矩陣摹乘法1、網(wǎng)絡(luò)的距離矩陣設(shè)一網(wǎng)絡(luò)N中有n個點(diǎn)，其中任意兩點(diǎn)vi

與vj

之間都有一條邊(vi,vj)，其權(quán)數(shù)為wij>-∞。若vi

與vj

不相鄰，則虛設(shè)一條邊(vi,vj)，并令其權(quán)數(shù)wij=∞。距離矩陣W=（wij

）前例中的距離矩陣為W=v1v2v3v4v5v6v1032∞∞4v2∞04∞41v3∞∞0-16∞v43-2∞01∞v55∞∞∞03v6∞∞33∞0第二十八頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

距離矩陣摹乘法2、求各點(diǎn)至某點(diǎn)的最短路求vi（i=1,2,…,n）至某點(diǎn)vr

的最短路。令：dir(k)=vi走k步達(dá)到vr

的最短距離，i=1,2,…,n則有dir(1)=wir,i=1,2,…,ndir(k)=min｛wij+djr(k-1)

｝,i=1,2,…,n1≤j≤n令：dk=（d1r(k),d2r(k),…dnr(k),）T,k=1,2,…第二十九頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

距離矩陣摹乘法矩陣摹乘運(yùn)算法：

dk=Wdk-1,(k=2,3,…)當(dāng)

dk=dk-1,(k=2,3,…)則計算停止，dk

中的元素即為各點(diǎn)到

vr

的最短距離。第三十頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)中心和重心問題一、基本概念網(wǎng)絡(luò)最短距離矩陣

D=(dij)n×ndij——表示vi到vj的最短距離（1）網(wǎng)絡(luò)的中心令：d(vi)=maxdij,i=1,2,…,n若maxd(vi)=d(vk)1≤i≤n1≤j≤n則稱點(diǎn)vk

為網(wǎng)絡(luò)的中心。第三十一頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)中心和重心問題（2）網(wǎng)絡(luò)的重心設(shè)gi

為點(diǎn)vi

的權(quán)重（i=1,2,…,n），令：h(vj)=∑gidij,j=1,2,…,ni=1n若maxh(vj)=h(vr)1≤j≤n則稱點(diǎn)vr

為網(wǎng)絡(luò)的重心。第三十二頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)中心和重心問題二、應(yīng)用例——某地7個村鎮(zhèn)之間的現(xiàn)有交通道路如下圖，邊旁數(shù)值為各村鎮(zhèn)之間道路的長度，點(diǎn)旁數(shù)值為各村鎮(zhèn)的小學(xué)生人數(shù)?，F(xiàn)擬在某一村鎮(zhèn)建一商店和小學(xué)，試問：（1）商店應(yīng)該建在何村，能使各村都離它較近？（2）小學(xué)應(yīng)該建在何村，能使各村小學(xué)生總的行走路程最短？第三十三頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)中心和重心問題v1v3v4v5v6v7v2746435712324230404535252050距離人數(shù)第三十四頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)中心和重心問題（1）中心問題網(wǎng)絡(luò)最短距離矩陣如下：vjviD=(dij)d(vi)=maxdij123456710345781010230324577343055688452502355(min)57452013768563102871078532010j結(jié)論：商店應(yīng)該建在v4村。第三十五頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)中心和重心問題（2）重心問題vjvigidij123456710120160200280320400275075501001251753180135022522527036041506015006090150514080100400206062801752101053507075003504002501501000h(vj)13259201095870850(min)9251215結(jié)論：小學(xué)應(yīng)該建在v5村。第三十六頁，共60頁。第四節(jié)最大流問題

如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234第三十七頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)流問題定義1：定一個有向圖D=(V,E),在V中有一個發(fā)點(diǎn)vs和一收點(diǎn)vt，其余的點(diǎn)為中間點(diǎn)。對于每一條弧(vi,vj),對應(yīng)有一個c(vi,vj)0,(cij)稱為弧的容量。這樣的有向圖稱為容量網(wǎng)絡(luò)。記為D=(V,E,C)。1、網(wǎng)絡(luò)流——義在弧集合E上的一個函數(shù)f={f(vi,vj)}，稱f(vi,vj)為弧(vi,vj)上的流量，簡記fij。2、可行流——3、最大流——4、增廣鏈——5、最小截集——第三十八頁，共60頁。2、可行流與最大流定義2滿足下列條件的流稱為可行流：1)0fijcij2)平衡條件：中間點(diǎn)fij=fji(vi,vj)A(vj,vi)A發(fā)點(diǎn)vsfsj–fjs=v(f)(vs,vj)A(vj,vs)Aftj–fjt=–v(f)(vt,vj)A收點(diǎn)vt，(vj,vt)A式中v(f)稱為這個可行流的流量，即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。第三十九頁，共60頁。最大流問題：求一流{fij}滿足0fijcijv(f)i=sfij–fji=0is，t–v(f)i=t且使v(f)達(dá)到最大。第四十頁，共60頁。3、增廣鏈

給定可行流f={fij}，使fij=cij的弧稱為飽和弧，使fij<cij的弧稱為非飽和弧，把fij=0的弧稱為零流弧，fij>0的弧稱為非零流弧。

若是網(wǎng)絡(luò)中連接發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，定義鏈的方向是從vs到vt，則鏈上的弧被分成兩類：前向?。夯〉姆较蚺c鏈的方向一致全體+后向?。夯〉姆较蚺c鏈的方向相反全體—定義3設(shè)f是一可行流，是從vs到vt的一條鏈，若滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)+上，0fij<cij

在弧(vi,vj)—上，0<fijcij第四十一頁，共60頁。

4、截集與截量

定義4給定網(wǎng)絡(luò)D=(V,A,C)，若點(diǎn)集V被剖分為兩個非空集合V1和V1，使vsV1，vtV1，則把弧集(V1,V1)稱為是（分離vs和vt的）截集。截集是從vs到vt的必經(jīng)之路。

定義5給定一截集(V1,V1)，把截集(V1,V1)中所有弧的容量之和稱為這個截集的容量(截量),記為C(V1,V1)。v(f)C(V1,V1)第四十二頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)流問題1、流量——截量定理容量網(wǎng)絡(luò)上任何一個可行流的流量不超過任何一個截集的截量。2、增廣鏈調(diào)整定理在增廣鏈上對可行流進(jìn)行調(diào)整可以得到一個流量更大的可行流。3、最大流定理可行流是最大流的充分必要條件是不存在關(guān)于該可行流的增廣鏈。第四十三頁，共60頁。步驟：2、標(biāo)號過程1、選取一個可行流（可選擇零流?。?/p>

從Vs出發(fā)，在前向弧上(vi,vj)，若fij<cij，則給vj標(biāo)號(vi,l(vj))，其中l(wèi)(vj)=min[l(vi)，cij–fij]。在后向弧(vj,vi)上，若fji>0，則給vj標(biāo)號(–Vi,l(vj))，其中l(wèi)(vj)=min[l(vi)，fji]。二、尋找最大流的標(biāo)號法(FordFulkerson)

思想：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增大流量，使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。第四十四頁，共60頁。3、若標(biāo)號延續(xù)到vt，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整階段4，否則當(dāng)前流即為最大流。4、調(diào)整過程令調(diào)整量為=l(vt)令fij+

(vi,vj)+fij′=fij–(vi,vj)—

fij(vi,vj)去掉所有的標(biāo)號，對新的可行流f′={fij′}，重新進(jìn)入標(biāo)號過程。第四十五頁，共60頁?？山Y(jié)合下圖理解其實(shí)際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第四十六頁，共60頁。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例求下列網(wǎng)絡(luò)的最大流與最小截集。[解]一、標(biāo)號過程則v1的標(biāo)號為(vs,l(v1))，其中第四十七頁，共60頁。l(v1)=min{l(vs)，cs1–fs1}=min{+，9–2}=2（3）檢查v1,在弧(v1,v4)上,f14=7,c14=9,f14<c14,則v4的標(biāo)號為(v1,l(v4))，其中l(wèi)(v4)=min{l(v1)，c14–f14}=min{2，3-1}=2（4）檢查v4,在弧(v3,v4)上,f14=1>0，則v3的標(biāo)號為(-v4,l(v3))，其中l(wèi)(v3)=min{l(v4)，f34}=min{2，1}=1（5）檢查v3,在弧(v3,vt)上,f3t=3,c3t=6,f3t<c3t,第四十八頁，共60頁。則vt的標(biāo)號為(v3,l(vt))，其中l(wèi)(vt)=min{l(v3)，c3t–f3t}=min{1，6-3}=1這樣，我們得到了一增廣鏈,如圖所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0,)(vs,2)(v1,2)(-v4,1)(v3,1)其中+={(vs,v1),(v1,v4),(v3,vt)}，—={(v3,v4)}第四十九頁，共60頁。二、調(diào)整過程取調(diào)整量為=1，在上調(diào)整f。在+上：fs1+=7+1=8

f14+=2+1=3

f4t+=5+1=6在—上：f43–=1–1=0s1vtvv3(9,8)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)第五十頁，共60頁。

在上圖中重復(fù)上述標(biāo)號過程，依次給vs,v2,v1,v4標(biāo)號后，由于標(biāo)號無法繼續(xù)下去，算法結(jié)束。這時的流為最大流，最大流的流量為vvv(4,4)v(f)=8+3=11

與此同時，可找到最小截集(V1,V1)，其中V1為標(biāo)號點(diǎn)集合，V1為未標(biāo)號點(diǎn)集合，弧集合(V1,V1)即為最小截集。此例中，V1={vs,v2,v1,v4},V1={v3,vt},(V1,V1)={(v1,v3)，(v4,vt)}第五十一頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

網(wǎng)絡(luò)流問題容量網(wǎng)絡(luò)N上最大流的標(biāo)號（Ford-Fulkerson）算法：下面，我們采用此算法來求解前面的旅行總社計劃問題案例——第五十二頁，共60頁。圖與網(wǎng)絡(luò)模型GraphTheory

最大流問題各辦事處已訂購機(jī)票情況表成都vs重慶v1武漢v2上海v3西安v4鄭州v5沈陽v6昆明v7廣州v8北京vt成都重慶武漢上海西安鄭州沈陽昆明廣州北京1015128121030106152510158