6圖與網(wǎng)絡(luò)最優(yōu)化方法

第六章圖與網(wǎng)絡(luò)最優(yōu)化方法學(xué)習(xí)要點(diǎn)1.掌握?qǐng)D的基本概念；2.掌握最小部分樹的求解方法；3.掌握一筆畫問(wèn)題求解方法——奇偶點(diǎn)作業(yè)法；4.掌握最短路徑的求解方法及應(yīng)用；5.掌握最大流問(wèn)題的求解方法及應(yīng)用；6.掌握最小費(fèi)用最大流求解方法。案例導(dǎo)讀1離散數(shù)學(xué)是應(yīng)用數(shù)學(xué)的一個(gè)重要組成部分，圖論是離散數(shù)學(xué)的重要分支。圖論知識(shí)在現(xiàn)代生活中的各個(gè)領(lǐng)域應(yīng)用十分廣泛，現(xiàn)代生活和管理中的很多問(wèn)題建立圖論模型后變得直觀易懂，不需要大量的預(yù)備知識(shí)也能理解，這也是圖論最吸引人的地方。許多圖論問(wèn)題源于數(shù)學(xué)游戲和實(shí)際問(wèn)題。近些年的數(shù)學(xué)競(jìng)賽和數(shù)學(xué)建模中常常會(huì)用到圖論的理論和方法來(lái)解題，如多階段決策問(wèn)題、選址問(wèn)題、管道的鋪設(shè)、網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題等。1736年著名數(shù)學(xué)家歐拉（Euler）發(fā)表了圖論方面第一篇論文，解決了有名的哥尼斯堡七橋難題，歐拉被公認(rèn)為圖論的創(chuàng)始人。圖論以集合元素間某種二元關(guān)系生成的拓?fù)鋱D形為研究對(duì)象，任何一個(gè)包含了某種二元關(guān)系的系統(tǒng)都可以用圖論的方法來(lái)分析。經(jīng)過(guò)200多年的發(fā)展，圖論已經(jīng)發(fā)展成為一個(gè)理論與應(yīng)用兼有的數(shù)學(xué)領(lǐng)域，在自然科學(xué)和社會(huì)科學(xué)研究中有著廣泛的應(yīng)用。目錄CONTENT圖與網(wǎng)絡(luò)的基本概念一最小部分樹問(wèn)題二中國(guó)郵遞員問(wèn)題三最短路徑問(wèn)題四最大流問(wèn)題五最小費(fèi)用最大流問(wèn)題六6.1圖與網(wǎng)絡(luò)的基本概念6.1.1圖的基本概念和術(shù)語(yǔ)1.無(wú)向圖與有向圖由點(diǎn)和邊組成的圖為無(wú)向圖，記為G(V,E)。由點(diǎn)和弧組成的圖為有向圖，記為D(V,A)。2.鏈與路、圈與回路在無(wú)向圖G(V,E)中，任意兩頂點(diǎn)vi到vj之間由頂點(diǎn)和邊相互交替構(gòu)成的一個(gè)序列稱為由vi到vj的一條鏈。在有向圖D(V,A)中由一個(gè)頂點(diǎn)到另一不相鄰頂點(diǎn)之間有同向的弧連接，則稱為由vi到vj的一條路，3.連通圖與支撐子圖圖G(V,E)中，任意兩頂點(diǎn)vi和vj之間至少有一條鏈存在，則該圖為連通圖，否則為不連通的圖。連通圖中不存在孤立的頂點(diǎn)。若圖G′(V′,E′)，V=V′，EE′，則稱G′(V′,E′)為G(V,E)的支撐子圖。4.賦權(quán)圖與網(wǎng)絡(luò)如果在圖G(V,E)中的每條邊或圖D(V,A)中每條弧上均標(biāo)有某種數(shù)量指標(biāo)，即權(quán)Cij，則該圖為賦權(quán)圖，又稱網(wǎng)絡(luò)，記為G(V,E，C)和D(V,A,C)。與各邊有關(guān)的數(shù)量指標(biāo)稱為該邊的權(quán)。5.歐拉圖給定圖G(V,E)，通過(guò)圖G的每條邊一次且僅一次的鏈稱為歐拉（Euler）鏈；通過(guò)圖G的每條邊一次且僅一次的回路稱為歐拉回路，存在歐拉回路的圖稱為歐拉圖。6.1.2樹的概念和術(shù)語(yǔ)1.樹連通且不含圈的圖叫樹。2.樹的性質(zhì)（1）樹的任意兩頂點(diǎn)之間存在且僅存在一條鏈，如果去掉樹中任意一條弧，則圖是不連通圖；（2）如果用弧把任意不相鄰的頂點(diǎn)連接起來(lái)，僅存在一個(gè)圈，再去掉該圈的另一條弧，又得到另一棵樹。因此，該性質(zhì)可以用“加一弧，得一圈；去一弧，破一圈”來(lái)說(shuō)明；（3）若樹的頂點(diǎn)和邊數(shù)分別為n和m，則m=n-1。3.部分樹在連通圖G(V,E)中，包括所有頂點(diǎn)的樹叫部分樹（支撐樹）。屬于部分樹的邊稱為內(nèi)邊，不屬于部分樹的邊稱為外邊。連通圖G(V,E)中，內(nèi)邊權(quán)值總和最小的部分樹為最小部分樹（最小支撐樹）。最大部分樹？6.2最小部分樹問(wèn)題6.1.1圖的基本概念和術(shù)語(yǔ)1.最小部分樹定理樹的任意一條外邊Cij比所對(duì)應(yīng)的鏈中最長(zhǎng)的邊還長(zhǎng)；即最小部分樹是指內(nèi)邊權(quán)總和最小的那棵樹2.最小部分樹算法【例6.1】某市區(qū)準(zhǔn)備在五個(gè)社區(qū)間架設(shè)光纖網(wǎng)絡(luò)，各社區(qū)的位置如圖6.2.1(a)，如何架設(shè)光纖網(wǎng)絡(luò)可使各社區(qū)間均能通網(wǎng)且光纖線路最短。6.3中國(guó)郵遞員問(wèn)題6.3.1哥尼斯堡七橋問(wèn)題普魯士哥尼斯堡（現(xiàn)稱加里寧格勒）的普雷瓦河中有兩個(gè)小島，連接兩岸與小島共架設(shè)了七座橋。

