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

1、第第6章章 圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析1. 圖的基本概念與模型圖的基本概念與模型2. 樹圖和圖的最小部分樹樹圖和圖的最小部分樹3. 最短路問題最短路問題4. 網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流5. 最小費(fèi)用流最小費(fèi)用流1.圖的基本概念與模型圖的基本概念與模型v 運(yùn)籌學(xué)中研究的圖用來表明一些研究運(yùn)籌學(xué)中研究的圖用來表明一些研究對(duì)象對(duì)象和這些對(duì)象之和這些對(duì)象之間的相互間的相互關(guān)系關(guān)系。v 用點(diǎn)表示研究對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則用點(diǎn)表示研究對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖圖g可以定義為可以定義為點(diǎn)點(diǎn)和和邊邊的集合，記作的集合，記作g=v，ev 如果給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù)，如距離、如果

2、給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù)，如距離、費(fèi)用等，稱為費(fèi)用等，稱為網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖。1v4v2v3v5v1e2e3e7e6e5e8e4ev 端點(diǎn)、關(guān)聯(lián)邊、相鄰端點(diǎn)、關(guān)聯(lián)邊、相鄰v 環(huán)、多重邊、簡(jiǎn)單圖環(huán)、多重邊、簡(jiǎn)單圖v 次、奇點(diǎn)、偶點(diǎn)、孤立點(diǎn)次、奇點(diǎn)、偶點(diǎn)、孤立點(diǎn)v 鏈、圈、路、回路、連通圖鏈、圈、路、回路、連通圖v 完全圖、偶圖完全圖、偶圖v 子圖、部分圖子圖、部分圖4v2v3v5v7e6e8e4e1v4v2v3v5v2e3e7e6e8e4e【例【例】有甲、乙、丙、丁、戊、己六名運(yùn)動(dòng)員報(bào)名參加有甲、乙、丙、丁、戊、己六名運(yùn)動(dòng)員報(bào)名參加a、b、c、d、e、f六個(gè)項(xiàng)目的比賽。如下表所示，打六個(gè)項(xiàng)目

3、的比賽。如下表所示，打的是各運(yùn)動(dòng)員報(bào)名參加的比賽的是各運(yùn)動(dòng)員報(bào)名參加的比賽項(xiàng)目。問六個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都不連續(xù)地項(xiàng)目。問六個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。參加兩項(xiàng)比賽。abcdef甲甲乙乙丙丙丁丁戊戊己己acbedf2. 樹圖和圖的最小部分樹樹圖和圖的最小部分樹v樹圖是無圈的連通樹圖是無圈的連通圖。圖。v性質(zhì)性質(zhì)1：任何樹圖中：任何樹圖中必存在次為必存在次為1的點(diǎn)；的點(diǎn)；v性質(zhì)性質(zhì)2：具體：具體n個(gè)頂個(gè)頂點(diǎn)的樹圖的邊數(shù)恰點(diǎn)的樹圖的邊數(shù)恰好為（好為（n-1）條；）條；v性質(zhì)性質(zhì)3：任何具有：任何具有n個(gè)點(diǎn)、（個(gè)點(diǎn)、（n-1）條邊）條邊的連

4、通圖是樹圖。的連通圖是樹圖。2. 樹圖和圖的最小部分樹樹圖和圖的最小部分樹v圖的最小部分樹圖的最小部分樹 如果如果g1是是g2的部分樹，又是樹圖，則稱的部分樹，又是樹圖，則稱g1是是g2的部分的部分樹（或支撐樹）。樹（或支撐樹）。 樹圖的各條邊稱為樹枝，一般圖含有多個(gè)部分樹，其樹圖的各條邊稱為樹枝，一般圖含有多個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹。中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹。 定理定理1：圖中任一個(gè)點(diǎn)：圖中任一個(gè)點(diǎn)i，若，若j是與是與i相鄰點(diǎn)中距離最近的，相鄰點(diǎn)中距離最近的，則邊則邊i，j一定必含在該圖的最小部分樹內(nèi)。一定必含在該圖的最小部分樹內(nèi)。 推論：

