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

圖與網(wǎng)絡(luò)分析第一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二近代圖論的歷史可追溯到18世紀(jì)的七橋問(wèn)題—穿過(guò)K?nigsberg城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。第一節(jié)圖的基本概念與模型K?nigsberg橋?qū)?yīng)的圖第二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例1、有甲、乙、丙、丁、戊五個(gè)球隊(duì)，它們之間比賽的情況也可以用圖表示出來(lái)。V1V2V3V4V5e5e4e1e2e3e6e7一、圖基本概念第三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例2某單位儲(chǔ)存八種化學(xué)藥品，其中某些藥品是不能存放在同一個(gè)庫(kù)房里的。為了反映這個(gè)情況可以用點(diǎn)V1,V2,……V8分別代表這八種藥品，若藥品Vi和藥品Vj是不能存放在同一個(gè)庫(kù)房的，則在Vi和Vj之間連一條線。?V1V2

??V3?V4?V5

?·V8?V7?V6第四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二圖的表示方法：

一般地，當(dāng)用圖論研究一個(gè)實(shí)際問(wèn)題時(shí)，常以頂點(diǎn)（Vertex）表示要研究的對(duì)象，以它們之間的連線，表示某種關(guān)系，這種連線稱(chēng)為邊（Edge），目的是為了解決某個(gè)極值問(wèn)題。圖中的點(diǎn)用v表示，邊用e表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：e1=[v1,v1];e2=[v1,v2];第五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二運(yùn)籌學(xué)中研究的圖具有下列特征:

強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀；每條邊上賦有一個(gè)權(quán)；建立網(wǎng)絡(luò)模型，求最大值或最小值。第六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二下圖可以提出很多極值問(wèn)題142653876631627433716第七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v3e7e4e8e5e6e1e2e3v1v2v4v5端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱(chēng)vi和vj是邊e的端點(diǎn)，反之稱(chēng)邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱(chēng)點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱(chēng)邊ei和ej相鄰。二、關(guān)于圖的另外一些名稱(chēng)和術(shù)語(yǔ)：第八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二環(huán),多重邊,簡(jiǎn)單圖如果邊e的兩個(gè)端點(diǎn)相重，稱(chēng)該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱(chēng)為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱(chēng)作簡(jiǎn)單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5第九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱(chēng)為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱(chēng)作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱(chēng)作偶點(diǎn)，次為1的點(diǎn)稱(chēng)為懸掛點(diǎn)，次為0的點(diǎn)稱(chēng)作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:一個(gè)圖的次等于各點(diǎn)的次之和。第十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二定理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ù)。第十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二鏈，圈，連通圖圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意vi,t-1和vit均相鄰稱(chēng)為鏈。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起點(diǎn)與終點(diǎn)重合的鏈稱(chēng)作圈。如果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱(chēng)這樣的圖為連通圖，否則稱(chēng)圖不連通。第十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二子圖，部分圖(支撐子圖)圖G1={V1、E1}和圖G2={V2，E2}如果有稱(chēng)G1是G2的一個(gè)子圖。若有，則稱(chēng)G1是G2的一個(gè)部分圖(支撐子圖)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖）第十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二網(wǎng)絡(luò)（賦權(quán)圖）賦權(quán)圖）:權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量)等等。無(wú)向網(wǎng)絡(luò):端點(diǎn)無(wú)序的賦權(quán)圖稱(chēng)為.有向網(wǎng)絡(luò):端點(diǎn)有序的賦權(quán)圖稱(chēng)為。①②③④⑤⑥910201571419256第十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二圖的矩陣描述：鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1.鄰接矩陣 對(duì)于圖G=（V，E），|V|=n，|E|=m，有nn階方矩陣A=(aij)nn，其中第十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二圖的基本概念與模型v5v1v2v3v4v64332256437例6.2下圖所表示的圖可以構(gòu)造鄰接矩陣A如下第十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二對(duì)于賦權(quán)圖G=(V,E),其中邊有權(quán),構(gòu)造矩陣B=(bij)nn

