《運(yùn)籌學(xué)》圖與網(wǎng)絡(luò)分析培訓(xùn)教材：樹(shù)和最小支撐樹(shù)、最短路問(wèn)題、網(wǎng)絡(luò)最大流

第6章圖與網(wǎng)絡(luò)分析

圖的基本概念與基本定理

樹(shù)和最小支撐樹(shù)

最短路問(wèn)題

網(wǎng)絡(luò)最大流

本章內(nèi)容重點(diǎn)

在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來(lái)畫(huà)出各式各樣的示意圖。

例：公路或鐵路交通圖、管網(wǎng)圖、通訊聯(lián)絡(luò)圖等各節(jié)點(diǎn)及聯(lián)系的邊。如果用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖G可以定義為點(diǎn)和邊的集合G={V,E}式中：V—點(diǎn)的集合,E—邊的集合如果給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù)，如距離、費(fèi)用、容量等這樣的圖稱(chēng)為網(wǎng)絡(luò)圖。

1.圖的基本概念與模型

用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。一般來(lái)說(shuō)，通常用點(diǎn)表示研究對(duì)象用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)系。由于在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯得并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。如圖6-1所示：端點(diǎn)，關(guān)聯(lián)邊，相鄰環(huán)，多重邊，簡(jiǎn)單圖次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)鏈，圈，路，回路，連通圖完全圖，偶圖子圖，部分圖例12.樹(shù)和最小支撐樹(shù)樹(shù)圖（簡(jiǎn)稱(chēng)樹(shù)，記作T（V,E））在各種各樣的圖中，有一類(lèi)圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖，這就是樹(shù)。

性質(zhì)1任何樹(shù)中必存在次為1的點(diǎn)。性質(zhì)2具有n個(gè)頂點(diǎn)的樹(shù)的邊數(shù)恰好為（n-1）條。性質(zhì)3任何具有n個(gè)點(diǎn)、（n-1）條邊的連通圖是樹(shù)圖。2.1樹(shù)的性質(zhì)2.2圖的最小部分樹(shù)如果G1是G2的部分圖，則稱(chēng)G1是G2的部分樹(shù)（或支撐樹(shù)）。樹(shù)圖的各條邊稱(chēng)為樹(shù)枝（假定各邊均有權(quán)重），一般圖G2含有多個(gè)部分樹(shù)，其中樹(shù)枝總長(zhǎng)最小的部分樹(shù)，稱(chēng)為該圖的最小部分樹(shù)（也稱(chēng)最小支撐樹(shù)）定理1圖中任一個(gè)點(diǎn)i，若j是與i相鄰點(diǎn)中距離最近的，則邊[i,j]一定必含在該圖的最小部分樹(shù)內(nèi)。推論把圖的所有點(diǎn)分成V和

兩個(gè)集合，則兩集合之間連線的最短邊一定含在最小部分樹(shù)內(nèi)。練習(xí):寫(xiě)下圖的樹(shù)圖v6v5v2v3v4v1v6v5v2v3v4v1練習(xí)用破圈法求出下圖的一個(gè)樹(shù)圖。V5V4V2V3V1e6e5e4e3e2e1e7e8

取一個(gè)圈(v1,v2,v3,v1)，在一個(gè)圈中去掉邊e3

。在剩下的圖中，再取一個(gè)圈（v1,v2,v4,v3,v1），去掉邊e4

。再?gòu)娜Γ╲3,v4v5,v3）中去掉邊e6

。再?gòu)娜?/p>