5、把圖的所有點(diǎn)分為推論：把圖的所有點(diǎn)分為v和和v兩個(gè)集合，則兩集合之兩個(gè)集合，則兩集合之間連線的最短邊一定包含在最小部分樹內(nèi)。間連線的最短邊一定包含在最小部分樹內(nèi)。de避避圈圈法法【例】如下圖所示，【例】如下圖所示，s、a、b、c、d、e、t代表村鎮(zhèn)，代表村鎮(zhèn)，它們間連線表明村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁數(shù)字代它們間連線表明村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁數(shù)字代表道路的長(zhǎng)度?，F(xiàn)要求沿圖中道路架設(shè)電線，使上述村鎮(zhèn)表道路的長(zhǎng)度?，F(xiàn)要求沿圖中道路架設(shè)電線，使上述村鎮(zhèn)全部同上電，應(yīng)如何架設(shè)使總的路線長(zhǎng)度為最短。全部同上電，應(yīng)如何架設(shè)使總的路線長(zhǎng)度為最短。bsact254175213574de破破圈圈法法【

6、例】如下圖所示，【例】如下圖所示，s、a、b、c、d、e、t代表村鎮(zhèn)，代表村鎮(zhèn)，它們間連線表明村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁數(shù)字代它們間連線表明村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁數(shù)字代表道路的長(zhǎng)度。現(xiàn)要求沿圖中道路架設(shè)電線，使上述村鎮(zhèn)表道路的長(zhǎng)度?，F(xiàn)要求沿圖中道路架設(shè)電線，使上述村鎮(zhèn)全部同上電，應(yīng)如何架設(shè)使總的路線長(zhǎng)度為最短。全部同上電，應(yīng)如何架設(shè)使總的路線長(zhǎng)度為最短。bsact2541752135743. 最短路問題最短路問題v最短路問題一般來說就是最短路問題一般來說就是從給定的網(wǎng)絡(luò)圖中找出從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之間距離最短的一條路任意兩點(diǎn)之間距離最短的一條路。這里的距離只。這里的距離只是

7、權(quán)數(shù)的代稱，在實(shí)際的網(wǎng)絡(luò)圖中，權(quán)數(shù)可以是是權(quán)數(shù)的代稱，在實(shí)際的網(wǎng)絡(luò)圖中，權(quán)數(shù)可以是時(shí)間、費(fèi)用等。時(shí)間、費(fèi)用等。v求解最短路問題有兩種算法：求解最短路問題有兩種算法： 求從某一點(diǎn)至其它各點(diǎn)之間最短求從某一點(diǎn)至其它各點(diǎn)之間最短距離的距離的狄克斯屈拉狄克斯屈拉（dijkstra）算法；算法； 求網(wǎng)絡(luò)圖上任意兩點(diǎn)之間最短距求網(wǎng)絡(luò)圖上任意兩點(diǎn)之間最短距離的離的矩陣矩陣算法；算法；狄狄克克斯斯屈屈拉拉算算法法1v2v3v4v5v6v7v5722126643701. l11=02. l1p=minl11+d12, l11+d13=min0+5, 0+2=2=l133. l1p=minl11+d12, l13

8、+d34, l13+d36=min0+5, 2+7, 2+4=5=l124. l1p=minl12+d25, l12+d24, l13+d34, l13+d36= =min5+7, 5+2, 2+7, 2+4=6=l16256狄狄克克斯斯屈屈拉拉算算法法1v2v3v4v5v6v7v5722126643705. l1p=minl12+d25, l12+d24, l13+d34, l16+d64, l16+d65, l16+d67=min5+7, 5+2, 2+7, 6+2, 6+1, 6+6=7=l14=l156. l1p=minl15+d57, l16+d67=min7+3, 6+6=10 =

9、l172567710【練習(xí)【練習(xí)】1v2v3v4v5v6v7v465715524168045591016矩矩陣陣算算法法1v2v3v4v5v6v7v57221266437111213141516172122232425262731323334353637(0)4142434445464751525354555657616263646566677172737475767705250272074270dddddddddddddddddddddddddddddddddddddddddddddddddd 627601342106360構(gòu)造一個(gè)新矩陣構(gòu)造一個(gè)新矩陣d（1）, 該矩陣給出了網(wǎng)絡(luò)中任意兩點(diǎn)之