其中：2.權(quán)矩陣第十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v5v1v2v3v4v64332256437例6.4下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:第十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二G=(V,E)矩陣表示A

鄰接矩陣B

關(guān)聯(lián)矩陣邊e=[u,v]

關(guān)聯(lián)邊

端點(diǎn)

重合環(huán)多重邊

平行邊簡(jiǎn)單圖不含多重圖含點(diǎn)的次

01奇數(shù)偶數(shù)子圖子圖生成子圖孤立點(diǎn)懸掛點(diǎn)奇點(diǎn)偶點(diǎn)頂點(diǎn)數(shù)p邊數(shù)q點(diǎn)邊關(guān)系各種鏈的概念第十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二歐拉圖與中國(guó)郵路問(wèn)題歐拉圖哥尼斯堡七橋問(wèn)題哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，Pregei河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒(méi)有辦法從某處（如A）出發(fā)，經(jīng)過(guò)各橋一次且僅一次最后回到原地呢？第二十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二Cab圖4-10ad哥尼斯堡七橋問(wèn)題第二十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二acbd(b)第二十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二定理2連通無(wú)向圖G為歐拉鏈的充要條件是它恰含兩個(gè)奇次頂點(diǎn)。定義1.在連通無(wú)向圖G中,若存在經(jīng)過(guò)每條邊恰好一次的一個(gè)圈或一條鏈,就稱(chēng)此圈或鏈為歐拉圈或歐拉鏈。若圖G含一條歐拉圈，則稱(chēng)為歐拉圖。定理1連通無(wú)向圖G為歐拉圖的充要條件是它的全部頂點(diǎn)都是偶次頂點(diǎn)。（G中無(wú)奇次頂點(diǎn)）第二十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二歐拉鏈歐拉圖第二十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二中國(guó)郵路問(wèn)題第二十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二定理3使圖G成為總權(quán)最小的歐拉圖的充要條件是：（1）在有奇次頂點(diǎn)的圖G中，通過(guò)加重復(fù)邊的方法使圖不再包含奇次頂點(diǎn)，但原圖的每條邊最多只能加一條重復(fù)邊。（2）在圖G的每個(gè)回路上，重復(fù)邊之總權(quán)不超過(guò)該回路非重復(fù)邊之總權(quán)。（或回路總長(zhǎng)的一半）

第二十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例1試為圖4-13（a)構(gòu)成總權(quán)最小的歐拉圖。圖中線旁的數(shù)字為相應(yīng)邊的權(quán)。124332124（a)圖4-13第二十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例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第二十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二413333333322圖4-14（b）22第二十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第二節(jié)樹(shù)樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。例6.2乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動(dòng)員第三十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例6.3某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。廠長(zhǎng)人事科財(cái)務(wù)科總工程師生產(chǎn)副廠長(zhǎng)經(jīng)營(yíng)副廠長(zhǎng)開(kāi)發(fā)科技術(shù)科生產(chǎn)科設(shè)備科供應(yīng)科銷(xiāo)售科檢驗(yàn)科動(dòng)力科第三十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二樹(shù)：無(wú)圈的連通圖即為樹(shù)性質(zhì)1：任何樹(shù)中必存在次為1的點(diǎn)。性質(zhì)2：n個(gè)頂點(diǎn)的樹(shù)必有n-1條邊。性質(zhì)3：樹(shù)中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)4：樹(shù)連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹(shù)無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。v1v2v3v4v5v6第三十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二圖的最小部分樹(shù)(支撐樹(shù))如果G2是G1的部分圖，又是樹(shù)圖，則稱(chēng)G2是G1的部分樹(shù)（或支撐樹(shù)）。樹(shù)圖的各條邊稱(chēng)為樹(shù)枝，一般圖G1含有多個(gè)部分樹(shù)，其中樹(shù)枝總長(zhǎng)最小的部分樹(shù)，稱(chēng)為該圖的最小部分樹(shù)（或最小支撐樹(shù)）。v1v2v3v4v5v1v2v3v4v5G1G2第三十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

