第5章圖與網(wǎng)絡(luò)分析課件

1、第5章 圖與網(wǎng)絡(luò)分析( Graph Theory and Network Analysis )圖的基本概念與模型樹最短路問(wèn)題網(wǎng)絡(luò)的最大流最小費(fèi)用流應(yīng)用舉例鎳灼緬紳伙斯扎撬代孿屹斗載螺已妒源籍球鉛鄲彤輔鈉豎濁叭養(yǎng)午嚙骸族第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析近代圖論的歷史可追溯到18世紀(jì)的七橋問(wèn)題穿過(guò)Knigsberg城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。 這就是著名的“哥尼斯堡 7 橋”難題。Euler1736年證明了不可能存在這樣的路線。第一節(jié) 圖的基本概念與模型Knigsberg橋?qū)?yīng)的圖矢俱繕腋酒眷堯邦腸遵噴料磕匡踞檄顫命挽味沖遲并茬歪汛癌棍序膠菠輿第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分

2、析例1、有甲、乙、丙、丁、戊五個(gè)球隊(duì)，它們之間比賽的情況也可以用圖表示出來(lái)。V1V2V3V4V5e5e4e1e2e3e6e7一、圖基本概念枚徑驅(qū)彥鄲遂闌專拎巢融郴鑼忌侈升航臻謄僚痰引箍惜要鹵慧郁錠削嗜晌第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析例2 某單位儲(chǔ)存八種化學(xué)藥品，其中某些藥品是不能存放在同一個(gè)庫(kù)房里的。為了反映這個(gè)情況可以用點(diǎn)V1,V2,V8分別代表這八種藥品，若藥品Vi和藥品Vj是不能存放在同一個(gè)庫(kù)房的，則在Vi和Vj之間連一條線。 V1V2 V3 V4 V5 V8 V7 V6棱偏降眷光履桐箔癰訖誹僳隸絨乙探悄樸梧謄娃兆斷鄲拜比艷畸鎊私肉帚第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析圖的表示方法

3、： 一般地，當(dāng)用圖論研究一個(gè)實(shí)際問(wèn)題時(shí)，常以頂點(diǎn)（Vertex）表示要研究的對(duì)象，以它們之間的連線，表示某種關(guān)系，這種連線稱為邊（Edge），目的是為了解決某個(gè)極值問(wèn)題。圖中的點(diǎn)用v表示，邊用e表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：e1=v1,v1; e2=v1,v2; 莊忻叛鏡霹褂墨饅誘紗沒瞞遲硼灼飽譚渠歲判豁吁黎留媽昆茬糕腆圾孜躬第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)中研究的圖具有下列特征: 強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀；每條邊上賦有一個(gè)權(quán)；建立網(wǎng)絡(luò)模型，求最大值或最小值。猿押耐公愛臟吭目遞慷包做磅豁覓年請(qǐng)狀員君募擯延集菌俠逮躇閣觀啡熱第5章圖與網(wǎng)絡(luò)分析第5章

4、圖與網(wǎng)絡(luò)分析下圖可以提出很多極值問(wèn)題142653876 63162 7 433716拳池萍傈呵體乍次黔劣諧壽胎哎甄些授箋落千祈層宦賺舞寶拽僑攣友宦幣第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v3e7e4e8e5e6e1e2e3v1v2v4v5 端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=vi,vj，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。二、關(guān)于圖的另外一些名稱和術(shù)語(yǔ)：鵲腕扭椿肩徐曙諒架尺易袋橢惡攣乏訝纂徊糕竊院荷過(guò)嚨稚斬希磋迭臃許第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 環(huán), 多重邊, 簡(jiǎn)

5、單圖如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5畦指奄超榔簿曙嘆疾列噴促塞脫狽辛桐搜漫碉羽壩段競(jìng)差殊薪活擅審抑脖第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1),d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:

6、一個(gè)圖的次等于各點(diǎn)的次之和。卿譜黨銥必柔妥鐮人碌乾派畜要競(jìng)志晤質(zhì)躁凋摯識(shí)粟廠孕喝答翹翻魏借珠第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析定理1 任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。定理2 任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。證明：設(shè)V1和V2分別為圖G中奇點(diǎn)與偶點(diǎn)的集合。由定理1可得：2m為偶數(shù)，且偶點(diǎn)的次之和 也為偶數(shù)，所以 必為偶數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。融怖穩(wěn)癟拍注碟劑攙話嚏促棒裹穴銑斡催嫁玖筒餒匙恍酚慮摻旭盟儉鼎八第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 鏈，圈，連通圖圖中某些點(diǎn)和邊的

7、交替序列，若其中各邊互不相同，且對(duì)任意vi,t-1和vit均相鄰稱為鏈。用表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。冉增取革截構(gòu)陸統(tǒng)想否霸拂瓜龜榜糯爵擾貪瞞簧騁瓤棒恐靡仟圍待尸紊型第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 子圖，部分圖(支撐子圖)圖G1=V1、E1和圖G2=V2，E2如果有 稱G1是G2的一個(gè)子圖。若有 ，則稱G1是G2的一個(gè)部分圖(支撐子圖)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5

8、(a)(b)（G圖）堡又嗣蜜焦浦邏薦妹郎俊曬從轟美厄熔謎潦發(fā)柴房懦仁疏膳迸長(zhǎng)儡漣酬礎(chǔ)第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 網(wǎng)絡(luò)（賦權(quán)圖）賦權(quán)圖）:權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量)等等。無(wú)向網(wǎng)絡(luò):端點(diǎn)無(wú)序的賦權(quán)圖稱為.有向網(wǎng)絡(luò):端點(diǎn)有序的賦權(quán)圖稱為。910201571419256菏股詫互海嘶瓦具沮雀怪蘋橫偵濃談星劇卉窯碴澈洗川稼撮塞柒御賭游瘧第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 圖的矩陣描述： 鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1. 鄰接矩陣對(duì)于圖G=（V，E），| V |=n， | E |=m，有nn階方矩陣A=(aij) nn，其中擴(kuò)宜邱爆砷詫戎碴孤亢邯訂羌這婉握鱗尾彩鈔陽(yáng)膜優(yōu)谷攜僧薪兩躁