10、間直該矩陣給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)和包括一個(gè)中間點(diǎn)時(shí)的最短距離。矩陣接到達(dá)和包括一個(gè)中間點(diǎn)時(shí)的最短距離。矩陣d（1）中每個(gè)元中每個(gè)元素的計(jì)算方式為：素的計(jì)算方式為：(1)minijirrjddd(0)05250272074270627601342106360d (1)05271265072741027065410726032812753013644210410108340d一般有矩陣一般有矩陣d（k）給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)，經(jīng)過給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)，經(jīng)過一個(gè)、兩個(gè)、一個(gè)、兩個(gè)、到（、到（2k-1）個(gè)中間點(diǎn)時(shí)比較得到的最短距）個(gè)中間點(diǎn)時(shí)比較得到的最短距離。矩陣離。矩

11、陣d（k）中每個(gè)元素的計(jì)算方式為：中每個(gè)元素的計(jì)算方式為：( )(1)(1)minkkkijirrjddd(1)05271265072741027065410726032812753013644210410108340d(2)052776105072548270654872603267553013644210410886340d(3)(2)dd【例】某人購買一臺(tái)摩托車，準(zhǔn)備在今后【例】某人購買一臺(tái)摩托車，準(zhǔn)備在今后4年內(nèi)使用。他可在第一年初年內(nèi)使用。他可在第一年初購買一臺(tái)新車，連續(xù)使用購買一臺(tái)新車，連續(xù)使用4年，也可于任何一年末換一臺(tái)新車。已知各年，也可于任何一年末換一臺(tái)新車。已知各年初的新車

12、購置價(jià)如下表年初的新車購置價(jià)如下表1。不同役齡車的年使用維護(hù)費(fèi)及年末處理價(jià)。不同役齡車的年使用維護(hù)費(fèi)及年末處理價(jià)如下表如下表2。要求確定該人使用摩托車的最優(yōu)更新策略，使。要求確定該人使用摩托車的最優(yōu)更新策略，使4年內(nèi)用于購買、年內(nèi)用于購買、更新及使用維護(hù)的總費(fèi)用為最省。單位：萬元。更新及使用維護(hù)的總費(fèi)用為最省。單位：萬元。第一年第一年第二年第二年第三年第三年第四年第四年年初的購置價(jià)年初的購置價(jià)2.52.62.83.1摩托車役齡摩托車役齡01年年12年年23年年34年年年使用維護(hù)費(fèi)年使用維護(hù)費(fèi)0.30.50.81.2該役齡年末處該役齡年末處理費(fèi)理費(fèi)2.01.61.31.1第一年第一年第二年第二年

13、第三年第三年第四年第四年年初的購置價(jià)年初的購置價(jià)2.52.62.83.1摩托車役齡摩托車役齡01年年12年年23年年34年年年使用維護(hù)費(fèi)年使用維護(hù)費(fèi)0.30.50.81.2該役齡年末處該役齡年末處理費(fèi)理費(fèi)2.01.61.31.11v2v3v4v5v0.80.91.11.41.71.822.82.94.200.81.72.63.7一個(gè)郵遞員從郵局出發(fā)，走遍他負(fù)責(zé)投遞的每一條街道，然一個(gè)郵遞員從郵局出發(fā)，走遍他負(fù)責(zé)投遞的每一條街道，然后再返回郵局，問應(yīng)選擇什么樣的路線，使走的路程為最短。后再返回郵局，問應(yīng)選擇什么樣的路線，使走的路程為最短。因?yàn)檫@個(gè)問題由中國(guó)數(shù)學(xué)工作者提出，故稱為因?yàn)檫@個(gè)問題由中國(guó)

