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

運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用(OperationsResearch)主講：楊啟明圖的基本概念與模型1樹圖和圖的最小部分樹2最短路問題3第6章圖與網(wǎng)絡(luò)分析郵路問題4網(wǎng)絡(luò)的最大流5近代圖論的歷史可追溯到18世紀(jì)的七橋問題—穿過K?nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。K?nigsberg橋?qū)?yīng)的圖6.1圖的基本概念與模型島北區(qū)東區(qū)南區(qū)

圖論中圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。

(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示，圖6-1就是一個表示這種關(guān)系的圖。圖的定義：

若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖G可以定義為點和邊的集合，記作：其中:V——點集E——邊集

當(dāng)然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙陳等七人的相互認(rèn)識關(guān)系我們也可以用圖6-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5圖6-2圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳圖6-3

如果我們把上面例子中的“相互認(rèn)識”關(guān)系改為“認(rèn)識”的關(guān)系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。圖6-3就是一個反映這七人“認(rèn)識”關(guān)系的圖。相互認(rèn)識用兩條反向的弧表示。圖的基本概念與模型定義:圖中的點用v表示，邊用e表示。對每條邊可用它所連接的點表示，記作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5

端點,關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點，反之稱邊e為點vi或vj的關(guān)聯(lián)邊。若點vi、vj與同一條邊關(guān)聯(lián)，稱點vi和vj相鄰；若邊ei和ej具有公共的端點，稱邊ei和ej相鄰。圖的基本概念與模型

環(huán),多重邊,簡單圖如果邊e的兩個端點相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個點之間多于一條，稱為多重邊，如右圖中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的基本概念與模型

次，奇點，偶點，孤立點與某一個點vi相關(guān)聯(lián)的邊的數(shù)目稱為點vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點稱作奇點，次為偶數(shù)的點稱作偶點，次為1的點稱為懸掛點，次為0的點稱作孤立點。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:

一個圖的次等于各點的次之和。圖的基本概念與模型

鏈，圈，連通圖圖中某些點和邊的交替序列，若其中各邊互不相同，且對任意vi,t-1和vit均相鄰稱為鏈。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起點與終點重合的鏈稱作圈。如果每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。圖的基本概念與模型

二部圖（偶圖）圖G=(V,E)的點集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=?,使得同一集合中任意兩個頂點均不相鄰，稱這樣的圖為偶圖。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二部圖，(b)也是二部圖，但不明顯，改畫為(c)時可以清楚看出。圖的基本概念與模型

子圖，部分圖(支撐子圖)圖G1={V1、E1}和圖G2={V2，E2}如果有稱G1是G2的一個子圖。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖）若有，則稱G1是G2的一個部分圖(支撐子圖)。圖的基本概念與模型

網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖G＝（V，E），對G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費用、通過能力(容量)等等。①②③④⑤⑥910201571419256端點無序的賦權(quán)圖稱為無向網(wǎng)絡(luò)端點有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。圖的基本概念與模型

出次與入次

有向圖中，以vi為始點的邊數(shù)稱為點vi的出次，用d+(vi)表示；以vi為終點的邊數(shù)稱為點vi的入次，用表示d-(vi)；vi點的出次和入次之和就是該點的次。※有向圖中，所有頂點的入次之和等于所有頂點的出次之和。圖的基本概念與模型圖的模型應(yīng)用例6.1有甲,乙,丙,丁,戊,己6名運(yùn)動員報名參加A,B,C,D,E,F6個項目的比賽。下表中打√的是各運(yùn)動員報告參加的比賽項目。問6個項目的比賽順序應(yīng)如何安排，做到每名運(yùn)動員都不連續(xù)地參加兩項比賽。ABCDEF甲√√乙√√√丙√√丁√√戊√√√己√√√圖的基本概念與模型解：用圖來建模。把比賽項目作為研究對象，用點表示。如果2個項目有同一名運(yùn)動員參加，在代表這兩個項目的點之間連一條線，可得下圖。ABCDEF在圖中找到一個點序列，使得依次排列的兩點不相鄰，即能滿足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A圖的基本概念與模型

一個班級的學(xué)生共計選修A、B、C、D、E、F六門課程，其中一部分人同時選修D(zhuǎn)、C、A，一部分人同時選修B、C、F，一部分人同時選修B、E，還有一部分人同時選修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會連續(xù)參加考試，試設(shè)計一個考試日程表。思考題圖的基本概念與模型思考題解答： 以每門課程為一個頂點，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點對應(yīng)課程不能連續(xù)考試，不相鄰頂點對應(yīng)課程允許連續(xù)考試，因此，作圖的補(bǔ)圖，問題是在圖中尋找一條哈密頓道路，如C—E—A—F—D—B，就是一個符合要求的考試課程表。圖的基本概念與模型AFEDCB圖的基本概念與模型AFEDCB圖的基本概念與模型圖的基本性質(zhì)：定理1任何圖中，頂點次數(shù)之和等于所有邊數(shù)的2倍。定理2任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。證明：由于每條邊必與兩個頂點關(guān)聯(lián)，在計算點的次時，每條邊均被計算了兩次，所以頂點次數(shù)的總和等于邊數(shù)的2倍。證明：設(shè)V1和V2分別為圖G中奇點與偶點的集合。由定理1可得：2m為偶數(shù)，且偶點的次之和也為偶數(shù)，所以必為偶數(shù)，即奇數(shù)點的個數(shù)必為偶數(shù)。圖的基本概念與模型圖的矩陣描述：如何在計算機(jī)中存儲一個圖呢？現(xiàn)在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有：鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1.鄰接矩陣 對于圖G=（V，E），|V|=n，|E|=m，有n

n階方矩陣A=(aij)n

n，其中v5v1v2v3v4v64332256437例6.2下圖所表示的圖可以構(gòu)造鄰接矩陣A如下對于賦權(quán)圖G=(V,E),其中邊有權(quán),構(gòu)造矩陣B=(bij)n

n

其中：圖的基本概念與模型2.關(guān)聯(lián)矩陣對于圖G=(V,E),|V|=n,|E|=m,有m

n階矩陣M=(mij)m

n，其中:3.權(quán)矩陣101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例6.3下圖所表示的圖可以構(gòu)造鄰接矩陣M如下:M=（mij）=v5v1v2v3v4v64332256437例6.4下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:無向圖：由點和邊構(gòu)成的圖，記作G=（V，E）。有向圖：由點和弧構(gòu)成的圖，記作D=（V，A）。連通圖：對無向圖G，若任何兩個不同的點之間，至少存在一條鏈，則G為連通圖?；芈罚喝袈返牡谝粋€點和最后一個點相同，則該路為回路。賦權(quán)圖：對一個無向圖G的每一條邊(vi,vj)，相應(yīng)地有一個數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。網(wǎng)絡(luò)：在賦權(quán)的有向圖D中指定一點，稱為發(fā)點，指定另一點稱為收點，其它點稱為中間點，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就稱為網(wǎng)絡(luò)。圖與網(wǎng)絡(luò)的基本概念樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。圖6-11中，(a)就是一個樹，而(b)因為圖中有圈所以就不是樹，(c)因為不連通所以也不是樹。圖6-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)6.2樹圖和圖的最小部分樹6.2樹圖和圖的最小部分樹樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。例6.2乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動員樹與圖的最小樹例6.3某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。廠長人事科財務(wù)科總工程師生產(chǎn)副廠長經(jīng)營副廠長開發(fā)科技術(shù)科生產(chǎn)科設(shè)備科供應(yīng)科銷售科檢驗科動力科樹與圖的最小樹