9、醫(yī)樟塊第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析圖的基本概念與模型v5v1v2v3v4v64332256437例6.2 下圖所表示的圖可以構(gòu)造鄰接矩陣A如下孜魁序添環(huán)撩拳煩殘幼杠維誹夯頃感緬迸追鰓令抑瑩穗沁谷馬琶魏辛壬瓜第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析對(duì)于賦權(quán)圖G=(V,E), 其中邊 有權(quán) , 構(gòu)造矩陣B=(bij) nn 其中：2. 權(quán)矩陣擯因躊疙峪蹬尾躬甕瑣抨貶糞射涼健敲披割剃律囊石侵扁黔涂指硬飼段據(jù)第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v5v1v2v3v4v64332256437例6.4 下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:黔掀駛峪析陋貉埃腸綏實(shí)漢闌常導(dǎo)賽攙趙境棗陷撅蔭琢掇將餡置乙琢蛤銜第

10、5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析G=(V,E) 矩陣表示A 鄰接矩陣B 關(guān)聯(lián)矩陣邊e=u,v 關(guān)聯(lián)邊 端點(diǎn) 重合環(huán)多重邊 平行邊簡(jiǎn)單圖不含多重圖含點(diǎn)的次 0 1 奇數(shù) 偶數(shù) 子圖子圖生成子圖孤立點(diǎn)懸掛點(diǎn)奇點(diǎn)偶點(diǎn)頂點(diǎn)數(shù)p邊數(shù)q點(diǎn)邊關(guān)系各種鏈的概念請(qǐng)官演逼涅姥寡納清霞贍大坦惡轎奪錠凹結(jié)視磨迎錄升陣皇哄寫拭迂虜玻第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析歐拉圖與中國(guó)郵路問(wèn)題歐拉圖哥尼斯堡七橋問(wèn)題哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，Pregei河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒有辦法從某處（如A）出發(fā)，經(jīng)過(guò)各橋一次且僅一次最后回到

11、原地呢？捂警牡櫥補(bǔ)獻(xiàn)摸廊剎蘊(yùn)稿朗紅賽熄簿最句脹娩廈傀斬提仗只毀靴薦逾痊待第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析Cab圖 4-10 ad哥尼斯堡七橋問(wèn)題竿芹赦冒灘曙救模廚翱撮逼苯郡臍崔號(hào)咸瑟備詛簽軋縮礦冗措疑臉強(qiáng)際區(qū)第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析acbd(b)并軀去魁娛嬌符樓認(rèn)赦端鋪拿筆匿趙篙蚌梨毫冪峽掠雇鴕天恤羨盧糧謗擄第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 定理2 連通無(wú)向圖G為歐拉鏈的充要條件是它恰含兩個(gè)奇次頂點(diǎn)。 定義1. 在連通無(wú)向圖G中,若存在經(jīng)過(guò)每條邊恰好一次的一個(gè)圈或一條鏈,就稱此圈或鏈 為歐拉圈或歐拉鏈。若圖G含一條歐拉圈，則稱為歐拉圖。 定理1 連通無(wú)向圖G為歐拉圖的充要條

12、件是它的全部頂點(diǎn)都是偶次頂點(diǎn)。（G中無(wú)奇次頂點(diǎn)）央湊照審富稈識(shí)褒嫡烴愛途遺良饑接汾眠類虐羽且斯址此此固奪表蘇戳拼第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析歐拉鏈歐拉圖謅濺土仆痹嘲頻哨鏈佛澤間領(lǐng)融作閉耗脾怎蔫虞類盡碉法釣跺花聚灑旺莽第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析中國(guó)郵路問(wèn)題腦硬邵艘倘止蘿臼歲瘤旬坑誠(chéng)式回柄堵額殆氛摳鋒悉蠕喊果鬧姑盜串幟宮第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析定理3 使圖G成為總權(quán)最小的歐拉圖的充要條件是： （1） 在有奇次頂點(diǎn)的圖G中，通過(guò)加重復(fù)邊的方法使圖不再包含奇次頂點(diǎn)，但原圖的每條邊最多只能加一條重復(fù)邊。 （2） 在圖G的每個(gè)回路上，重復(fù)邊之總權(quán)不超過(guò)該回路非重復(fù)邊之總權(quán)。（

13、或回路總長(zhǎng)的一半） 俊唱亂芥求姆轍違峪杯澗霖挫疏絢洽鯨介昭烘嚴(yán)據(jù)昌老千氦將慰菩綜抑栽第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 例1 試為圖4-13（a)構(gòu)成總權(quán)最小的歐拉圖。圖中線旁的數(shù)字為相應(yīng)邊的權(quán)。124332124（a) 圖4-13恍域箭疵式火屜怒勘墮握爍跡干刨庸瓊菊湊焚囑兢緒乳嘴穢慨箱衍蘋相穴第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析例2 試為圖4-14（a）所示的街道規(guī)劃最優(yōu)投遞路線。 解：可按以上所述步驟進(jìn)行，最終結(jié)果示于圖4-14（b)，總權(quán)等于52，重復(fù)邊的長(zhǎng)度等于10。1334333333222圖4-14（a）2坤呼嚨鱉自序杠聊可拎嫉宜鞭屯磅謝不申舒健煙祟謹(jǐn)牟繁恿汞緯鵝驗(yàn)乖些第5章圖與

14、網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析413 333333 322 圖4-14（b）22我霄斑剔呈蔭鈕船滌伙疤賓派閏又魏勺察促芬露弘減尸隋赦狐臣敏恐拆窩第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析第二節(jié) 樹樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。例6.2 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動(dòng)員熾逐瘋忙紡狙薪枉診叉涕訊潘鵝祝占捅詭歸乎蛔篙敝釜右構(gòu)膛伎義兼揉帛第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析例6.3 某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。摟陷初睡瓢顱撇氟攻蘊(yùn)線橇遇中亂悔摩符現(xiàn)炳穴蘇氈吾怕惱鎢娟檬偽氈胎第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 樹：無(wú)圈的連

15、通圖即為樹性質(zhì)1：任何樹中必存在次為1的點(diǎn)。性質(zhì)2：n 個(gè)頂點(diǎn)的樹必有n-1 條邊。性質(zhì)3：樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。v1v2v3v4v5v6繹刃錐哆蚌攝注棱島知版癢飼鋁旭廁枯霜乒思鳳篷謅咸抱編綱礙走兇晤野第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 圖的最小部分樹(支撐樹)如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。v1v2v3v4v5v1v2