14、數(shù)學(xué)工作者提出，故稱為中國(guó)郵路問題中國(guó)郵路問題。歐拉回路歐拉回路的定義是：連通圖的定義是：連通圖g中，若存在一條回路，經(jīng)過每中，若存在一條回路，經(jīng)過每邊一次且僅一次，稱這條回路為歐拉回路。稱具有歐拉回路邊一次且僅一次，稱這條回路為歐拉回路。稱具有歐拉回路的圖為歐拉圖。的圖為歐拉圖。【例【例】設(shè)某郵遞員設(shè)某郵遞員負(fù)責(zé)投遞的街道如負(fù)責(zé)投遞的街道如圖所示，要求找出圖所示，要求找出該郵遞員的最短投該郵遞員的最短投遞路線。遞路線。1v2v3v4v5v6v7v8v9v10v11v12v13v44575412454214422連通圖連通圖g是歐拉圖的充分必要條件是圖中的點(diǎn)全為是歐拉圖的充分必要條件是圖中的點(diǎn)

15、全為偶點(diǎn)偶點(diǎn)。（1）每條邊上最多重復(fù)一次；）每條邊上最多重復(fù)一次；（2）在圖）在圖g的每個(gè)回路上，有重復(fù)邊的長(zhǎng)度不超過回路總的每個(gè)回路上，有重復(fù)邊的長(zhǎng)度不超過回路總長(zhǎng)的一半。長(zhǎng)的一半。1v2v3v4v5v6v7v8v9v10v11v12v13v445754124542144224. 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流v 網(wǎng)絡(luò)最大流的有關(guān)概念網(wǎng)絡(luò)最大流的有關(guān)概念1. 有向圖與容量網(wǎng)絡(luò)有向圖與容量網(wǎng)絡(luò) 有向圖上的連線是有規(guī)定指向的，稱作有向圖上的連線是有規(guī)定指向的，稱作弧?。?所謂容量網(wǎng)絡(luò)是指對(duì)網(wǎng)絡(luò)上的每條弧都給出一個(gè)所謂容量網(wǎng)絡(luò)是指對(duì)網(wǎng)絡(luò)上的每條弧都給出一個(gè)最大的通過能力，稱為該最大的通過能力，稱為該弧的容量

16、弧的容量，記為，記為c(vi, vj)或簡(jiǎn)寫或簡(jiǎn)寫cij； 在容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)在容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)發(fā)點(diǎn)（記為（記為s）和一個(gè)）和一個(gè)收點(diǎn)收點(diǎn)（記為（記為t），網(wǎng)絡(luò)中既非發(fā)點(diǎn)又非收點(diǎn)的其它），網(wǎng)絡(luò)中既非發(fā)點(diǎn)又非收點(diǎn)的其它點(diǎn)稱為中間點(diǎn)；點(diǎn)稱為中間點(diǎn)； 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量。過的最大流量。4. 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流2.流與可行流流與可行流所謂所謂流流是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量，記是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量，記作作f(vi ,vj)或簡(jiǎn)寫為或簡(jiǎn)寫為fij；若網(wǎng)絡(luò)上所有的若網(wǎng)絡(luò)上所有的fij=0，這個(gè)流

17、稱為，這個(gè)流稱為零流零流；在容量網(wǎng)絡(luò)上滿足以下條件的一組流稱為可行流：在容量網(wǎng)絡(luò)上滿足以下條件的一組流稱為可行流：i.容量限制條件，對(duì)所有弧有容量限制條件，對(duì)所有弧有ii. 中間點(diǎn)平衡條件中間點(diǎn)平衡條件0( ,)( ,)ijijf v vc v v( ,)(,)0 (, )ijjif v vf v v is t4. 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流v割和流量割和流量割是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使割是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使st的流中斷的一組弧的集合。的流中斷的一組弧的集合。割的容量是組成它的集合中的各弧的容量之和。割的容量是組成它的集合中的各弧的容量之和。st1v2v3v4v9(

18、4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)st1v2v3v4v9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)vv割割容量容量1234,v v v v t12( ,)( ,)s vs v15s1, s v234,v v v t13122( ,)( ,)( ,)v vv vs v212, s v134,v v v t124( ,)(,)s vv v1712,s v v34,v v t1324( ,)(,)v vv v1813,s v v24,v v t332122( , )( ,)( ,)( ,)v t v vv vs v1924,s v v