樹：無圈的連通圖即為樹性質(zhì)1：任何樹中必存在次為1的點。性質(zhì)2：n個頂點的樹必有n-1條邊。性質(zhì)3：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。v1v2v3v4v5v6樹與圖的最小樹

圖的最小部分樹(支撐樹)如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2樹與圖的最小樹abcfedhgbfed樹與圖的最小樹abcfedhgbfdg樹與圖的最小樹bcedabcfedhg樹與圖的最小樹abchabcfedhg樹與圖的最小樹afdgabcfedhg樹與圖的最小樹求樹的方法：破圈法和避圈法破圈法樹與圖的最小樹部分樹樹與圖的最小樹避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5樹與圖的最小樹賦權(quán)圖中求最小樹的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)＝n-1=5樹與圖的最小樹v1v2v3v4v5v643521得到最小樹：MinC(T)=15避圈法（Kruskal）思想：在圖中取一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈（每一步中，如果有兩條或兩條以上的邊都是最小權(quán)的邊，則從中任選一條）。5v1v2v3v4v5v6843752618樹與圖的最小樹v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336練習(xí)：應(yīng)用破圈法求最小樹樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v6201591625328174123樹與圖的最小樹v1v7v4v3v2v5v6201591625328174123樹與圖的最小樹v1v7v4v3v2v5v61591625328174123樹與圖的最小樹v1v7v4v3v2v5v61591625328174123樹與圖的最小樹v1v7v4v3v2v5v691625328174123樹與圖的最小樹v1v7v4v3v2v5v691625328174123樹與圖的最小樹v1v7v4v3v2v5v6925328174123樹與圖的最小樹v1v7v4v3v2v5v6925328174123樹與圖的最小樹v1v7v4v3v2v5v69328174123樹與圖的最小樹v1v7v4v3v2v5v69328174123樹與圖的最小樹v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=57樹與圖的最小樹練習(xí)：應(yīng)用避圈法求最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57樹與圖的最小樹課堂練習(xí)：3749346321MinC(T)=12MinC(T)=15254173314475答案：樹與圖的最小樹34122323242MinC(T)=12213638534567454321MinC(T)=186.3最短路問題如何用最短的線路將三部電話連起來？此問題可抽象為設(shè)△ABC為等邊三角形，，連接三頂點的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個，其中最短路線者顯然是二邊之和（如AB∪AC）。ABCABCP但若增加一個周轉(zhuǎn)站（新點P）連接4點的新網(wǎng)絡(luò)的最短路線為PA＋PB＋PC。最短新路徑之長N比原來只連三點的最短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。最短路問題問題描述： 就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路.