例如，圖4-18（a）是一個(gè)有四個(gè)頂點(diǎn)（n=4）的連通圖，它共有nn-2=42=16個(gè)生成樹(shù)。V1V2V3V4圖4-18（a）第三十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第三十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第三十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二abcfedhgbfed第三十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二abcfedhgbfdg第三十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二bcedabcfedhg第三十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二abchabcfedhg第四十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二afdgabcfedhg第四十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二賦權(quán)圖中求最小樹(shù)的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)＝n-1=5第四十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v2v3v4v5v643521得到最小樹(shù)：MinC(T)=15第四十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二避圈法:

去掉G中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。加邊的原則為：從最短邊開(kāi)始添加，加邊的過(guò)程中不能形成圈，直到點(diǎn)點(diǎn)連通(即:n-1條邊)。5v1v2v3v4v5v6843752618第四十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15第四十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v7v4v3v2v5v620159162532817412336練習(xí)：應(yīng)用破圈法求最小樹(shù)第四十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57第四十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二課堂練習(xí)：3749346321MinC(T)=12MinC(T)=15254173314475答案：第四十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二34122323242MinC(T)=12213638534567454321MinC(T)=18第四十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

某一點(diǎn)到另一點(diǎn)的最短路的Dijkstra法所有點(diǎn)對(duì)間的最短路

返回第三節(jié)最短路問(wèn)題第五十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二 就是從給定的網(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)題。因此這類(lèi)問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。第五十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二里特城（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)的主要因素，所以消防隊(duì)隊(duì)長(zhǎng)希望事先能夠確定從消防站到每一個(gè)農(nóng)場(chǎng)社區(qū)的最短路。例子：里特城的消防隊(duì)問(wèn)題第五十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第五十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二最短路：O—A—B—E—F—T19英里第五十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二一、求最短路的Dijkstra算法

1、算法的基本思想第五十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二2.有向圖的狄克斯屈拉(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)步。第五十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二①②③④⑤⑥⑦610123214675811165圖5－19【例5-1】圖5－1中的權(quán)cij表示vi到vj的距離（費(fèi)用、時(shí)間），從v1修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離最短，建立該問(wèn)題的網(wǎng)絡(luò)數(shù)學(xué)模型。第五十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二【解】設(shè)xij為選擇弧(i，j)的狀態(tài)變量，選擇弧(i，j)時(shí)xij＝1，不選擇弧(i，j)時(shí)xij＝0，得到最短路問(wèn)題的網(wǎng)絡(luò)模型：第五十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二②③④⑤⑥⑦610123214675811165圖5－1961012920p(9,v2)18P（6,V1）①16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)【例5-1】用Dijkstra算法求圖5－1所示v1到v7的最短路及最短路長(zhǎng)v1到v7的最短路為：p17=｛v1,v2,v3,v5,v7｝，最短路長(zhǎng)為L(zhǎng)17=2914P（0,V1）第五十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二②③④⑤⑥⑦610123214675811165圖5－1961012920p(9,v2)18P（6,V1）①16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)v1到v7的最短路為：p17=｛v1,v2,v3,v5,v7｝，最短路長(zhǎng)為L(zhǎng)17=2914P（0,V1）第六十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二從上例知，只要某點(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。第六十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二【例6-5】求圖6-10所示v1到各點(diǎn)的最短路及最短距離①②③④⑤⑥⑦⑧452617839326121618P(0,v1)452P(2,v1)310P(3,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ú)向圖最短路的求法第六十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二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í)，所謂相鄰必須是箭頭指向的節(jié)點(diǎn)；若第n1

次迭代后仍有節(jié)點(diǎn)的標(biāo)號(hào)為，則表明vs