A

D

B圖6.3.1哥尼斯堡七橋問(wèn)題

C【定理1】若圖G的每個(gè)頂點(diǎn)所關(guān)聯(lián)的邊數(shù)是偶數(shù)條，則圖G是歐拉回路，這樣的圖能一筆畫出；【定理2】若除鏈的端點(diǎn)以外其余每個(gè)頂點(diǎn)所關(guān)聯(lián)的邊數(shù)是偶數(shù)條（即圖中奇點(diǎn)數(shù)為2），則圖是歐拉鏈，若想走過(guò)該圖所有的邊而不走重復(fù)路，就只能從一個(gè)奇點(diǎn)出發(fā)到達(dá)另一個(gè)奇點(diǎn)。歐拉回路也稱一筆圈圖，歐拉鏈也稱一筆鏈圖，二者均為一筆畫圖。6.3.2中國(guó)郵遞員問(wèn)題由中國(guó)數(shù)學(xué)家管梅谷先生在1962年提出.抽象成圖的語(yǔ)言就是：給定一個(gè)無(wú)向的連通圖，怎樣才能使每條邊至少出現(xiàn)一次并使邊長(zhǎng)總和最小。這類問(wèn)題叫中國(guó)郵遞員問(wèn)題或一筆畫問(wèn)題。中國(guó)郵遞員問(wèn)題可以描述為：在一個(gè)有奇點(diǎn)的連通圖中，增加一些重復(fù)邊，使得該圖成為一筆圈圖，并且要求重復(fù)邊的總路長(zhǎng)最小。6.3.3奇偶點(diǎn)圖上作業(yè)法中國(guó)郵路問(wèn)題就是要通過(guò)增加一些邊，使得新圖中不含奇點(diǎn)，并且新增加的邊的權(quán)值之和最小?！纠?.2】某小區(qū)有9棟樓，樓與樓之間有道路連接如下圖6.3.4(a)所示。安保值班人員每天需對(duì)小區(qū)的范圍進(jìn)行巡視，巡視完畢回到安保室所在樓宇V1。要求每條道路都要巡視到。為使安保人員巡視路線最短，如何確定最優(yōu)巡視路線？6.4最短路徑問(wèn)題6.4.1兩固定頂點(diǎn)——狄克斯特拉法狄克斯特拉（Dijkstra）于1959年提出一種求最短的路徑的方法。其基本思想是：從起點(diǎn)v1開始逐步計(jì)算從v1到網(wǎng)絡(luò)各中間點(diǎn)vi的最短路，逐步外推直至算出v1至終點(diǎn)vt的最短路?！纠?.3】某工地道路網(wǎng)如圖6.4.2(a)所示，工地值班員準(zhǔn)備從v1點(diǎn)出發(fā)去v8點(diǎn)，怎樣走，距離最近呢？6.4.2邊長(zhǎng)有負(fù)值或有回路網(wǎng)絡(luò)的算法——福特法對(duì)有n個(gè)頂點(diǎn)且有負(fù)權(quán)值或回路的網(wǎng)絡(luò)，由點(diǎn)S至某點(diǎn)的最短距離需在S直接到達(dá)該點(diǎn)、經(jīng)由一個(gè)頂點(diǎn)到達(dá)該點(diǎn)、經(jīng)由兩個(gè)頂點(diǎn)……經(jīng)由（n-1）個(gè)頂點(diǎn)到達(dá)該點(diǎn)的距離中選最小值。因此算法從確定直接到達(dá)每個(gè)頂點(diǎn)的最短距離開始，依次計(jì)算經(jīng)由一個(gè)頂點(diǎn)、兩個(gè)頂點(diǎn)……（n-1）個(gè)頂點(diǎn)到達(dá)該頂點(diǎn)的最短距離。只要知道S點(diǎn)到各頂點(diǎn)的距離，就可遞推得出點(diǎn)S經(jīng)由一個(gè)頂點(diǎn)、經(jīng)由兩個(gè)頂點(diǎn)……經(jīng)由（n-1）個(gè)頂點(diǎn)到達(dá)各頂點(diǎn)的最短距離。通過(guò)選擇最小值時(shí)的對(duì)應(yīng)關(guān)系即可確定路徑。具體算法如下：（1）列出網(wǎng)絡(luò)矩陣A，其元素aij為：具體算法如下：