有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應(yīng)用。最短路問題例6.4渡河游戲 一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過河去，并且在河上來回次數(shù)最少？這個問題就可以用求最短路方法解決。最短路問題定義：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）點——vi

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

表示由狀態(tài)vi

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

4）權(quán)——邊ek

上的權(quán)定為1我們可以得到下面的加權(quán)有向圖狀態(tài)說明：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求最短路有兩種算法:

狄克斯屈拉(Dijkstra)標(biāo)號算法逐次逼近算法最短路問題狄克斯屈拉(Dijkstra)標(biāo)號算法的基本思路：若序列{vs,v1…..vn-1,vn}是從vs到vt間的最短路，則序列{vs,v1…..vn-1}必為從vs到vn-1的最短路。

假定v1→v2→v3→v4是v1→v4的最短路，則v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5最短路問題求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點是vs,終點是vt,以vi為起點vj為終點的弧記為(i,j)

距離為dijP標(biāo)號(點標(biāo)號)：b(j)—起點vs到點vj的最短路長；T標(biāo)號(邊標(biāo)號)：k(i,j)=b(i)+dij，步驟：1.令起點的標(biāo)號；b(s)＝0。2.找出所有已標(biāo)號vi到未標(biāo)號vj的弧集合B={(i,j)}如果這樣的弧不存在或vt已標(biāo)號則計算結(jié)束；3.計算集合B中弧k(i，j)=b(i)+dij的標(biāo)號4.選一個點標(biāo)號在終點vl處標(biāo)號b(l),返回到第2步。例6.5求下圖v1到v7的最短路長及最短路線①②③④⑤⑥⑦86252353421057086225441114751071211v7已標(biāo)號，計算結(jié)束。從v1到v7的最短路長是11,最短路線：v1→v4→v6

→v7P標(biāo)號T標(biāo)號已標(biāo)號點未標(biāo)號點①②③④⑤⑥⑦（①，②），（①，③），（①，④）

0+80+60+2①④②③⑤⑥⑦（①，②），（①，③），（④，③），（④，⑥）0+80+62+32+2①④⑥②③⑤⑦（①，②）（①，③）（④，③）（⑥，②）（⑥，⑤）（⑥，⑦）

0+80+62+34+3

4+10

4+7