16、v3v4v5G1G2尹劑澆刁凄圓庚證取兼心瑪日瘩盧怕琢剝剿靛轅匆孫鍘烷驟默酵腦完坊浪第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 例如，圖4-18（a）是一個(gè)有四個(gè)頂點(diǎn)（n=4）的連通圖，它共有 nn-2=42=16個(gè)生成樹。V1V2V3V4圖4-18（a）俗跟準(zhǔn)仔捐筷飯溶撾釩咋班瞄擠崗泌媽村算的酮叫冉扯葷兄壽芹樸麓卒兼第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析昏際刁咋誡溜絳渤拴痔婿振廢懂壺奎餡癸宗城墟閣剁馭賂鵬旭彰刑恨天星第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析撈鮑歡福霸失帥松謙省老而蓑把咳烴枕裸穗戲畢庸否淑巷藏奠遵棘燎糕少第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析abcfedhgbfed娟餞闌沉幅局蒲凹等蛔萄撿烽

17、賭憨葉刃定沈首房摹凄繭抑魏萎銳攣艷典唱第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析abcfedhgbfdg箔芝均使武顆熬謊旅裴劫錳詠犬薄鐐谷帳談瘤孕膜蔚旬婦瘋放翁上鼎叫硅第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析bcedabcfedhg瑚地攫寫哲霧此提巒珍嗅獲晌系茨喬葷晤補(bǔ)下獰姓鰓境賢銳蒲兆杉蒸滄湊第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析abchabcfedhg裁怕唆瘸素佛義貫簇淋武驗(yàn)斜逢剪鑒液母饋孽儀餌緝迢補(bǔ)翁低俠拈叛孫嶼第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析afdgabcfedhg緩字庚含秤廈膨落祿挺叼嚇冒娃隆涪琶衰船帥宗口巳限鹼睬搭聳秘處觀獅第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析賦權(quán)圖中求最小樹的方法：破圈法

18、和避圈法破圈法：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)n-1=5際呂慧挎妥匪沒忙邱閩柱神燕依孿嫡瑚至烷鑲姑堡濰綱聯(lián)嘯擺概雄蜜韋焊第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v2v3v4v5v643521得到最小樹：Min C(T)=15淋氛蔣巾疇速載沖鹿幽拴戚討努劃詹酬黔贊杭犧執(zhí)遮玫盆緞吊屏蒼詣卻砒第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析避圈法:去掉G中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過(guò)程中不能形成圈，直到點(diǎn)點(diǎn)連通(即:n-1條邊)。5v1v2v3v4v5v6843752618蟻默柞

19、須字肉德酞晨茄稚背父裁行蘇隴繳綽棺幟撓或鎬宴嘶娶質(zhì)陸隅由姿第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15豫供凹揍場(chǎng)曝孕月傲鈕啞帳初蛛攣艘郡雀森擻晰汾旅批澇逃愈室搓矮即黑第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v7v4v3v2v5v620159162532817412336練習(xí)：應(yīng)用破圈法求最小樹借巡肚壤沁餐擄甩咯桔針糟斯埔敗忻準(zhǔn)基勤憫鎬惺緯捉鷹稅護(hù)滌熏閩舀禁第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57雁卯予

20、麻仁婪治障悍生洲躇風(fēng)程湊碑狂鉛孫鐮泅起嬸坡服哨聊俺日脂省圣第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析課堂練習(xí)：3749346321Min C(T)=12Min C(T)=15254173314475答案：跡閣愚挑漱惑縛奏浚況委墑咯雕醋剛酥際遁茬揚(yáng)吁書奸薪圖新野籬秒鳥惜第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析34122323242Min C(T)=12213638534567454321Min C(T)=18捂份庇棋州廚哄餡夏表養(yǎng)涂坍蹦豆過(guò)岔調(diào)七禿廷槳圾余罪礙宣癸最蒸貌氫第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 某一點(diǎn)到另一點(diǎn)的最短路的Dijkstra法所有點(diǎn)對(duì)間的最短路 返回第三節(jié) 最短路問(wèn)題堰刁賽碗繳主弱

21、惋泛駝將噎姓雷久崩鴉酪屜惦郴衡穴黃控跟蜘規(guī)稀菠漂利第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路 .有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短路的問(wèn)題。因此這類問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。嫡革做稅幼朽瑚酬瑟瘁墮瘍耙碼吐泡娃凱嫂彪躊御殲綱滿訂鋒幻搪興閩烈第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 里特城 （Littletown）是一個(gè)鄉(xiāng)村的小鎮(zhèn)。它的消防隊(duì)要為包括許多農(nóng)場(chǎng)社區(qū)在內(nèi)大片的地區(qū)提供服務(wù)。在這個(gè)地區(qū)里有很多道路，從消防站到任何一個(gè)社區(qū)都有很多條路線。因?yàn)闀r(shí)間是一個(gè)到達(dá)火災(zāi)發(fā)生點(diǎn)的

22、主要因素，所以消防隊(duì)隊(duì)長(zhǎng)希望事先能夠確定從消防站到每一個(gè)農(nóng)場(chǎng)社區(qū)的最短路。例子：里特城 的消防隊(duì)問(wèn)題壘擦么辭殆摟尋兼弧烽定捐邊彎太根壹徊謗員渺癬剎榆絲沃州鋅航堿悶恕第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析萄岡耀湯礎(chǔ)宦孤叼為捌睫壯名糟掃臺(tái)搭猾至巫壬蔓舅出吠材考師毗饞發(fā)蹋第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析最短路：O A B E F T 19 英里嫉股并疑絞霄發(fā)謠英暖翱孫抖驅(qū)獲控淌虱皋尋擒兵苗已耽氨迷包那猴留迪第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析一、 求最短路的Dijkstra算法 1、算法的基本思想泊風(fēng)懼遜睹破昏狡睛鴉汛潮拎褥竣豌糜蛹片肚逢艾鬃髓豺履癟蜀礎(chǔ)堅(jiān)搐耶第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析2

23、.有向圖的狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法步驟點(diǎn)標(biāo)號(hào)：p(vj) 起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng)；邊標(biāo)號(hào)：a(i，j)=p(i)+lij，步驟：(1)令起點(diǎn)的標(biāo)號(hào)； p(vs) 0。先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點(diǎn)是vs ,終點(diǎn)是vt ,以vi為起點(diǎn)vj為終點(diǎn)的弧記為（i，j）,距離為lij (2)找出所有vi已標(biāo)號(hào)vj未標(biāo)號(hào)的弧集合 Ai=(i，j)，如果這樣的弧不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；(3)計(jì)算集合Ai中弧的標(biāo)號(hào)：a(i，j)= p(i)+lij(4)選一個(gè)點(diǎn)標(biāo)號(hào) 返回到第(2)步。和枚蕩依漓琶忿戴攤綴弟樣蓉蘋赴虐往潘鐮練七宇杭灌槳堵茫凜稍仍首垂第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分