（1）列出網(wǎng)絡(luò)矩陣A；（2）確定

，它是A矩陣中S行的元素，為S點(diǎn)直接到達(dá)各頂點(diǎn)的距離。（3）按

計(jì)算

，并標(biāo)記路徑。當(dāng)

時(shí)，計(jì)算結(jié)束。（4）根據(jù)

及標(biāo)記，反向確定最短路徑。6.4.3最短路徑問(wèn)題與應(yīng)用【例6.4】某企業(yè)每年年初都需決定購(gòu)買新設(shè)備，還是繼續(xù)使用舊設(shè)備。購(gòu)買新設(shè)備，需支付購(gòu)置費(fèi)，繼續(xù)使用舊設(shè)備，需支付一筆維修費(fèi)，現(xiàn)需制定一個(gè)五年計(jì)劃，使企業(yè)在設(shè)備更新和維修中所支付的費(fèi)用最少。年份12345價(jià)格1.21.21.31.31.4維修費(fèi)0.60.70.91.21.9表6.4.3

設(shè)備價(jià)格和維修費(fèi)用預(yù)計(jì)表

單位：萬(wàn)元6.5最大流問(wèn)題系統(tǒng)中均有物流、能流和信息流的流動(dòng)，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；通信系統(tǒng)中有信息流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有資金流等等。對(duì)于這樣一些包含了流量問(wèn)題的系統(tǒng)，我們往往要求出其系統(tǒng)的最大流量。6.5.1基本假設(shè)和符號(hào)（1）源點(diǎn)，記為S；終點(diǎn)稱為匯點(diǎn)，記為T；中間點(diǎn)，記為i。（2）假設(shè)源點(diǎn)有無(wú)限多的物質(zhì)、能量、信息等待運(yùn)出，而匯點(diǎn)則有無(wú)限大的倉(cāng)庫(kù)來(lái)存儲(chǔ)這些物資、能量、信息等。（3）假設(shè)中間點(diǎn)不存儲(chǔ)任何物資、和信息等，只起傳遞作用。（4）規(guī)定由i點(diǎn)到j(luò)點(diǎn)的最大傳遞數(shù)量為路線（弧）的容量，以C(i,j)表示。（5）規(guī)定X(i,j)為由i點(diǎn)到j(luò)點(diǎn)的實(shí)際通過(guò)流量，且0≤X(i,j)≤C(i,j)。6.5.2基本的定理和概念1.可行流可行流為網(wǎng)絡(luò)上一個(gè)流，它應(yīng)滿足容量條件和平衡條件。（1）容量條件：對(duì)每一弧上的實(shí)際流量X(i,j)要小于等于弧的容量C(i,j)，即0≤X(i,j)≤C(i,j)；（2）平衡條件：中間點(diǎn)的流入量與流出量相等。2.飽和弧與零流弧對(duì)網(wǎng)絡(luò)上一個(gè)可行流f,若某弧上的實(shí)際流量X(i,j)=容量C(i,j)，則稱該弧為飽和弧，否則稱其為非飽和弧。對(duì)一個(gè)可行流f，若某弧上實(shí)際流量X(i,j)=0，稱該弧為零流弧，否則稱其為非零流弧。對(duì)任何一個(gè)網(wǎng)絡(luò)總存在可行流，如令所有弧的流量X(i,j)=0，就得到一個(gè)可行流（零流）。一個(gè)網(wǎng)絡(luò)上所有可行流中流量最大的可行流稱為最大流。所以，網(wǎng)絡(luò)的最大流問(wèn)題即是尋找流量最大的可行流。3.增廣鏈（或稱可擴(kuò)充鏈）設(shè)f是網(wǎng)絡(luò)上一可行流，若在起點(diǎn)S與終點(diǎn)T之間有一條鏈μ,規(guī)定其方向?yàn)镾→T。鏈上相應(yīng)弧按μ方向分成兩類：與μ方向一致的弧為前向弧，相反的弧則為后向弧。若鏈μ上弧的流量滿足：①μ上所有前向弧上流量X(i,j)<C(i,j)；②μ上所有后向弧上流量X(i,j)>0,則稱μ為關(guān)于流f的增廣鏈。4.割集及割集容量對(duì)于一連通網(wǎng)絡(luò)圖G，若點(diǎn)集V被分割稱為兩個(gè)非空集合