①④⑥③②⑤⑦(①,②)(①,③)(③,④)（③,②)(③,⑥)(⑥,②)(⑥,⑤)(⑥,⑦)

0+80+65+25+10

5+44+34+10

4+7

╳╳12最短路問題例

求下圖中v1到v6的最短路v23527531512v1v6v5v3v4（0,s)解：采用Dijkstra算法，最短路徑為v1→

v3→

v4→

v6(3,3)(2,1)(3,1)(8,4)點v5不能標(biāo)號，說明vs不可達(dá)v5最短路問題從上例知，只要某點已標(biāo)號，說明已找到起點vs到該點的最短路線及最短距離，注：無向圖最短路的求法只將上述步驟2將弧改成邊即可。因此可以將每個點標(biāo)號，求出vs到任意點的最短路線，如果某個點vj不能標(biāo)號，說明vs不可達(dá)vj。例6.6求下圖v1到各點的最短距離及最短路線。①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有點都已標(biāo)號，點上的標(biāo)號就是v1到該點的最短距離，最短路線就是紅色的鏈。課堂練習(xí)：1.用Dijkstra算法求下圖從v1到v6的最短距離及路線。v3v54v1v2v4v635222421v1到v6的最短路為：最短路問題2.求從v1到v8的最短路徑237184566134105275934682最短路問題237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路徑為v1→v4→v7→v5→v8，最短距離為10最短路問題3.求下圖中v1點到另外任意一點的最短路徑v1v2v3v4v6v5322762133最短路問題v1V2V3V4V6V5322762133024714最短路問題v1V2V3V4V6V5322762133024714最短路問題算法適用條件：Dijkstra算法只適用于全部權(quán)為非負(fù)情況，如果某邊上權(quán)為負(fù)的，算法失效。此時可采用逐次逼近算法。例6.7如右圖所示中按dijkstra算法可得P(v1)=5為從vs→v1的最短路長顯然是錯誤的，從vs→v2→v1路長只有3。v2vsv15-58最短路問題的應(yīng)用：例6.7電信公司準(zhǔn)備準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。v1（甲地）1517624431065v2v7(乙地)v3v4v5v6解：這是一個求無向圖的最短路的問題。直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標(biāo)號的點到未標(biāo)號的點的弧的集合改成已標(biāo)號的點到未標(biāo)號的點的邊的集合即可。最短路徑v1→v3→

v5→

v6→

v7

V1（甲地）1517624431065v2V7（乙地）V5V6V3V4（0,s)（10,1)（13,3)（14,3)（16,5)（18,5)（22,6)最短路問題例6.8設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費，當(dāng)然新設(shè)備的維修費用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費，但維修費用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。已知：設(shè)備每年年初的價格表年份12345年初價格1111121213最短路問題設(shè)備維修費如下表使用年數(shù)0-11-22-33-44-5每年維修費用5681118解：將問題轉(zhuǎn)化為最短路問題，如下圖：用vi表示“第i年年初購進(jìn)一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6把所有弧的權(quán)數(shù)計算如下表，把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723

最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條：v1→v3→v6和v1→v4→v6V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)

郵遞員的工作是每天在郵局里選出郵件，然后送到他所管轄的客戶中，再返回郵局。自然地，若他要完成當(dāng)天的投遞任務(wù)，則他必須要走過他所投遞郵件的每一條街道至少一次。問怎樣的走法使他的投遞總行程為最短？這個問題就稱為中國郵路問題。1、提出問題上圖表示從R1-R15個街道交叉點，街道上的數(shù)字表示該街道的長度，單位為米。6.4中國郵路問題

首先把這個實際問題轉(zhuǎn)換成一個非負(fù)賦權(quán)圖G，G的頂點代表街與街之間的交叉路口和終端，兩個頂點相鄰當(dāng)且僅當(dāng)這兩點所對應(yīng)的路口有直通街道而中間不通過其他路口，每條邊的權(quán)是這條邊所對應(yīng)街道的長度。G的通過每條邊至少一次的閉途徑稱為G的環(huán)游。具有最小權(quán)的環(huán)游稱為G的最優(yōu)環(huán)游，則中國郵路問題就是要在賦權(quán)圖G中找一條最優(yōu)環(huán)游。2、分析問題