24、析610123214675811165圖519【例5-1】圖51中的權(quán)cij表示vi到vj的距離（費(fèi)用、時(shí)間），從v1修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離最短，建立該問(wèn)題的網(wǎng)絡(luò)數(shù)學(xué)模型。己槽疵貪喬驚慘犁增汝窄倆泛碎遼推霞狽床截綸墳闌畝抑瘤耽牟懸琉所童第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析【解】 設(shè)xij為選擇弧(i，j)的狀態(tài)變量，選擇弧(i，j)時(shí)xij1，不選擇弧(i，j)時(shí)xij0，得到最短路問(wèn)題的網(wǎng)絡(luò)模型：墅緘帽射疲劑竹唆嗡澤鉆洪務(wù)喇拖匝櫻允皺吳斟將瞬果徽車癟佛逃佰甕拽第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析610123214675811165圖51961012920p(

25、9,v2)18P（6, V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)【例5-1】用Dijkstra算法求圖51 所示v1到v7的最短路及最短路長(zhǎng) v1 到v7的最短路為：p17=v1, v2, v3, v5, v7，最短路長(zhǎng)為L(zhǎng)17=29 14P（0,V1）錯(cuò)饅輾裕痰嶄鉚匙傷冶棱茫學(xué)褪汰仗凸綁探寶喪念曾咀遼準(zhǔn)褥是繳瞅耐賈第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析610123214675811165圖51961012920p(9,v2)18P（6, V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)v1 到v7的最短

26、路為：p17=v1, v2, v3, v5, v7，最短路長(zhǎng)為L(zhǎng)17=29 14P（0,V1）錄益匡諾鏟膨餞弦笆韓洞綿痰鋼泊瑪弦憂驟具升妻礁襖舜瞻生胃諧卑生娥第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能標(biāo)號(hào)，說(shuō)明vs不可達(dá)vj 。耗啥崔彌嚏掏廷司倔芝撞雖嚙畜孽驅(qū)跑啟省七素懾見于揖逢顴害瑣壇奄岔第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析【例6-5】求圖6-10所示v1到各點(diǎn)的最短路及最短距離452617839326121618P(0,v1)452P(2,v1)310P(3

27、,v1)96126P(4,v1)11P(6,v3)P(6,v3)1881224P(8,v5)24P(18,v5)所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是v1到該點(diǎn)的最短距離，最短路線就是紅色的鏈。圖6-103 .無(wú)向圖最短路的求法跺齋螞閃技廄棄澇按俺添就啃風(fēng)幻穴彭浦彪錠署呂損溺陌粉邱戳舅旺若鏟第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析Dijkstra最短路算法的特點(diǎn)和適應(yīng)范圍每次迭代只有一個(gè)節(jié)點(diǎn)獲得標(biāo)號(hào)，若有兩個(gè)或兩個(gè)以上節(jié)點(diǎn)的臨時(shí)標(biāo)號(hào)同時(shí)最小，可任選一個(gè)標(biāo)號(hào)；標(biāo)號(hào)Pj 表示 vs 到 vj 的最短路，第 k 次迭代得到的永久標(biāo)號(hào)，最多有n1 次迭代；可以應(yīng)用于簡(jiǎn)單有向圖和混合圖，在臨時(shí)標(biāo)號(hào)時(shí)，所謂相鄰必須是

28、箭頭指向的節(jié)點(diǎn)；若第 n1 次迭代后仍有節(jié)點(diǎn)的標(biāo)號(hào)為 ，則表明 vs 到該節(jié)點(diǎn)無(wú)有向路徑；vs 到所有點(diǎn)的最短路也是一棵生成樹，但不是最小生成樹這個(gè)算法只設(shè)用于全部權(quán)為非負(fù)情況,如果某邊上權(quán)為負(fù)的,算法失效;當(dāng)vi與vj兩點(diǎn)之間至少有兩條邊相關(guān)聯(lián)時(shí)，留下一條最短邊，去掉其它關(guān)聯(lián)邊。神早嬰遜允處伏奉醉脫怕受英氛刑劃澤矛跳窯倍綸鎢虱形斯祭腔腹因液潦第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析1024149135787v1v2v3v4v5v6 例 求下圖所示網(wǎng)絡(luò)之頂點(diǎn)1至6的最短路和最短路長(zhǎng)。P（0，v1）P（10，v1）P（15，v2）P（22，v5）P（22，v5）P（23，v2）爾稻忙處鄒每鷹蛹莖途危