到該節(jié)點(diǎn)無(wú)有向路徑；vs到所有點(diǎn)的最短路也是一棵生成樹(shù)，但不是最小生成樹(shù)這個(gè)算法只設(shè)用于全部權(quán)為非負(fù)情況,如果某邊上權(quán)為負(fù)的,算法失效;當(dāng)vi與vj兩點(diǎn)之間至少有兩條邊相關(guān)聯(lián)時(shí)，留下一條最短邊，去掉其它關(guān)聯(lián)邊。第六十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二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）第六十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二142653876631627433716第六十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二二、所有點(diǎn)對(duì)間的最短路Floyd算法1、寫(xiě)出圖的權(quán)矩陣

第六十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二步驟：１、輸入權(quán)矩陣Ｄ（０）＝Ｄ；２、對(duì)n個(gè)頂點(diǎn)的圖G,該方法迭代n步結(jié)束，第k次迭代的矩陣Dk的元素dij(k)按下式選取

dij(k)=min{dij(k-1),[dik(k-1）+dkj(k-1）]}其中，i,j=1,2,3,………,n。但當(dāng)i=k或j=k時(shí)，dij(k)=dij(k-1).。３、Ｄ（ｎ）中的元素就是ｖｉ到ｖｊ的最短路長(zhǎng)。第六十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v3v4v2v5512310655228442例求下圖所示網(wǎng)絡(luò)圖各點(diǎn)對(duì)間的最短路和最短路長(zhǎng)。第六十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第六十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第七十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第七十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第七十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二23147432910例求下圖所示網(wǎng)絡(luò)圖各點(diǎn)對(duì)間的最短路和最短路長(zhǎng)。第七十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二課堂練習(xí)：1.用Dijkstra算法求下圖從v1到v6的最短距離及路線。v3v54v1v2v4v635222421v1到v6的最短路為：第七十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二2.求從v1到v8的最短路徑237184566134105275934682第七十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路徑為v1→v4→v7→v5→v8，最短距離為10第七十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二最短路問(wèn)題的應(yīng)用：例6.7電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。v1（甲地）1517624431065v2v7(乙地)v3v4v5v6第七十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題。第七十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第四節(jié)網(wǎng)絡(luò)最大流如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷(xiāo)售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。第七十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二實(shí)例：ＢＭＺ公司的最大流問(wèn)題

ＢＭＺ公司是歐洲一家生產(chǎn)豪華汽車(chē)的制造商。雖然它生產(chǎn)的汽車(chē)在所有發(fā)達(dá)國(guó)家的銷(xiāo)量都不錯(cuò)，但是對(duì)于這家公司來(lái)說(shuō)，出口到美國(guó)顯得尤其重要。ＢＭＺ公司因?yàn)樘峁﹥?yōu)質(zhì)的服務(wù)而獲得很好的聲譽(yù)，保持這個(gè)聲譽(yù)一個(gè)很重要的秘訣是它有著充裕的汽車(chē)配件供應(yīng)，從而能夠隨時(shí)供貨給公司眾多的經(jīng)銷(xiāo)商和授權(quán)維修店。這些供應(yīng)件主要存放在公司的配送中心里，這樣一有需求就可以立即送貨?？栃枰獌?yōu)先考慮的是改進(jìn)這些配送中心的不足之處。

背景第八十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

該公司在美國(guó)有幾個(gè)配送中心。但是，離洛杉礬中心最近的一個(gè)配送中心卻坐落在離洛杉礬1000多英里的西雅圖。由于ＢＭＺ的汽車(chē)在加利福尼亞越來(lái)越受歡迎，所以保證洛杉礬中心良好的供應(yīng)就顯得尤為重要了。因此，現(xiàn)在那里的供應(yīng)不斷減少的現(xiàn)狀成為了公司高層管理真正關(guān)心的問(wèn)題——正如現(xiàn)在卡爾深切領(lǐng)會(huì)到了一樣。大部分的汽車(chē)配件以及新車(chē)是在該公司坐落于德國(guó)斯圖加特的總廠和新車(chē)一起生產(chǎn)的。也就是這家工廠向洛杉礬中心供應(yīng)汽車(chē)配件。由于其中的一些配件體積很大，某些配件的需求量很多，這就使得供應(yīng)的總量非常龐大——每月有超過(guò)300，000立方英尺的配件需要運(yùn)到?，F(xiàn)在，下個(gè)月需要多得多的數(shù)量以補(bǔ)充正在減少的庫(kù)存。第八十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