19、13,v v t1434( ,)(,)(, )s vv vv t24123,s v v v4,v t243(,)( , )v vv t14124,s v v v3,v t13434( ,)(,)(, )v vv vv t251234,s v v v vt34( , )(, )v t v t154. 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流v最大流最小割定理最大流最小割定理如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在這條如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在這條鏈上所有指向?yàn)殒溕纤兄赶驗(yàn)閟t的弧（稱為的?。ǚQ為前向弧前向弧，記作，記作 + +），），存在存在f0，這樣的鏈稱為，這樣的鏈稱為增廣鏈增廣鏈。11fc

20、20f 30f 44fc55fcst4. 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流v最大流最小割定理最大流最小割定理當(dāng)增廣鏈存在時(shí)，找出當(dāng)增廣鏈存在時(shí)，找出再令再令定理：定理：在網(wǎng)絡(luò)中在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的的最大流量等于它的最小割集的容量容量。()min0iiicf f對(duì)對(duì)對(duì)對(duì)iiiffff 對(duì)對(duì)所所有有對(duì)對(duì)所所有有對(duì)對(duì)非非增增廣廣鏈鏈上上的的弧弧4. 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流vford-fulkerson標(biāo)號(hào)算法標(biāo)號(hào)算法1.首先給發(fā)點(diǎn)首先給發(fā)點(diǎn)s標(biāo)號(hào)標(biāo)號(hào) 。括弧中的第一個(gè)數(shù)字是。括弧中的第一個(gè)數(shù)字是使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào)；括弧中的第使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào)；括弧中的第二個(gè)數(shù)字表示