街道結(jié)構(gòu)圖由上構(gòu)造右圖3、解決問題返回結(jié)束尋找Euler圖的最優(yōu)環(huán)游的基本思路：（1）用雙倍邊方法求的一個Euler賦權(quán)母圖，使達(dá)到最小。（2）用Fleury算法求得的Euler環(huán)游,就是圖的環(huán)游；定理4.2.1（管梅谷，1960）設(shè)是一個連通的賦權(quán)圖，是的一個Euler賦權(quán)生成母圖，則當(dāng)且僅當(dāng)沒有重復(fù)數(shù)大于2的邊。并且的每一個長度至少是3的回路中多重邊的權(quán)和不超過此回路權(quán)和的一半。返回結(jié)束奇偶點圖上作業(yè)法（求最優(yōu)環(huán)游算法）：(1)把中度為奇數(shù)的頂點兩兩配對，記為。對每個，中取一條路，將上的每一條邊都添加一條邊，從而得到的一個賦權(quán)Euler生成母圖。(2)去掉中關(guān)于的某一對相鄰頂點有多于2條邊連接它們，則去掉其中的偶數(shù)條邊，留下1條或2條邊連接這兩個頂點。直到每一對相鄰頂點至多由2條邊連接。(4)用Fleury算法求的Euler環(huán)游。(3)檢查的每一個回路，如果某個回路上多重邊的權(quán)和超過此回路權(quán)和的一半，則將進(jìn)行調(diào)整：刪除，的邊重數(shù)增加1。例1下圖(a)給出賦權(quán)圖，是的四個奇點。根據(jù)上述算法,求下圖的最優(yōu)環(huán)游。解：根據(jù)上述算法(1)，把和配對，和配對，取，并對中每條邊各添加一條邊；又取，并對中每條邊各添加一條邊。得圖(b).依次按算法，得到圖(c),(d),(e)奇偶點圖上作業(yè)法缺陷：奇偶點圖上作業(yè)法需要檢查圖中的每個回路。隨著頂點個數(shù)和邊數(shù)增加，回路個數(shù)增加。如下圖一，圖二。圖一回路超過150個，圖二回路至少有上千個。思考：如何求恰好有兩個奇點的賦權(quán)圖的最優(yōu)環(huán)游？設(shè)恰好有兩個奇點和，則可以利用2.2節(jié)求出的一條最短路，在中只要把中的每一條邊中再添加一條邊，加上權(quán)就可得Eluer圖?？梢宰C明的Eluer環(huán)游就是的最優(yōu)環(huán)游。下左圖的最優(yōu)環(huán)游即為右圖。如何制定一個運(yùn)輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡(luò)最大流問題。6.5網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流基本概念：1.容量網(wǎng)絡(luò)：隊網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個發(fā)點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網(wǎng)絡(luò)中其他點稱為中間點。s①②③④t48441226792.網(wǎng)絡(luò)的最大流

是指網(wǎng)絡(luò)中從發(fā)點到收點之間允許通過的最大流量。3.流與可行流流是指加在網(wǎng)絡(luò)各條弧上的實際流量，對加在弧(vi,vj)上的負(fù)載量記為fij。若fij=0，稱為零流。滿足以下條件的一組流稱為可行流。

容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0≤fij≤cij

中間點平衡條件。

若以v(f)表示網(wǎng)絡(luò)中從s→t的流量，則有：網(wǎng)絡(luò)的最大流結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）網(wǎng)絡(luò)最大流問題： 指滿足容量限制條件和中間點平衡的條件下，使v(f)值達(dá)到最大。

割與割集割是指容量網(wǎng)絡(luò)中的發(fā)點和收點分割開，并使s→t的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用表示。左圖中，AA′將網(wǎng)絡(luò)上的點分割成兩個集合。

●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AA’BB’現(xiàn)有，稱弧的集合(v1,v3),(v2,v4)}是一個割，且的流量為18。定理1

設(shè)網(wǎng)絡(luò)N中一個從s到t

的流f的流量為v(f

)，(V,V′)為任意一個割集，則v(f

)

=f(V,V′)

f(V′,V)推論1

對網(wǎng)絡(luò)N中任意流量v(f

)和割集(V,V′)，有v(f

)