卡爾需要盡快做出一個(gè)方案，使得下個(gè)月從總廠運(yùn)送到洛杉礬配送中心的供應(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)題第八十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第八十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二LASTLIROBONONY806070405030507040BMZ的網(wǎng)絡(luò)模型，圖中的數(shù)字代表該弧的容量第八十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

一基本概念二求最大流的標(biāo)號(hào)法返回第八十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二如圖4-23是聯(lián)接某產(chǎn)品產(chǎn)地v1和銷(xiāo)售地v6點(diǎn)

的交通網(wǎng)。s①②③④t4844122679第八十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二s①②③④t4，38,44,04,21,12,22,26,07,49,3第八十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二一、基本概念：1.容量網(wǎng)絡(luò)：對(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過(guò)能力，稱(chēng)為該弧的容量，簡(jiǎn)記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)(也稱(chēng)源點(diǎn)，記為s)和一個(gè)收點(diǎn)(也稱(chēng)匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱(chēng)為中間點(diǎn)。s①②③④t4844122679第八十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二2.網(wǎng)絡(luò)的最大流

是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。3.流與可行流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，記為fij。若fij=0，稱(chēng)為零流。第八十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二在網(wǎng)絡(luò)中滿(mǎn)足下述條件的流為可行流：（1）、容量限制條件：0fijcij

（2）、平衡條件：第九十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）網(wǎng)絡(luò)最大流問(wèn)題： 指滿(mǎn)足容量限制條件和中間點(diǎn)平衡的條件下，使F值達(dá)到最大。第九十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二割與割集割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開(kāi)，并使s→t的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用表示。如下圖中，AA′將網(wǎng)絡(luò)上的點(diǎn)分割成兩個(gè)集合。并有，稱(chēng)弧的集合={(vs,v3),(v2,v4),(v2,v5)}是一個(gè)割。第九十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二（S，）={(vs,v3),(v2,v4),(v2,v5)}割容量是：9+6+5=20第九十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二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）第九十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二定理1在網(wǎng)絡(luò)中s→t的最大流量等于它的最小割集的容量，即：v＊(f)=c＊(V,V′)第九十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二流量可增鏈 在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所有指向?yàn)閟→t的弧，稱(chēng)為前向弧，記作μ+,存在f<c；所有指向?yàn)閠→s的弧，稱(chēng)為后向弧，記做μ－，若f>0，則稱(chēng)這樣的鏈為增廣鏈。例如下圖中，s→v2→v1→v3→v4→t。定理3網(wǎng)絡(luò)N中的流F是最大流當(dāng)且僅當(dāng)N中不包含任何增廣鏈第九十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二二、求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法[基本思想]