21、從上一個(gè)標(biāo)號(hào)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的二個(gè)數(shù)字表示從上一個(gè)標(biāo)號(hào)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值。最大允許調(diào)整值。2.列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：i. 考慮從已標(biāo)號(hào)點(diǎn)考慮從已標(biāo)號(hào)點(diǎn)i出發(fā)的?。ǔ霭l(fā)的弧（i，j）：）：(0, ( )sijijfcj點(diǎn)不標(biāo)號(hào)點(diǎn)不標(biāo)號(hào)ijijfcj點(diǎn)標(biāo)號(hào)點(diǎn)標(biāo)號(hào)( , ( )ij( )min ( ),()ijijjicf2.列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：ii.考慮所有指向已標(biāo)號(hào)點(diǎn)考慮所有指向已標(biāo)號(hào)點(diǎn)i的?。ǖ幕。╤，i）：）：iii.如果某未標(biāo)號(hào)點(diǎn)如果某未標(biāo)號(hào)點(diǎn)k有兩個(gè)以上相鄰的標(biāo)號(hào)點(diǎn)，為減少迭有

22、兩個(gè)以上相鄰的標(biāo)號(hào)點(diǎn)，為減少迭代次數(shù)，可按代次數(shù)，可按i、ii中所述規(guī)則分別計(jì)算出中所述規(guī)則分別計(jì)算出 的值，的值，并取其中最大的一個(gè)標(biāo)記。并取其中最大的一個(gè)標(biāo)記。3.重復(fù)第重復(fù)第2步，可能出現(xiàn)兩種結(jié)局：步，可能出現(xiàn)兩種結(jié)局：i.標(biāo)號(hào)過程中斷，標(biāo)號(hào)過程中斷，t得不到標(biāo)號(hào)，說明網(wǎng)絡(luò)中不存在增廣得不到標(biāo)號(hào)，說明網(wǎng)絡(luò)中不存在增廣鏈，給定的流量即為最大流。記已標(biāo)號(hào)點(diǎn)的集合為鏈，給定的流量即為最大流。記已標(biāo)號(hào)點(diǎn)的集合為v,未未標(biāo)號(hào)點(diǎn)集合為標(biāo)號(hào)點(diǎn)集合為v，（，（v，v）為網(wǎng)絡(luò)的最小割；）為網(wǎng)絡(luò)的最小割；ii.t點(diǎn)得到標(biāo)號(hào)，反向追蹤找出增廣鏈；點(diǎn)得到標(biāo)號(hào)，反向追蹤找出增廣鏈；0hifh點(diǎn)不標(biāo)號(hào)點(diǎn)不標(biāo)號(hào)0hi

23、fh點(diǎn)標(biāo)號(hào)點(diǎn)標(biāo)號(hào)( , ( )ih( )min ( ),hihif( )k4.修改流量，設(shè)圖中原有可行流為修改流量，設(shè)圖中原有可行流為f，按一下方式獲得，按一下方式獲得新的可行流新的可行流f：5.抹掉圖中所有標(biāo)號(hào)，重復(fù)第抹掉圖中所有標(biāo)號(hào)，重復(fù)第1到第到第4步，直至圖中找步，直至圖中找不到任何增廣鏈，即出現(xiàn)第不到任何增廣鏈，即出現(xiàn)第3步的結(jié)局步的結(jié)局i為止，這時(shí)為止，這時(shí)網(wǎng)絡(luò)圖中的流量即為最大流。網(wǎng)絡(luò)圖中的流量即為最大流。( )( )ftfftf 對(duì)對(duì)增增廣廣鏈鏈上上所所有有前前向向弧弧對(duì)對(duì)增增廣廣鏈鏈上上所所有有后后向向弧弧所所有有非非增增廣廣鏈鏈上上的的弧弧st1v2v3v4v9(4)9(9

24、)8(8)7(5)5(4)2(0)6(1)5(5)10(8)(0,)( ,2)s2(,2)v1( ,2)v3( ,1)v4(,1)vst1v2v3v4v9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(5)10(8)7(6)5(3)9(5)6(0)10(9)(0,)( ,1)s2(,1)v1( ,1)v(0,)最小割最小割最大流：最大流：14324( , ),(,)v tv vst1v2v3v4v5v5(5)6(4)3(3)5(4)2(0)3(3)3(2)4(4)2(2)2(0)8(6)6(6)st1v2v3v4v5v5(5)6(5)3(3)5(5)2(0)3(2)3(3)4(4)2

25、(1)2(0)8(7)6(6)(0,)( ,2)s2(,1)v5(,1)v3( ,1)v1( ,1)v4(,1)v(0,)( ,1)s最小割最小割最大流：最大流：131325(,),(,),(,)ssvvvv vvdbceaf1234567891011 1213【例】某河流中有【例】某河流中有4個(gè)島嶼，從兩岸至各島嶼及各島嶼之間個(gè)島嶼，從兩岸至各島嶼及各島嶼之間的橋梁編號(hào)如圖所示，在一次敵對(duì)的軍事行動(dòng)中，問至少應(yīng)的橋梁編號(hào)如圖所示，在一次敵對(duì)的軍事行動(dòng)中，問至少應(yīng)炸斷哪幾座橋梁，才能完全切斷兩岸的交通聯(lián)系？炸斷哪幾座橋梁，才能完全切斷兩岸的交通聯(lián)系？dbceaf1234567891011 12

26、13abcdef221211113abcdef2(1)21(1)2(1)1111(1)3(1)abcdef2(1)21(1)2(1)1111(1)3(1)(0,)( ,1)a( ,2)a( ,1)b( ,1)d( ,1)eabcdef2(2)21(1)2(2)111(1)1(1)3(2)(0,)( ,2)a( ,1)c( ,1)d最小割：最小割：(d, f), (d, e), (a, e)dbceaf1234567891011 12135. 最小費(fèi)用流最小費(fèi)用流v最小費(fèi)用流問題最小費(fèi)用流問題對(duì)于容量網(wǎng)絡(luò)，除考慮各條弧上的流量、容量外，對(duì)于容量網(wǎng)絡(luò)，除考慮各條弧上的流量、容量外，還需考慮弧上通過

27、單位流量時(shí)的費(fèi)用（還需考慮弧上通過單位流量時(shí)的費(fèi)用（bij），保），保證最終給出的流量或最大流也是費(fèi)用最少的。證最終給出的流量或最大流也是費(fèi)用最少的。關(guān)鍵點(diǎn)：確定關(guān)鍵點(diǎn)：確定“最小費(fèi)用增廣鏈最小費(fèi)用增廣鏈”。st1v2v3v(5, 8)(8, 7)(2, 5)(4, 9)(10, 9)(3, 2)(8, 4)【例】各弧旁數(shù)字【例】各弧旁數(shù)字為為(cij, bij)，試求圖，試求圖中從中從st的最小費(fèi)的最小費(fèi)用最大流。用最大流。1.從原容量網(wǎng)絡(luò)的零流從原容量網(wǎng)絡(luò)的零流f0開始；開始；2.對(duì)原容量網(wǎng)絡(luò)的可行流對(duì)原容量網(wǎng)絡(luò)的可行流fk構(gòu)造構(gòu)造加權(quán)網(wǎng)絡(luò)加權(quán)網(wǎng)絡(luò)w(fk):對(duì)對(duì)0fijcij的弧的弧(i

28、, j)，在加權(quán)網(wǎng)絡(luò)的，在加權(quán)網(wǎng)絡(luò)的i點(diǎn)和點(diǎn)和j點(diǎn)之間分別繪制弧點(diǎn)之間分別繪制弧(i, j)和和(j, i)，其權(quán)數(shù)分別為，其權(quán)數(shù)分別為bij和和-bij；對(duì)對(duì)fij=cij的弧，在加權(quán)網(wǎng)絡(luò)的的弧，在加權(quán)網(wǎng)絡(luò)的i點(diǎn)和點(diǎn)和j點(diǎn)之間繪制弧點(diǎn)之間繪制弧(j, i)，其權(quán)數(shù)為，其權(quán)數(shù)為-bij；對(duì)對(duì)fij=0的弧，在加權(quán)網(wǎng)絡(luò)的的弧，在加權(quán)網(wǎng)絡(luò)的i點(diǎn)和點(diǎn)和j點(diǎn)之間繪制弧點(diǎn)之間繪制弧(i, j)，其權(quán)數(shù)為，其權(quán)數(shù)為bij。3.確定最小費(fèi)用增廣鏈等價(jià)于求解加權(quán)網(wǎng)絡(luò)確定最小費(fèi)用增廣鏈等價(jià)于求解加權(quán)網(wǎng)絡(luò)st之間的最之間的最短路。找出增廣鏈之后調(diào)整原容量網(wǎng)絡(luò)的流量；短路。找出增廣鏈之后調(diào)整原容量網(wǎng)絡(luò)的流量；4.重

29、復(fù)重復(fù)2、3步驟，直到步驟，直到st之間找不出最短路為止，此時(shí)之間找不出最短路為止，此時(shí)求得原容量網(wǎng)絡(luò)的最小費(fèi)用最大流。求得原容量網(wǎng)絡(luò)的最小費(fèi)用最大流。5. 最小費(fèi)用流最小費(fèi)用流st1v2v3v(5, 8)(8, 7)(2, 5)(4, 9)(10, 9)(3, 2)(8, 4)1vt2v3vs87599240781014st1v2v3v5(3)8(0)2(0)4(0)10(0)3(3)8(3)st1v2v3v(5, 8)(8, 7)(2, 5)(4, 9)(10, 9)(3, 2)(8, 4)st1v2v3v5(3)8(0)2(0)4(0)10(0)3(3)8(3)1vt2v3vs875994-8-2-412312308780950920440 s v v v tsvvvt(0)d(1)d(2)d12312308716178015935091310204640 s v v v tsvvvt123123087131780159350913102304146740 s v v v tsvvvt1vt2v3vs875994-8-2-4st1v2v3v5(3)8(0)2(0)4(0)10(0)3(3)8(3)st1v2v3v5(5)8(0)2(0)4(2)10(0)3(3)8(3)1vt2v3vs875994-8-2-4st1v2v3v(5, 8)(8, 7)(2,