c(V,V′)[證明]w=f(V,V′)

f(V′,V)

f(V,V′)

c(V,V′)推論2

最大流量v＊

(f

)不大于最小割集的容量，即：v＊

(f

)min{c(V,V′)}定理2

在網(wǎng)絡(luò)中s→t的最大流量等于它的最小割集的容量，即：v＊

(f)=c＊(V,V′)增廣鏈 在網(wǎng)絡(luò)的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為s→t的弧，稱為前向弧，記作μ+,存在f<c；所有指向為t→s的弧，稱為后向弧，記做μ－，若f>0，則稱這樣的鏈為增廣鏈。例如下圖中，s→v2→v1→v3→v4→t。定理3

網(wǎng)絡(luò)N中的流f

是最大流當(dāng)且僅當(dāng)N中不包含任何增廣鏈●stv3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)求網(wǎng)絡(luò)最大流的標(biāo)號算法：[基本思想]

由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。[基本方法]找出第一個可行流，（例如所有弧的流量fij=0。）用標(biāo)號的方法找一條增廣鏈

首先給發(fā)點s標(biāo)號(∞),標(biāo)號中的數(shù)字表示允許的最大調(diào)整量。選擇一個點vi

已標(biāo)號并且另一端未標(biāo)號的弧沿著某條鏈向收點檢查：

如果弧的起點為vi，并且有fij<Cij，則給vj標(biāo)號為(Cij－fij)

如果弧的方向指向vi，并且有fji>0，則vj標(biāo)號(fji)(3)重復(fù)第(2)步，可能出現(xiàn)兩種結(jié)局：

標(biāo)號過程中斷，t無法標(biāo)號，說明網(wǎng)絡(luò)中不存在增廣鏈，目前流量為最大流。同時可以確定最小割集，記已標(biāo)號的點集為V,未標(biāo)號的點集合為V′,(V,V′)為網(wǎng)絡(luò)的最小割。

t得到標(biāo)號，反向追蹤在網(wǎng)絡(luò)中找到一條從s到t得由標(biāo)號點及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第(4)步(4)修改流量。設(shè)原圖可行流為f，令得到網(wǎng)絡(luò)上一個新的可行流f’。(5)擦除圖上所有標(biāo)號，重復(fù)(1)-(4)步，直到圖中找不到任何增廣鏈，計算結(jié)束。網(wǎng)絡(luò)的最大流例6.10用標(biāo)號算法求下圖中s→t的最大流量，并找出最小割?！駍tv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)解：(1)先給s標(biāo)號(∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0，∞)(2)檢查與s點相鄰的未標(biāo)號的點，因fs1<cs1，故對v1標(biāo)號=min{∞,cs1-fs1}=1,(s，1)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(0，∞)(s，1)(2)檢查與v1點相鄰的未標(biāo)號的點，因f13<c13，故對v3標(biāo)號=min{1,c13-f13}=min{1,6}=1(v1，1)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0，∞)(s，1)(v1，1)(3)檢查與v3點相鄰的未標(biāo)號的點，因f3t<c3t，故對vt標(biāo)號=min{1,c3t-f3t}=min{1,1}=1(v3，1)找到一條增廣鏈s→v1→v3→t(4)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?！駍tv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(0，∞)(s，1)(v1，1)(v3，1)(5)擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈?！駍tv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)(0，∞)(s，1)(v1，1)(v3，1)(5)擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈?！駍tv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(0，∞)(s，2)ε(2)=min{∞,2}=2(v2，2)ε(1)=min{ε(v2),f12}=min{2,3}=2ε(3)=min{2,5}=2(v1，2)(v3，1)ε(4)=min{2,1}=1(v4，1)ε(t)=min{1,2}=1(6)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?！駍tv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(0，∞)(s，2)(v2，2)(v1，2)(v3，1)(v4，1)●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(7)擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。(0，∞)(s，2)(v2，2)(v1，2)(v3，1)(v4，1)●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(s，1)(v2，1)(v1，1)(7)擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。ε(2)=min{∞,1}=1ε(1)=min{1,2}=1ε(3)=min{1,4}=1(0，∞)例6.9求下圖s→t的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)