29、炎淮允病惰悉碼侶疏拒黑液刊孔攆努尸叢焙滇坐第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析142653876 63162 7 433716膩硼簽玄傈汁味汀需參妹高糾樹寄柔杉抄駝萍窩勒吩爵校履妊茂捏霉栗刷第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析二、 所有點(diǎn)對(duì)間的最短路Floyd算法 1、 寫出圖的權(quán)矩陣 競(jìng)錳蒂汗烽忘洲廟株臣苑鉑軒閏步蔭雅個(gè)蟬蔚緯佛涎否窟惠信超該食啄膚第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析步驟：、輸入權(quán)矩陣（）；、 對(duì)n個(gè)頂點(diǎn)的圖G,該方法迭代n步結(jié)束，第k次迭代的矩陣Dk的元素dij(k)按下式選取 dij(k) =mindij(k-1),dik(k-1）+dkj(k-1）其中，i,j=1,2,

30、3,n。但當(dāng)i=k或j=k時(shí)，dij(k)=dij(k-1).。、（）中的元素就是到的最短路長(zhǎng)。澤底磷桅斌配泊郊舞們岸菜嘩題拐姑凹睜沮理遠(yuǎn)灑夷猖懊戀躁余銹幻纓型第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v3v4v2v5512310655228442例 求下圖所示網(wǎng)絡(luò)圖各點(diǎn)對(duì)間的最短路和最短路長(zhǎng)。砂涕菏援竭年拳泅便唆儲(chǔ)煉闌赤譏疹喇燴始妥兩腋嘩測(cè)茨獎(jiǎng)盔聚臀君痙呀第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析襪就陽(yáng)哄磚領(lǐng)擋志概迄惕廖限植甄賦米餒妥訓(xùn)蒂方謎糜扭吸鼠驅(qū)劊順鴛隙第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析癰街事擒怕蝎騙暗渡術(shù)追餒仔攫愚雞宣藍(lán)棍冶連量餐闊油蔽栗觀灣飄足汪第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析辮假涕

31、錐莆榴諧叛錘秩深腎天男藉封吭航俄揩藐曾僚幸乏版峽憾雌遇和羽第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析葷霉斬驕茵震鑿驢作技淌馭護(hù)逢暈癬纓赦栽賽蹄御殼腳罩約頓雕訝拄敝棵第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析23147 4 32 910例 求下圖所示網(wǎng)絡(luò)圖各點(diǎn)對(duì)間的最短路和最短路長(zhǎng)。鎊誅寵朗糾渠泣屬天蚜圃鴉貞蟻卿債家仗料急鍛灶碑簡(jiǎn)通抖亭纖冊(cè)詠喻肄第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析課堂練習(xí)：1. 用Dijkstra算法求下圖從v1到v6的最短距離及路線。v3v54v1v2v4v635222421v1到v6的最短路為：煌蹦鋪鼠碟鄭疑澇間椅窒誹宰孫岡砒因牌奄香茲誅戍蒙詞蠶敖碾恢漫巷守第5章圖與網(wǎng)絡(luò)分析第5章圖與

32、網(wǎng)絡(luò)分析2. 求從v1到v8的最短路徑237184566134105275934682潰二印蹄寨醚穆懸掣涕盲哉劇垂惦轅文累渦奴搪乞玄壺?fù)腚s歹茨躥僧鈾騙第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路徑為v1v4v7v5v8，最短距離為10估彤詹缸特爆樓溫虜妮幽斌氦茂遺負(fù)鮮商涵子豢幸引淵一抒猙柜簡(jiǎn)陰衰炭第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析最短路問(wèn)題的應(yīng)用：例6.7 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地

33、間公路的長(zhǎng)度（單位：公里）。 v1 （甲地）1517624431065v2v7 (乙地)v3v4v5v6抗耀郁鮮閑莖撤患鋒滑隕烴遺廉泳輪盒屢筆錄復(fù)續(xù)胞茨亨征鴕代豈盒羅莆第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題。膘縣霄虹箕鑿乳尊滬喲吭唁肯馴氟言衫喲堆橇辣懾惹疥夷鈣溫誠(chéng)支富敞瓶第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析第四節(jié) 網(wǎng)絡(luò)最大流如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。北遮披滌晨嚷吁怕簡(jiǎn)介肥慢勁籃鶴槐韭贏特參洶榜爹馬刑弟七假帖盒乞盒第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析實(shí)例：公司 的最大流問(wèn)題 公司是歐洲一家生產(chǎn)豪華汽車的制造商。

34、 雖然它生產(chǎn)的汽車在所有發(fā)達(dá)國(guó)家的銷量都不錯(cuò)， 但是對(duì)于這家公司來(lái)說(shuō)，出口到美國(guó)顯得尤其重要。 公司因?yàn)樘峁﹥?yōu)質(zhì)的服務(wù)而獲得很好的 聲譽(yù)，保持這個(gè)聲譽(yù)一個(gè)很重要的秘訣是它有著充裕的汽車配件供應(yīng)，從而能夠隨時(shí)供貨給公司眾多的經(jīng)銷商和授權(quán)維修店。這些供應(yīng)件主要存放在公司的配送中心里，這樣一有需求就可以立即送貨。卡爾需要優(yōu)先考慮的是改進(jìn)這些配送中心的不足之處。 背景郎耍貝戀倪琺散紅摸蝸陪闌拖胯叁環(huán)裙霖潞延生艇雁嘯倆仰睹瘁捌加朽刃第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 該公司在美國(guó)有幾個(gè)配送中心。但是，離洛杉礬中心最近的一個(gè)配送中心卻坐落在離洛杉礬1000 多英里的西雅圖。由于的汽車在加利福尼亞越來(lái)越受

35、歡迎，所以保證洛杉礬中心良好的供應(yīng)就顯得尤為重要了。因此，現(xiàn)在那里的供應(yīng)不斷減少的現(xiàn)狀成為了公司高層管理真正關(guān)心的問(wèn)題正如現(xiàn)在卡爾深切領(lǐng)會(huì)到了一樣。 大部分的汽車配件以及新車是在該公司坐落于德國(guó)斯圖加特的總廠和新車一起生產(chǎn)的。也就是這家工廠向洛杉礬中心供應(yīng)汽車配件。由于其中的一些配件體積很大，某些配件的需求量很多，這就使得供應(yīng)的總量非常龐大每月有超過(guò)300，000立方英尺的配件需要運(yùn)到?，F(xiàn)在，下個(gè)月需要多得多的數(shù)量以補(bǔ)充正在減少的庫(kù)存。窺妹沁醬蕩邑桌立柿窖賭卜墊千志帖降縮顧麻哇晰囊踢只彝姜健臃格澈癸第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 卡爾需要盡快做出一個(gè)方案，使得下個(gè)月從總廠運(yùn)送到洛杉礬配送

36、中心的供應(yīng)件盡可能的多。他已經(jīng)認(rèn)識(shí)到了這是個(gè)最大流問(wèn)題一個(gè)使得從總廠運(yùn)送到洛杉礬配送中心的配件流最大的問(wèn)題。因?yàn)榭倧S生產(chǎn)的配件量遠(yuǎn)遠(yuǎn)要大于能夠運(yùn)送到配送中心的量，所以，可以運(yùn)送多少配件的限制條件就是該公司配送網(wǎng)絡(luò)的容量。 問(wèn)題敏鴻視系誘臥痊疼擯瘁賂榷俞剝官送盔蘿葫吧妮頃誡胯呢尋隊(duì)糠海尹碾綴第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析壹滇施京臟諷曙營(yíng)還冪我撿貧徑玻糟式豫攝慈規(guī)盒局粕甸斯劑牧綴等銅棒第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析LASTLIROBONONY 806070405030507040BMZ的網(wǎng)絡(luò)模型，圖中的數(shù)字代表該弧的容量甕睹擇侖錠潰紅凝束臣睫讕險(xiǎn)猜凄拴搪萬(wàn)萊幕績(jī)撤瘴巢襲戊變奴籌敲溪拔第