由一個(gè)流開(kāi)始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個(gè)增流過(guò)程，直至不存在增廣鏈。[基本方法]找出第一個(gè)可行流，（例如所有弧的流量fij=0。）用標(biāo)號(hào)的方法找一條增廣鏈?zhǔn)紫冉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)檢查：第九十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二如果弧的起點(diǎn)為vi，并且有fij<Cij，則給vj標(biāo)號(hào)為(Cij－fij)如果弧的方向指向vi，并且有fji>0，則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)的弧連接而成的流量可增鏈。繼續(xù)第(4)步第九十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二(4)修改流量。設(shè)原圖可行流為f，令得到網(wǎng)絡(luò)上一個(gè)新的可行流F。(5)擦除圖上所有標(biāo)號(hào)，重復(fù)(1)-(4)步，直到圖中找不到任何流量可增鏈，計(jì)算結(jié)束。第九十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例6.10用標(biāo)號(hào)算法求下圖中s→t的最大流量，并找出最小割。●stv1v3v2v48,79,35,410,86,12,09,95,47,5第一百頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二解：(1)先給s標(biāo)號(hào)(∞)●stv1v3v2v48,79,35,410,86,12,09,95,47,5(0,∞)F0=12第一百零一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二●stv1v3v2v48,79,35,410,86,12,09,95,47,5(0∞)(2)檢查與s點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因fs1<cs1，故對(duì)v1標(biāo)號(hào)=min{∞,cs1-fs1}=1,(s,1)第一百零二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二●stv1v3v2v48,79,35,410,86,12,0,9,95,47,6(0,∞)(s,1)(2)檢查與v1點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f13<c13，故對(duì)v3標(biāo)號(hào)=min{1,c13-f13}=min{1,6}=1(v1,1)第一百零三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二●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)，因f3t<c3t，故對(duì)vt標(biāo)號(hào)=min{1,c3t-f3t}=min{1,1}=1(v3,1)找到一條增廣鏈s→v1→v3→t第一百零四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第一百零五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二●stv1v3v2v48,89,45,510,86,12,09,95,47,5F1=12+1=13(4)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。第一百零六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二(5)重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。●stv1v3v2v48,89,45,510,86,12,09,95,47,5(0，∞)(s,2)(-v2,2)(v1,2)(-v3,1)(v4,1)第一百零七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二(6)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。●stv1v3v2v48,89,55,510,96,02,09,95,37,6(0，∞)F2=13+1=14第一百零八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二●stv1v3v2v48,89,55,510,96,02,09,95,37,6(0，∞)(s,1)(-v2,1)(v1,1)Fmax=14(7)擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。第一百零九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例6.9求下圖s→t的最大流，并找出最小割stv1v2v3v4v54,33,210,43,21,14,33,25,34,22,27,68,3●F0=9第一百一十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二解:初始可行流：14存在增廣鏈:s→v2→v3→t流量可增值=2F1=9+2=11(2)s→v2→v5→v3→t流量可增值=1F1=11+1=12(3)s→v5→v3→t流量可增值=1F1=12+1=13(4)s→v1→v5→v4→t流量可增值=1F1=13+1=14第一百一十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二stv1v2v3v4v54,43,310,73,31,14,43,35,54,42,27,78,7●(0,∞)(s,3)無(wú)法標(biāo)號(hào)，不存在增廣鏈，此可行流已為最大流。最大流量為14。第一百一十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

第五節(jié)最小費(fèi)用流

無(wú)限配送公司有兩個(gè)工廠生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運(yùn)到兩個(gè)倉(cāng)庫(kù)里。下面是一些具體的信息。

工廠1生產(chǎn)80個(gè)單位。工廠2生產(chǎn)70個(gè)單位。倉(cāng)庫(kù)1需要60個(gè)單位。倉(cāng)庫(kù)2需要90個(gè)單位。（每個(gè)單位對(duì)應(yīng)貨車(chē)滿(mǎn)載時(shí)的產(chǎn)品數(shù)量。）

例子：無(wú)限配送公司的問(wèn)題第一百一十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二下圖給出了運(yùn)輸這些產(chǎn)品可利用的配送網(wǎng)絡(luò)。在圖中，F(xiàn)I和FZ代表兩個(gè)工廠，W1和W2代表兩個(gè)倉(cāng)庫(kù)，DC表示一個(gè)配送中心。箭頭表示可行的運(yùn)輸線路。特別地，工廠1和倉(cāng)庫(kù)1之間以及工廠2和倉(cāng)庫(kù)2之間各有一條鐵路運(yùn)輸軌道。（在鐵路上的運(yùn)輸量是沒(méi)有限制的。）除此以外，卡車(chē)司機(jī)總共可以從工廠運(yùn)輸50個(gè)單位到配送中心，然后可以從配送中心運(yùn)輸50個(gè)單位到倉(cāng)庫(kù)。（任何運(yùn)輸?shù)脚渌椭行牡漠a(chǎn)品必須隨后運(yùn)送到倉(cāng)庫(kù)里。）第一百一十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二第一百一十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二每條路線的單位運(yùn)輸成本如圖6．2中箭頭上方的數(shù)字所示第一百一十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