(v1,v2,v5,v4,v3,v1

）中去掉邊e7，這樣，剩下的圖不含圈，于是得到一個(gè)支撐樹(shù)，如下圖所示。v2e1e2e5e8v1v3v42.3避圈法和破圈法（1）避圈法從網(wǎng)絡(luò)圖中依次尋找權(quán)數(shù)較小的邊，尋找過(guò)程中，節(jié)點(diǎn)不得重復(fù)，即不得構(gòu)成圈。注意在找較小權(quán)數(shù)邊時(shí)不考慮已選過(guò)的邊和可能造成圈的邊。如此反復(fù)進(jìn)行，直到得到最短樹(shù)或證明網(wǎng)絡(luò)不存在最短樹(shù)。在圖中尋找最小部分樹(shù)的步驟：P153（2）破圈法①在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最短樹(shù)或網(wǎng)絡(luò)不存在最短樹(shù)；②去掉該圈中權(quán)數(shù)最大的邊；反復(fù)重復(fù)①②兩步，直到最短樹(shù)。練習(xí)：用破圈法求出下圖的最小部分樹(shù)圖av6v5v2v3v4v1627535441v3v2v1v4v6v553142圖b最短路問(wèn)題最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問(wèn)題之一。許多優(yōu)化問(wèn)題都可以使用這個(gè)模型，如設(shè)備更新、管道的鋪設(shè)、線路的安排、廠區(qū)的布局等。最短路問(wèn)題的一般提法是：設(shè)為連通圖，圖中各邊有權(quán)(表示，之間沒(méi)有邊）,

為圖中任意兩點(diǎn)，求一條道路，使它是從到的所有路中總權(quán)最小的路。即：最小。最短路算法中1959年由（狄克斯特洛）提出的算法被公認(rèn)為是目前最好的方法，我們稱(chēng)之為算法。下面通過(guò)例子來(lái)說(shuō)明此法的基本思想。條件：所有的權(quán)數(shù)思路：逐步探尋。下求到的最短路：1）從出發(fā)，向走。首先，從到的距離為0，給標(biāo)號(hào)（0）。畫(huà)第一個(gè)弧。（表明已標(biāo)號(hào)，或已走出）從出發(fā)，只有兩條路可走，其距離為2）①可能最短路為①給劃成粗線。③劃第二個(gè)弧。②

給標(biāo)號(hào)（4）。①②表明走出后走向的最短路目前看是，最優(yōu)距離是4?，F(xiàn)已考察完畢第二個(gè)圈內(nèi)的路，或者說(shuō)，已完成的標(biāo)號(hào)。①②3）接著往下考察，有三條路可走：可選擇的最短路為①給劃成粗線。③劃第3個(gè)弧。②

給標(biāo)號(hào)（6）。③①②4）接著往下考察，有四條路可走：可選擇的最短路為①給劃成粗線。③劃第4個(gè)弧。②

給標(biāo)號(hào)（8）。①②③④5）接著往下考察，有四條路可走：可選擇的最短路為①給劃成粗線。③劃第5個(gè)弧。②

給標(biāo)號(hào)（9）。①②③④⑤6）接著往下考察，有四條路可走：可選擇的最短路為①給劃成粗線。③劃第6個(gè)弧。②

給標(biāo)號(hào)（13）。①②③④⑤⑥7）接著往下考察，有四條路可走：可選擇的最短路為①同時(shí)給劃成粗線。②分別給標(biāo)號(hào)（14）。最后，從逆尋粗線到，得最短路：長(zhǎng)度為14。最短路問(wèn)題的兩個(gè)應(yīng)用最短路問(wèn)題在圖論應(yīng)用中處于很重要的地位，下面舉兩個(gè)實(shí)際應(yīng)用的例子。例1設(shè)備更新問(wèn)題某工廠使用一臺(tái)設(shè)備，每年年初工廠要作出決定：繼續(xù)使用，購(gòu)買(mǎi)新的？如果繼續(xù)使用舊的，要負(fù)維修費(fèi)；若要購(gòu)買(mǎi)一套新的，要負(fù)購(gòu)買(mǎi)費(fèi)。試確定一個(gè)5年計(jì)劃，使總支出最小若已知設(shè)備在各年的購(gòu)買(mǎi)費(fèi)，及不同機(jī)器役齡時(shí)的殘值與維修費(fèi)，如表2所示.項(xiàng)目第1年第2年第3年第4年第5年購(gòu)買(mǎi)費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210表2解：把這個(gè)問(wèn)題化為最短路問(wèn)題。用點(diǎn)表示第i年初購(gòu)進(jìn)一臺(tái)新設(shè)備，虛設(shè)一個(gè)點(diǎn)，表示第5年底。邊表示第i年購(gòu)進(jìn)的設(shè)備一直使用到第j年初（即第j-1年底）。邊上的數(shù)字表示第i年初購(gòu)進(jìn)設(shè)備，一直使用到第j年初所需支付的購(gòu)買(mǎi)費(fèi)、維修的全部費(fèi)用（可由表8-2計(jì)算得到）。這樣設(shè)備更新問(wèn)題就變?yōu)椋呵髲牡降淖疃搪穯?wèn)題.項(xiàng)目第1年第2年第3年第4年第5年購(gòu)買(mǎi)費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210表2⑴①⑵