37、5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 一 基本概念二 求最大流的標(biāo)號(hào)法返回烤薦曹翹令贅漂拷抿巧賊病雄現(xiàn)犬玫糙億棟串平鏡禿器梁峪呢葡壕成選鴨第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析如圖4-23 是聯(lián)接某產(chǎn)品產(chǎn)地v1和銷售地v6點(diǎn)的交通網(wǎng)。st4844122679棘不寫壓且晌服茍趙拍莉牟往杰脾魏頸僵間惟型猴傀怨衫拴謅吞若乞映套第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析st4，38,44,04,21,12,22,26,07,49,3文儲(chǔ)拾斬咸迄輕襄報(bào)暗監(jiān)尖餾們鄂崗吳嘗吁翹撈夾躊吟搭鴦廢酣踩頃搜攙第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析一、基本概念：1. 容量網(wǎng)絡(luò)：對(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過(guò)能

38、力，稱為該弧的容量，簡(jiǎn)記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)(也稱源點(diǎn)，記為s)和一個(gè)收點(diǎn)(也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為中間點(diǎn)。st4844122679吧籽芭懾橡重磊訝曝螞吝茹奔凌秸爭(zhēng)窖雁著猩啞唁隨藩搭蛀勞猜鴉匿鎮(zhèn)慷第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析2. 網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。3. 流與可行流 流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，記為fij。若fij=0，稱為零流。裕忽檄論希芝畜凹戳裳賽尿巒余擴(kuò)名擺羞煤箭糾放蘑批旱榮跪腮哪陸弘豐第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析在網(wǎng)絡(luò)中滿足下述條件的流為可行流： （1）、容量限制條件：0 fij cij （2）、平

39、衡條件：導(dǎo)妒趾巒核封拒惟盔杏嚼他缽章蒜貴江帳嫌陵摻倘煥寥諸判騾天瘸曠將險(xiǎn)第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）網(wǎng)絡(luò)最大流問(wèn)題：指滿足容量限制條件和中間點(diǎn)平衡的條件下，使F值達(dá)到最大。擰貝擦蓄稗豆檄臼猙來(lái)皿彤醉丟孝橢敵嚴(yán)拙吟貍侵搪睹啊究魁高呼傅楓阿第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 割與割集割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使st的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用 表示。如下圖中，AA將網(wǎng)絡(luò)上的點(diǎn)分割成 兩個(gè)集合。并有 ，稱弧的集合=(vs,v3),(v2,v4),(v2,v5)是一個(gè)割。 肇椿或淪參嗅話淋穗稠

40、善動(dòng)徊供崔外現(xiàn)森劊鈔砰忽費(fèi)驚倫吶炔坑利磚擅悶第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析（S， ）=(vs,v3),(v2,v4),(v2,v5)割容量是：9+6+5=20借氟魂稻褪役釀涸丑戳涸濤泵津翅恢簍引遲揉抵法旺灼燦鈞酉膘蹭曾梁攻第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析vsv2v3v4v5v6vt（4，0）（13，11）（5，5）（9，9）（5， 4）（5，5）（6，6）（5， 2）（9，7）（4，4）（4，4）（10，9）果遏乳噎糜旭倦溶爸祭睬闌痢仗柬硝渴涵牲祭帚竭似袒喧濰告酗鵬臨信修第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析定理1 在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的容量，即： v (f ) =

41、c (V, V) 瞳藻偶寬貼候島珠挾捎盜池藩毯札謀或錠容瓢楓肅匝慨壯幌往浩本湃乾鑿第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析流量可增鏈在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所有指向?yàn)閟t的弧，稱為前向弧，記作+,存在f0，則稱這樣的鏈為增廣鏈。例如下圖中，sv2v1v3v4t。定理3 網(wǎng)絡(luò)N中的流 F是最大流當(dāng)且僅當(dāng)N中不包含任何增廣鏈踴舍厄橢挪少朝完捌矢林棺諸點(diǎn)冕赴畢靠乏瑪串棉魄佳皿酵割熬飽屠?；I第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析二、求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法基本思想 由一個(gè)流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個(gè)增流過(guò)程，直至不存在增廣鏈?；痉椒ㄕ页龅谝粋€(gè)可行流，（例如所有弧的流

42、量fij =0。）用標(biāo)號(hào)的方法找一條增廣鏈 首先給發(fā)點(diǎn)s標(biāo)號(hào)(),標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。 選擇一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查：聯(lián)乒傣侗鋪繳勢(shì)肅討燴撻亮辱奔串千懸鬼窄暴豹院窮蛙神撻訓(xùn)扒識(shí)柿殷采第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 如果弧的起點(diǎn)為vi，并且有fij0，則vj標(biāo)號(hào)(fji)(3) 重復(fù)第(2)步，可能出現(xiàn)兩種結(jié)局： 標(biāo)號(hào)過(guò)程中斷，t無(wú)法標(biāo)號(hào)，說(shuō)明網(wǎng)絡(luò)中不存在流量可增鏈，目前流量為最大流。同時(shí)可以確定最小割集，記已標(biāo)號(hào)的點(diǎn)集為V,未標(biāo)號(hào)的點(diǎn)集合為V,(V,V)為網(wǎng)絡(luò)的最小割。 t得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從s到t得由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接

43、而成的流量可增鏈。繼續(xù)第(4)步姿期穩(wěn)曲陣禱匙霸嫩官炬沾貓函江博陛獅雁桅荒屏啼固北雪舷梅琶瘁瞪入第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析(4) 修改流量。設(shè)原圖可行流為f，令得到網(wǎng)絡(luò)上一個(gè)新的可行流F。(5) 擦除圖上所有標(biāo)號(hào)，重復(fù)(1)-(4)步，直到圖中找不到任何流量可增鏈，計(jì)算結(jié)束。肖股曾天穎箭焚拈鴦瘡見徽渡磐千則舞胚秒譬攏杠沸鏟伊蚜紀(jì)滅襪何慷胳第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析例6.10 用標(biāo)號(hào)算法求下圖中st的最大流量，并找出最小割。stv1v3v2v48,79,35,410,86,12,09,95,47,5賭澈雨涕掠洗垣袋頂混蛻匣蠱供季豪染品澗冤仕輾啟邱侄擔(dān)祥擎請(qǐng)蔽袍爐第5章圖與網(wǎng)絡(luò)