和

。當(dāng)G是有向圖時(shí)，把從

指向

弧的集合稱為分離S和T的一個(gè)割集，即所有前向弧的集合，記為

。一個(gè)割集中所有邊（或?。┑娜萘恐头Q為這個(gè)割集的容量,記為

。在連通圖G中，稱容量最小的割集為最小割集。5.最大流——最小割定理對(duì)于一個(gè)可行流f*，網(wǎng)絡(luò)中有一個(gè)割集，使f*=

，則f*必定是最大流，而

也必定是所有割集中容量最小的一個(gè)，即最小割集。6.5.3標(biāo)記法主要步驟是：①確定一初始可行流f及其流量；②檢驗(yàn)是否是網(wǎng)絡(luò)中的最大流，若不是，需進(jìn)一步調(diào)整；③將當(dāng)前的可行流調(diào)整成一個(gè)流量更大的新可行流，再由②檢驗(yàn)。6.5.3標(biāo)記法是從一個(gè)可行流出發(fā)，判斷網(wǎng)絡(luò)D中是否存在增廣鏈，若無(wú)增廣鏈則f為最大流；若有增廣鏈，則在增廣鏈上對(duì)當(dāng)前流f進(jìn)行調(diào)整（增流），得到新的可行流，繼續(xù)迭代。當(dāng)發(fā)現(xiàn)當(dāng)前流圖是最大流時(shí)，同時(shí)也就發(fā)現(xiàn)了最小割集。其思想是通過(guò)最大流找最小割集，而不是通過(guò)最小割集找最大流。6.5.4幾種特殊情況的處理1.多源點(diǎn)、多匯點(diǎn)的處理6.5.4幾種特殊情況的處理2.頂點(diǎn)有容量網(wǎng)絡(luò)的處理6.6最小費(fèi)用最大流問(wèn)題在最大流問(wèn)題的基礎(chǔ)上，如果考慮每條弧上的運(yùn)輸費(fèi)用，則是最小費(fèi)用最大流問(wèn)題。其求解的基本思路是：以單位費(fèi)用為網(wǎng)絡(luò)的權(quán)值，求出由S到T的最短路徑（稱為最小費(fèi)用鏈），讓其飽和；再尋找另一條費(fèi)用增加最少的路徑，再讓其飽和，直至找不到由S到T的路經(jīng)為止，即求得該網(wǎng)絡(luò)的最小費(fèi)用最大流。6.6最小費(fèi)用最大流問(wèn)題在最大流問(wèn)題的基礎(chǔ)上，如果考慮每條弧上的運(yùn)輸費(fèi)用，則是最小費(fèi)用最大