給劃成彩線。②⑶①②

給劃成彩線。⑷③

給劃成彩線。④⑸①②③④

給、劃成彩線。⑤①②③④⑤⑹

給劃成彩線。計(jì)算結(jié)果：最短路①②③④⑤最短路路長(zhǎng)為49。即：在第一年、第三年初各購(gòu)買(mǎi)一臺(tái)新設(shè)備為最優(yōu)決策。這時(shí)5年的總費(fèi)用為49。例3(選址問(wèn)題)已知某地區(qū)的交通網(wǎng)絡(luò)如圖所示，其中點(diǎn)代表居民小區(qū)，邊代表公路，邊權(quán)為小區(qū)間公路距離，問(wèn)區(qū)中心醫(yī)院應(yīng)建在哪個(gè)小區(qū)，可使離醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路程最近？解求中心的問(wèn)題。解決方法：先求出到其它各點(diǎn)的最短路長(zhǎng)如再求即為所求。比如求⑴⑵

給劃成彩線。⑶

給劃成彩線。給標(biāo)號(hào)20。⑷給劃成彩線。給標(biāo)號(hào)30。⑸分別給劃成彩線。分別給標(biāo)號(hào)33。⑹給劃成彩線。給標(biāo)號(hào)63。其它計(jì)算結(jié)果見(jiàn)下表：

小區(qū)號(hào)030506393456093300203363153063502002050254050633320030183363936350300486393451525184801548603040336315063表1由于最小，所以醫(yī)院應(yīng)建在，此時(shí)離醫(yī)院最遠(yuǎn)的小區(qū)距離為48。第四節(jié)最大流問(wèn)題最大流問(wèn)題是一類(lèi)應(yīng)用極為廣泛的問(wèn)題，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車(chē)流、貨物流、供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。一．有關(guān)概念：例：下圖是輸油管道網(wǎng)，為起點(diǎn)，為終點(diǎn)，，，，為中轉(zhuǎn)站，邊上的數(shù)字表示該管道的最大輸油能力（也稱(chēng)容量），記為，問(wèn)應(yīng)如何安排各管道輸油量，才能使從到的總輸油量最大？①分別稱(chēng)為發(fā)點(diǎn)、收點(diǎn)。其余的點(diǎn)稱(chēng)為中間點(diǎn)。②

每一個(gè)邊上都給定一個(gè)容量的網(wǎng)絡(luò)稱(chēng)為容量網(wǎng)絡(luò)，記

的每一個(gè)邊上都給定一個(gè)實(shí)際流量的網(wǎng)絡(luò)稱(chēng)為給定了網(wǎng)絡(luò)一個(gè)流。④容量限制條件：對(duì)每一邊上都有⑤平衡條件：a)中間點(diǎn)：流入量=流出量。

b)發(fā)收點(diǎn)：發(fā)出流量=匯入流量。若，稱(chēng)邊是飽和邊。⑥

可增廣鏈：是指從到有一條鏈，此鏈上有≤的現(xiàn)象出現(xiàn)。（非飽和鏈）這種流稱(chēng)為可行流。上圖就是一個(gè)可行流。使流量達(dá)到最大的流稱(chēng)為最大流。二．求解最大流：先給標(biāo)號(hào)（?，+∞），其中?意思是流入的結(jié)點(diǎn)，現(xiàn)沒(méi)有，純屬一個(gè)符號(hào)。+∞表示的流出量。因它上面沒(méi)有結(jié)點(diǎn)來(lái)控制它，故設(shè)為+∞.1）尋找可增廣鏈：b)接著檢查與相鄰接的點(diǎn)，，。已飽和，流量不可再增。再檢查，可調(diào)整量為4-2=2，可提供量+∞，取調(diào)整量給標(biāo)號(hào)，其中表示的所調(diào)整量2來(lái)自，且為正向流（向前流）。同理，給標(biāo)號(hào)下對(duì)已標(biāo)號(hào)點(diǎn)（可望調(diào)整點(diǎn)）接著向下檢查。已飽和。再檢查與相鄰接且未標(biāo)號(hào)的點(diǎn)調(diào)整量為給標(biāo)號(hào)為d)檢查與相鄰接且未標(biāo)號(hào)的點(diǎn)，。而對(duì)來(lái)講是流入，現(xiàn)欲增加流出量，應(yīng)壓縮的流入量，只要的流入