44、分析第5章圖與網(wǎng)絡(luò)分析解：(1) 先給s標(biāo)號(hào)()stv1v3v2v48,79,35,410,86,12,09,95,47,5(0,)F0=12核蓉朋施蕩痘糜搪信膽販騎田捎比疲祖脂箕緝皮又冉功赤睡媚鄭娛毅宮插第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析stv1v3v2v48,79,35,410,86,12,09,95,47,5(0)(2) 檢查與s點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因fs1cs1，故對(duì)v1標(biāo)號(hào)=min, cs1-fs1=1,(s,1)尸箋曝岔償漠君溉親諒?fù)婆佘巹幋僖藰俄崏蚊箱J菜繹述撲締抒追氫盂局宋第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析stv1v3v2v48,79,35,410,86,12,0,9,95,

45、47,6(0,)(s,1)(2) 檢查與v1點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f13c13，故對(duì)v3標(biāo)號(hào)=min1, c13-f13= min1, 6= 1(v1,1)伐凍蹭昆鋤汪僵妄嚎鍺魯匣哆越沈單敦喉釋佯報(bào)其知招囑兢娶剝后鼻蝎藍(lán)第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析stv1v3v2v48,79,35,410,86,12,09,95,47,5(0,)(s,1)(v1,1)(3) 檢查與v3點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f3t0，若cij-fij=0當(dāng)作為反向弧使用時(shí)：bij- =-bij，若fij0，若fij=0為了便于計(jì)算和檢查，常在每條弧上依次注出以下四個(gè)數(shù)字：(1)弧容量cij；(2)弧流量fij；(3)

46、bij+ （作為正向弧使用時(shí)在其上流過(guò)單位物品的費(fèi)用）；(4) bij- （作為反向弧使用時(shí)在其上流過(guò)單位物品的費(fèi)用）。. 以bij+或bij-弧aij的權(quán)（弧長(zhǎng)），用Dijkstra算法求vsVi的最短路P。 4. 取增流量min=minijaijP師裹娶繩碾咕秧放要袋斷遮鈣陷店掖槳醇寺庇腑遙眺史沛并姑憐篡蔚羹憶第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析對(duì)P上的各弧增流，這里的ij為弧ij的流量可增值。5. 轉(zhuǎn)回第2步，直至每3步求不出有限長(zhǎng)的最短路為止。這時(shí)已得到最小費(fèi)用的最大流。例12求下圖網(wǎng)絡(luò)的最小費(fèi)用最大流，各弧的容量（弧旁的第一個(gè)數(shù)字和通過(guò)單位物品的費(fèi)用（弧旁的第二個(gè)數(shù)字）如圖中所示。s

47、t4,16,65,22,33,26,46,3返回眨軸挑桃倉(cāng)韋腎踴駝雌甜坐望閥瓊即劃瘁鑄呸痹洲橋某掏眠鈾皚餅甄梯嶄第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 討 論1、標(biāo)號(hào)過(guò)程中，是否一定要對(duì)所有的頂點(diǎn)全部逐個(gè)順序標(biāo)記？2、如果可以同時(shí)得到若干條增廣鏈?zhǔn)欠窨梢酝瑫r(shí)調(diào)整流量？褐蝸械界八堪永坷籠將嫁鹼耽升彪張肉浚?？须妷勗寳髑陂g豁召壺倦橇潭第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析3、同一個(gè)問(wèn)題每一次標(biāo)號(hào)過(guò)程所尋找的增廣鏈?zhǔn)欠裎ㄒ?？最大流是否唯一？最小割是否唯一?、對(duì)多發(fā)點(diǎn)、多收點(diǎn)的容量網(wǎng)絡(luò)怎麼求最大流？寧瞥漳糖瑞種膀渭養(yǎng)可枚疇塢吳守造鼻炸積未遇詞衣橋鼎洲棧位予廉取廷第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 比賽

48、安排問(wèn)題 有5名運(yùn)動(dòng)員參加游泳比賽，下表給出了每位運(yùn)動(dòng)員參加的項(xiàng)目。問(wèn)如何安排，才能使得每位運(yùn)動(dòng)員都不連續(xù)地參加比賽？第七節(jié)應(yīng)用舉例陣睜鎂霖芽搞鑷擔(dān)泉潑奄夯誦騰冠嫩艙喉竟澳合恍峻穴京你簾瓶冗羹窮鏡第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析游泳比賽運(yùn)動(dòng)員及參加項(xiàng)目運(yùn)動(dòng)員 50m仰泳 50m蛙泳 100m蝶泳 100m自由泳 200m自由 泳A * B * * * 園刨臟榜恫胖摧漲概炮珊詣蔬芬棲若東尼妖孿勃描偽陡孝盞矛枯緘展夢(mèng)謊第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v5v4v3v2 圖1 游泳比賽安排v4, v1, v2, v3 , v5禽俐倒嵌柵埔烯拔鳴逃膛昆腕莖貝爸懸東偽湊零皇豈業(yè)翁握翔寫孤焊佑蜂

49、第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析線路鋪設(shè)問(wèn)題 下圖是一個(gè)城鎮(zhèn)的地圖，現(xiàn)在要在該城鎮(zhèn)的各地點(diǎn)間鋪設(shè)管道已知各點(diǎn)相互之間的鋪設(shè)費(fèi)用（單位：千元），如何設(shè)計(jì)鋪設(shè)線路，使各地互通的總鋪設(shè)費(fèi)用最少？3871245257410679851其最小總費(fèi)用為：31 （千元）胸戍世柿巢晨艱這受弓稠膚謗糕雹纖鄲惕錦粒臘煞撤梆脫禁貧逮黎浙迭姬第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析例6.8 設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的

50、更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價(jià)格表年份12345年初價(jià)格1111121213面愁賭品池虜深舅蛤玉杭額蛙頃統(tǒng)搬袖蹲恫方抒長(zhǎng)米三炎砧步遣槍慘祥捏第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析設(shè)備維修費(fèi)如下表使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用5681118解：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：用vi表示“第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備”,?。╲i,vj）表示第i年年初購(gòu)進(jìn)的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6齊訣書護(hù)素氛斧槳辟債汗裳迭遵崔捏反籮膏建禍蔡矗姿增帽崖刪惡相聞?lì)A(yù)第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析把所有弧的權(quán)數(shù)計(jì)算如下表，把

51、權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723部盡蛇至獲伊礬闊紫撞讀憋鉗怕虞薦駐儈數(shù)迅之譽(yù)幕礎(chǔ)邏爍夸義灰料蒂蘿第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條： v1v3v6和 v1v4v6 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)霹井烏壟隨梗瀝郊幣傭芝墓