不同運(yùn)輸路線的運(yùn)輸成本是不一樣的。每條路線的單位運(yùn)輸成本如圖6．2中箭頭上方的數(shù)字所示。

管理者的目標(biāo)是確定一個(gè)運(yùn)輸方案（即每條路線運(yùn)送多少單位的產(chǎn)品），使運(yùn)輸成本的總和達(dá)到最小。第一百一十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二w2w1F1答案如下圖所示，每條路線中的運(yùn)輸數(shù)量都已經(jīng)在圓括號(hào)里標(biāo)出。成本，此解決方案的總運(yùn)輸成本是：（80）（70）＄700（-60）（-90）＄300＄200（50,50）＄400＄400＄900（50.,30）（50,50）（50，30）（∞，30）（∞，40）F1F2第一百一十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二總運(yùn)輸成本=３０（＄７００）＋５０（＄３００）＋５０（＄４００）＋５０（＄２００）＋５０（＄４00）＋２０（＄９００）＝＄１０４，０００第一百一十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二二、最小費(fèi)用最大流該方法的迭代步驟如下。１.任給一最小費(fèi)用可行流。由于bij≥0，故fij=0（vi,vj∈V,(vi,vj)∈A）必是一個(gè)最小費(fèi)用可行流，因而常從零流開(kāi)始迭代。２.給網(wǎng)絡(luò)的弧aij賦權(quán)；當(dāng)作為正向弧使用時(shí)：第一百二十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二bij+

=bij，若cij-fij>0∞，若cij-fij=0當(dāng)作為反向弧使用時(shí)：bij-=-bij，若fij>0∞，若fij=0為了便于計(jì)算和檢查，常在每條弧上依次注出以下四個(gè)數(shù)字：(1)弧容量cij；(2)弧流量fij；(3)bij+

（作為正向弧使用時(shí)在其上流過(guò)單位物品的費(fèi)用）；(4)bij-（作為反向弧使用時(shí)在其上流過(guò)單位物品的費(fèi)用）。３.以bij+或bij-弧aij的權(quán)（弧長(zhǎng)），用Dijkstra算法求vs→Vi的最短路P。

4.取增流量△min=min{△ij}aij∈P第一百二十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二對(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２３t4,16,65,22,33,26,46,3返回第一百二十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

討論1、標(biāo)號(hào)過(guò)程中，是否一定要對(duì)所有的頂點(diǎn)全部逐個(gè)順序標(biāo)記？2、如果可以同時(shí)得到若干條增廣鏈?zhǔn)欠窨梢酝瑫r(shí)調(diào)整流量？第一百二十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二3、同一個(gè)問(wèn)題每一次標(biāo)號(hào)過(guò)程所尋找的增廣鏈?zhǔn)欠裎ㄒ?？最大流是否唯一？最小割是否唯一?、對(duì)多發(fā)點(diǎn)、多收點(diǎn)的容量網(wǎng)絡(luò)怎麼求最大流？第一百二十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二比賽安排問(wèn)題有5名運(yùn)動(dòng)員參加游泳比賽，下表給出了每位運(yùn)動(dòng)員參加的項(xiàng)目。問(wèn)如何安排，才能使得每位運(yùn)動(dòng)員都不連續(xù)地參加比賽？第七節(jié)應(yīng)用舉例第一百二十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二游泳比賽運(yùn)動(dòng)員及參加項(xiàng)目運(yùn)動(dòng)員50m仰泳50m蛙泳100m蝶泳100m自由泳200m自由泳A

*

B**＊Ｃ＊＊Ｄ＊＊Ｅ＊

*