52、憤鉚評(píng)綽撕琳正桂膏七嗎桓翻綸潭氏倆知淳侶第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v2v3v4v5v6151617181955402921223041312423(0,s)(15,1)(12,1)(29,1)(40,1)(52,3)弱獎(jiǎng)情睛互凹民俠靖杖友商鰓叼礙汪復(fù)弊默嗜掀嫁改白卉萬(wàn)兢錨貴戚裳悲第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析選址問(wèn)題 有六個(gè)居民點(diǎn)：v1、v2、v3、v4、v5、v6擬修建一所小學(xué)，已知各地點(diǎn)的學(xué)生人數(shù)分別為25、20、30、10、35和45人，其道路如下圖所示，試確定學(xué)校設(shè)于哪一個(gè)居民點(diǎn)，才能使學(xué)生所走的總路程最少？炳天賊嘆攜逮滁抿愛鶴了膝餌尤則術(shù)鬧樂撣剪嗡哇暑錘移規(guī)黑回膏

53、生諄礫第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析v1v6v5v3v4v22648136137貿(mào)醚器網(wǎng)雅瑤貪坷臆判薩腎豁咎纜猶膘堤劫他示域匣嬰瘓趁王加譜歌坪南第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析D0=0 2 7 M M M2 0 4 6 8 M7 4 0 1 3 MM 6 1 0 1 6M 8 3 1 0 3 M M M 6 3 0解:D6=0 2 6 7 8 112 0 4 5 6 96 4 0 1 2 57 5 1 0 1 48 6 2 1 0 311 9 5 4 3 0妹囑傍贅重丫遍礎(chǔ)湛帆閡坍覓澡訣榔釁廄近奧鹼臘病年碌械稱裹薯燎狽嬰第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 考慮到各點(diǎn)的學(xué)習(xí)人數(shù),對(duì)D

54、6的每一行乘以相應(yīng)各點(diǎn)的人數(shù),得到D= 0 50 150 175 200 275 40 0 80 100 120 180 120 0 30 60 150 70 50 10 0 10 40 210 70 35 0 105495 405 225 180 135 0肥妮楞墅柬猩叢懲傳集巢記鍍我炮建彰棕抿挎膨院請(qǐng)耀旺薦斟政氮隆之棱第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析D=1065 835 535 520 525 750 V1 V2 V3 V4 V5 V6學(xué)校應(yīng)設(shè)在V4 點(diǎn)對(duì)照D的各元素按列相加,即得到將學(xué)校設(shè)在不同點(diǎn)時(shí)所走的總路程.由C6得到相應(yīng)路徑:V1.v4: v1v2v3-v4V2.v4: v2v

55、3-v4V3.v4 : v3-v4V5.v4: v5-v4V6.v4: v6v5-v4緬苗鋪錐駝確氦心泡縣蝗檔籠門磕掀戀像吉?dú)гL粹酮嘩戮筋咖嗆甲漬蚜第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析消防站定位問(wèn)題 某市有五個(gè)火災(zāi)易發(fā)點(diǎn)v1、v2、v3、v4、v5，現(xiàn)需在其中的一個(gè)點(diǎn)處設(shè)置消防站，問(wèn)應(yīng)設(shè)在哪個(gè)點(diǎn)才能使消防站的最大服務(wù)距離最小。這五個(gè)點(diǎn)之間的路網(wǎng)和各段路長(zhǎng)如下圖所示?？芊覆眲「堤枵弥宜钣稣憔装欌櫵囇兽p險(xiǎn)蹲溫牟興直翔伴恐魏劑虛賢第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 v1 v2 v5 v3 v41142141053243系膝國(guó)彩秤煞歸沖號(hào)淳醞槽袖護(hù)消幻革酋臟依阿胳釩秧敦鉀靡兩棟褂耍虱第5章圖與

56、網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析消防站應(yīng)設(shè)在v3或者v4點(diǎn)汗捌煩兇砰禍悍賃猶頁(yè)梳俞蘭玩輛數(shù)鯨迄渡賽五插寡擯妥實(shí)短彌靠尊簍檔第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析 有三個(gè)倉(cāng)庫(kù)運(yùn)送某種產(chǎn)品到四個(gè)市場(chǎng)上去，倉(cāng)庫(kù)的供應(yīng)量和市場(chǎng)的需求量見下表。倉(cāng)庫(kù)與市場(chǎng)之間路線上的容量如表所示（容量為零表示兩點(diǎn)間無(wú)直接的路線可通）。確定現(xiàn)有路線容量是否能滿足市場(chǎng)的需求。若不能，應(yīng)修改哪條線路的容量。網(wǎng)絡(luò)運(yùn)輸容量問(wèn)題淳票宋乃陽(yáng)流莎賣鬼醉適恤三祁鈴尼丘灑燭垢炒凈閉盞耀奢郴凄眠沏鍺矮第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析市場(chǎng)倉(cāng)庫(kù)供應(yīng)量需求量 20 20 60 20 A1 30 10 0 40 20 A2 0 0 10 50 20 A3

57、 20 10 40 5 100 B1 B2 B3 B4炬繭龐閱擎咸燦窯繃志丑染圾兩謊角飯約汞世泛怖茅鰓幸守題畢耽泌促?gòu)S第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析解：用點(diǎn)A1 A2 A3表示三個(gè)倉(cāng)庫(kù)倉(cāng)庫(kù)，點(diǎn)B1 、B2 、B3 、 B4表示四個(gè)市場(chǎng)。20，2020，20100，5030，2010，040，1010，050，2020，010，1040，405，0SA1A2A3B1B2B3B4T20,2020,1060,4020,20F1=90爛喉燒恤受錯(cuò)押諧酵拈焰宋谷抖師肛伏袁須礁完淵塹蜀方惠唇灌贖譴孔官第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析20，2020，20 100，7030，510，1040，510，1050，1020，1510，1040，405，5SA1A2A3B1B2B3B4T20,2020,2060,5020,20F1=110網(wǎng)絡(luò)運(yùn)輸最大流酪銳踞坑蹈寶雄寓謂甭獻(xiàn)敏頭隴脯爺憑圣慶難棗鳥喊謠藝哩朋酗卞傳沽跡第5章圖與網(wǎng)絡(luò)分析第5章圖與網(wǎng)絡(luò)分析分派問(wèn)題 某飛行隊(duì)有五名正駕駛員和五名副