第一百二十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二●●●●●v1v5v4v3v2圖1游泳比賽安排{v4,v1,v2,v3,v5}第一百二十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二線路鋪設(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（千元）第一百二十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二例6.8設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買(mǎi)新的設(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)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價(jià)格表年份12345年初價(jià)格1111121213第一百二十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二設(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第一百三十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723第一百三十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二最終得到下圖，可知，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)第一百三十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v2v3v4v5v6151617181955402921223041312423(0,s)(15,1)(12,1)(29,1)(40,1)(52,3)第一百三十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二選址問(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é)生所走的總路程最少？第一百三十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v6v5v3v4v22648136137第一百三十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二D0=027MMM20468M74013MM61016M83103MMM630解:D6=02678112045696401257510148621031195430第一百三十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

考慮到各點(diǎn)的學(xué)習(xí)人數(shù),對(duì)D6的每一行乘以相應(yīng)各點(diǎn)的人數(shù),得到D=050150175200275400801001201801200306015070501001040210703501054954052251801350第一百三十七頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二D={1065835535520525750]V1V2V3V4V5V6學(xué)校應(yīng)設(shè)在V4點(diǎn)對(duì)照D的各元素按列相加,即得到將學(xué)校設(shè)在不同點(diǎn)時(shí)所走的總路程.由C6得到相應(yīng)路徑:V1…..v4:v1—v2—v3---v4V2…..v4:v2—v3---v4V3…..v4:v3---v4V5…..v4:v5---v4V6…..v4:v6—v5---v4第一百三十八頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二消防站定位問(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)如下圖所示。第一百三十九頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二v1v2v5v3v41142141053243第一百四十頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二消防站應(yīng)設(shè)在v3或者v4點(diǎn)第一百四十一頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二

有三個(gè)倉(cāng)庫(kù)運(yùn)送某種產(chǎn)品到四個(gè)市場(chǎng)上去，倉(cāng)庫(kù)的供應(yīng)量和市場(chǎng)的需求量見(jiàn)下表。倉(cāng)庫(kù)與市場(chǎng)之間路線上的容量如表所示（容量為零表示兩點(diǎn)間無(wú)直接的路線可通）。確定現(xiàn)有路線容量是否能滿(mǎn)足市場(chǎng)的需求。若不能，應(yīng)修改哪條線路的容量。網(wǎng)絡(luò)運(yùn)輸容量問(wèn)題第一百四十二頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二市場(chǎng)倉(cāng)庫(kù)供應(yīng)量需求量20206020A1301004020A200105020A32010405100B1B2B3B4第一百四十三頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二解：用點(diǎn)A1A2A3表示三個(gè)倉(cāng)庫(kù)倉(cāng)庫(kù)，點(diǎn)B1、B2、B3、B4表示四個(gè)市場(chǎng)?！瘛瘛瘛瘛瘛瘛瘛瘛?0，2020，20100，5030，2010，040，1010，050，2020，010，1040，405，0SA1A2A3B1B2B3B4T20,2020,1060,4020,20F1=90第一百四十四頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二●●●●●●●●●20，2020，20100，7030，510，1040，510，1050，1020，1510，1040，405，5SA1A2A3B1B2B3B4T20,2020,2060,5020,20F1=110網(wǎng)絡(luò)運(yùn)輸最大流第一百四十五頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二分派問(wèn)題某飛行隊(duì)有五名正駕駛員和五名副駕駛員。由于種種原因，某些正、副駕駛員不能同機(jī)飛行，某些則可以，如下表所示（“*”表示可同機(jī)飛行）。每?jī)r(jià)飛機(jī)出航時(shí)需正、副駕駛員各一人，問(wèn)最多能有幾架飛機(jī)同時(shí)出航？應(yīng)如何安排正、副駕駛員？第一百四十六頁(yè)，共一百六十頁(yè)，編輯于2023年，星期二正、副駕駛員同機(jī)飛行情況正副B1B2B3B4B5A1