運(yùn)籌學(xué)-第六章圖與網(wǎng)絡(luò)分析課件

1、2022/10/151第六章 圖與網(wǎng)絡(luò)分析 2022/10/111第六章 圖與網(wǎng)絡(luò)分析 2022/10/152學(xué)習(xí)目標(biāo)理解有向圖、無(wú)向圖的相關(guān)概念理解樹、支撐樹、最小支撐樹的概念掌握求解支撐樹和最小支撐樹的破圈法和避圈法掌握求解最短路的算法掌握求解最大流的算法掌握求解最小費(fèi)用最大流的算法2022/10/112學(xué)習(xí)目標(biāo)2022/10/153Modern公司的光纖聯(lián)網(wǎng)問(wèn)題Modern公司決定鋪設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)，以便為它的主要中心之間提供高速的數(shù)據(jù)、聲音和圖像等高速通信。該公司的主要中心包括公司的總部、巨型計(jì)算機(jī)、研究區(qū)、生產(chǎn)和配送中心，根據(jù)各中心的分布，公司分析設(shè)計(jì)了可能的光纖鋪設(shè)位置如下圖6-

2、1所示，每條虛線旁邊的數(shù)字表示在該位置鋪設(shè)光纖所需的成本（單位：百萬(wàn)美元）。2022/10/113Modern公司的光纖聯(lián)網(wǎng)問(wèn)題Mode2022/10/154圖6-1 光纖鋪設(shè)位置分析2022/10/114圖6-1 光纖鋪設(shè)位置分析2022/10/155 考慮到光纖技術(shù)在中心之間高速通信的優(yōu)勢(shì)，所以不需在每?jī)蓚€(gè)中心之間都用一條光纖把他們直接連接起來(lái)。那些需要光纖直接連接的中心有一系列的光纖連接他們。 因此，公司面臨的問(wèn)題是如何選擇在哪兩個(gè)中心之間鋪設(shè)光纖，能夠使得每?jī)蓚€(gè)中心之間都是聯(lián)通的，但是同時(shí)總的通信成本又是最低的。2022/10/115 考慮到光纖技術(shù)在中心之間高速通2022/10/15

3、6 圖論是運(yùn)籌學(xué)中有著廣泛應(yīng)用的一個(gè)分支。管理科學(xué) 、計(jì)算機(jī)科學(xué) 、信息論 、控制論 、物理 、化學(xué) 、生物學(xué) 、心理學(xué)等不同領(lǐng)域內(nèi)的許多問(wèn)題都可以描述為圖論模型來(lái)解決。 隨著科學(xué)技術(shù)的發(fā)展以及電子計(jì)算機(jī)的出現(xiàn)和應(yīng)用，20世紀(jì) 50年代，圖論的理論得到了進(jìn)一步的發(fā)展。將寵大復(fù)雜的工程和管理問(wèn)題用圖描述，可以解決很多工程設(shè)計(jì)和管理決策的最優(yōu)化問(wèn)題。 歐拉 (E. Euler)在 1736年發(fā)表圖論方面的第一篇論文解決了著名的哥尼斯堡七橋問(wèn)題，被公認(rèn)為是圖論的創(chuàng)始人。2022/10/116 圖論是運(yùn)籌學(xué)中有著廣泛應(yīng)2022/10/157 18世紀(jì)的哥尼斯堡城中流過(guò)一條河 (普雷格爾河)，河上有七座

4、橋連結(jié)著河的兩岸和河中的兩個(gè)小島，如圖6-2所示。當(dāng)時(shí)，那里的人們熱衷于這樣的問(wèn)題：一個(gè)散步者能否走過(guò)七座橋，且每座橋只走過(guò)一次，最后回到出發(fā)點(diǎn)。沒(méi)有人想出這種走法，也沒(méi)有人證明不存在這種走法，這就是著名的“七橋”難題 。2022/10/117 18世紀(jì)的哥尼斯堡城中流2022/10/1582022/10/1182022/10/159 歐拉把這個(gè)試驗(yàn)化為下圖所示的一個(gè)圖論問(wèn)題。它用結(jié)點(diǎn)A，B，C，D分別表示對(duì)應(yīng)的陸地，用邊來(lái)表示連接陸地的橋。這樣哥尼斯堡七橋問(wèn)題就轉(zhuǎn)化 為下圖中尋求 一條包含每邊 一次的回路問(wèn) 題。圖6-3 “七橋難題”圖解2022/10/119 歐拉把這個(gè)試驗(yàn)化為下圖2022

5、/10/1510 歐拉證明七橋問(wèn)題無(wú)解，因?yàn)閳D中的每個(gè)點(diǎn)都只與奇數(shù)條線相關(guān)聯(lián)，不可能將這個(gè)圖不重復(fù)地一筆畫成。 從而解決了這一難題，它的抽象與論證方法開創(chuàng)了圖論科學(xué)的研究。 隨著科學(xué)技術(shù)的發(fā)展以及電子計(jì)算機(jī)的出現(xiàn)與廣泛應(yīng)用，二十世紀(jì)五十年代，圖論的理論得到進(jìn)一步發(fā)展。將龐大復(fù)雜的工程系統(tǒng)和管理問(wèn)題用圖描述，可以解決很多工程設(shè)計(jì)和管理決策的最優(yōu)化問(wèn)題。 例如，完成工程任務(wù)的時(shí)間最少，距離最短，費(fèi)用最省等等。圖論受到數(shù)學(xué)、工程技術(shù)及經(jīng)營(yíng)管理等各個(gè)方面越來(lái)越廣泛的重視。2022/10/1110 歐拉證明七橋問(wèn)題無(wú)解，2022/10/15116.1 圖與網(wǎng)絡(luò)基本知識(shí) 在生產(chǎn)和日常生活中經(jīng)常碰到各種各樣

6、的圖：公路或鐵路交通圖、管網(wǎng)圖、電網(wǎng)圖、通訊聯(lián)絡(luò)圖等. 運(yùn)籌學(xué)中所研究的圖（graph）是上述各類圖的抽象概括，它表明一些研究對(duì)象和這些對(duì)象之間的相互聯(lián)系。如交通圖是表明一些城鎮(zhèn)及城鎮(zhèn)之間的道路溝通情況；管網(wǎng)圖是表明供應(yīng)源、用戶、中間加壓站之間管網(wǎng)的聯(lián)系情況等。2022/10/11116.1 圖與網(wǎng)絡(luò)基本知識(shí)2022/10/1512 例6-1 為了反映五個(gè)球隊(duì)的賽事關(guān)系，可以用點(diǎn)表示球隊(duì)，用點(diǎn)間連線表示兩個(gè)球隊(duì)已進(jìn)行過(guò)比賽，如圖6-4所示。其中點(diǎn) 分別表示5個(gè)球隊(duì)，兩點(diǎn)的連接表示兩球隊(duì)之間的賽事關(guān)系。因此，從圖中可反映出 球隊(duì)分別與 球隊(duì)有賽事； 球隊(duì)還與 球隊(duì)， 球隊(duì)還與 球隊(duì)有賽事。202

7、2/10/1112 例6-1 為了反映五個(gè)球隊(duì)的2022/10/1513圖6-4 球隊(duì)賽事關(guān)系圖2022/10/1113圖6-4 球隊(duì)賽事關(guān)系圖2022/10/1514例6-2 為了描述城市間的交通，可以用點(diǎn)表示城市，用點(diǎn)間連線表示城市間的道路，如果連線旁標(biāo)注城市間的距離網(wǎng)絡(luò)圖中稱為權(quán)，形成加權(quán)圖，就稱為網(wǎng)絡(luò)圖，就可進(jìn)一步研究從一個(gè)城市到另一個(gè)城市的最短路徑；或者標(biāo)上單位運(yùn)價(jià)，就可分析運(yùn)費(fèi)最小的運(yùn)輸方案。圖6-5是一張7個(gè)城市間物資運(yùn)輸關(guān)系的運(yùn)輸網(wǎng)示意圖， 表示7個(gè)城市，箭線旁的數(shù)字表示物流的單位運(yùn)價(jià)。2022/10/1114例6-2 為了描述城市間的交通，可以2022/10/1515圖6-5

8、 物資運(yùn)輸關(guān)系圖2022/10/1115圖6-5 物資運(yùn)輸關(guān)系圖2022/10/1516 由此看出，用圖來(lái)描述事物間的聯(lián)系，不僅直觀清晰，便于統(tǒng)觀全局，而且圖中點(diǎn)的相對(duì)位置，連線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不重要。如上述球隊(duì)比賽的例子也可以用6-6所示的圖表示，這與圖6-4沒(méi)有本質(zhì)的區(qū)別。圖6-6 球隊(duì)賽事關(guān)系圖2022/10/1116 由此看出，用圖來(lái)描述事物間的2022/10/1517 前面幾個(gè)例子涉及到的對(duì)象之間的“關(guān)系”具有“對(duì)稱性”，即如果甲與乙有這種關(guān)系，那么同時(shí)，乙與甲也有這種關(guān)系。但在現(xiàn)實(shí)生活中，有許多關(guān)系不具有這種對(duì)稱性，比如，球隊(duì)比賽的勝負(fù)關(guān)系，甲勝乙，那么乙就不能

9、勝甲。反映這種非對(duì)稱關(guān)系，不能只用一條連線，可以用一條帶箭頭的連線表示。如球隊(duì) 勝了球隊(duì) ，可以從 引一條帶箭頭的連線到 。如圖6-7反映了五個(gè)球隊(duì)的勝負(fù)情況。2022/10/1117 前面幾個(gè)例子涉及到的對(duì)象之間2022/10/1518圖6-7 球隊(duì)勝負(fù)關(guān)系圖 綜上，一個(gè)圖是由一些點(diǎn)和一些點(diǎn)之間的連線（不帶箭頭和帶箭頭）組成。為區(qū)別起見(jiàn)，把兩點(diǎn)之間不帶箭頭的連線成為邊，帶箭頭的連線成為弧。2022/10/1118圖6-7 球隊(duì)勝負(fù)關(guān)系圖 綜2022/10/15191、無(wú)向圖 (1)無(wú)向圖 定義6-1無(wú)向圖是由點(diǎn)及邊所構(gòu)成的無(wú)序二元組 ，記為 ，其中 是 個(gè)點(diǎn)的集合，簡(jiǎn)稱頂點(diǎn)集； 是 條邊的集

10、合，簡(jiǎn)稱邊集合。連接點(diǎn) 的邊記為 或 。圖6-8即為無(wú)向圖，圖中： 2022/10/11191、無(wú)向圖 2022/10/1520點(diǎn)集 中元素的個(gè)數(shù)稱為圖G的頂點(diǎn)數(shù)，記為 如圖6-7， 。邊集E中元素的個(gè)數(shù)稱為圖G的邊數(shù)，記為 。如圖6-8， 。若邊 ，稱 為e的端點(diǎn)，e為 的關(guān)聯(lián)邊。圖6-8中， 為 的端點(diǎn)， 為 的關(guān)聯(lián)邊。若點(diǎn) 有邊相連，即 ，則稱 相鄰， 與e關(guān)聯(lián)。如圖6-8中， 相鄰， 與 關(guān)聯(lián)。2022/10/1120點(diǎn)集 中元素的個(gè)數(shù)稱為圖G的頂點(diǎn)數(shù)，2022/10/1521圖6-8 無(wú)向圖2022/10/1121圖6-8 無(wú)向圖2022/10/1522（2）簡(jiǎn)單圖若某邊e的兩個(gè)端點(diǎn)

11、相同，則稱e為環(huán)（自回路）。如圖6-8中的 。若兩個(gè)點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。如圖6-8中的 。定義6-2不含環(huán)和多重邊的圖稱為簡(jiǎn)單圖。無(wú)環(huán)，但含有多重邊的圖稱為多重圖。（3） 點(diǎn)的次（度） 定義6-3以點(diǎn)V為端點(diǎn)的邊數(shù)叫做點(diǎn)V的次，記作如圖6-8中， 。 若 ，則稱 稱為圖 的次序列。 次為 1 的點(diǎn)稱為懸掛點(diǎn)，懸掛點(diǎn)的連接邊稱為懸掛邊。次為 0的點(diǎn)稱為孤立點(diǎn)。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。2022/10/1122（2）簡(jiǎn)單圖2022/10/1523定理 6-1 圖 中，所有點(diǎn)的次數(shù)之和等于邊數(shù)的2倍。即證明：由于每條邊必有兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被

12、計(jì)算了兩次，所以頂點(diǎn)次數(shù)之和等于邊數(shù)的2倍。定理6-2 任何圖 中奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。證明：設(shè) 和 分別為圖G中奇點(diǎn)與偶點(diǎn)的集合， 。由定理6-1 知 由于 為偶數(shù)， 也為偶數(shù)。所以 必為偶數(shù)，從而奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。2022/10/1123定理 6-1 圖 中，所有2022/10/1524（4）鏈對(duì)于無(wú)向圖 ，一個(gè)點(diǎn)和邊交替的序列 ，如果滿足 ，則稱其為連接 和的一條鏈，記為 。其中稱 和 為鏈的兩個(gè)端點(diǎn)。圖6-8中的 都是鏈。 2022/10/1124（4）鏈2022/10/1525鏈 中， ，則稱之為圈，如圖6-8中的 若 中，點(diǎn) 都是不同的，則稱之為初等鏈。若圈 中， 都是不相同的，則

13、稱之為初等圈。定義6-4 圖G中，如果任何兩個(gè)頂點(diǎn)之間都有一條鏈，該圖稱為連通圖，否則成為不連通圖。 2022/10/1125鏈 2022/10/15262、有向圖（1）有向圖 定義6-5有向圖由點(diǎn)及弧所構(gòu)成的有序二元組 ，記為 ，其中 是 個(gè)頂點(diǎn)的集合， 是 條弧的集合，并且 是一個(gè)有序二元組，記為 ，并稱 是以 為始點(diǎn)， 為終點(diǎn)的弧， 的順序不能顛倒，圖中弧的方向用箭頭標(biāo)識(shí)。圖6-9 即為有向圖，圖中： ， 2022/10/11262、有向圖2022/10/1527（2）簡(jiǎn)單有向圖 兩個(gè)端點(diǎn)重合的弧稱為環(huán)。如圖6-9 中的 。 兩個(gè)端點(diǎn)之間的同向弧數(shù)大于等于2，稱為多重弧。如圖6-9中的

14、之間的二重弧，而 之間的二重弧。無(wú)環(huán)也無(wú)多重弧的有向圖稱為簡(jiǎn)單有向圖。2022/10/1127（2）簡(jiǎn)單有向圖2022/10/1528（3）點(diǎn)的出次和入次 以點(diǎn) 為起點(diǎn)的弧數(shù)叫做點(diǎn) 的出次，記作 。如圖6-9中， 。以點(diǎn) 為終點(diǎn)的弧數(shù)叫做點(diǎn) 的入次，記作 。如圖6-9中， 。稱 為點(diǎn) 的次。如圖6-9中， 。（4）路 在有向圖 中，點(diǎn)和弧交替的序列 ，若有 或 ，則稱 是一條連接 和 的一條路；若有 ，則稱 是一條從 和 的有向路。2022/10/1128（3）點(diǎn)的出次和入次2022/10/15293、網(wǎng)絡(luò) 實(shí)際問(wèn)題中，如果只用圖來(lái)描述所研究對(duì)象之間的關(guān)系有時(shí)還不夠，需要在圖中給邊賦予一定的數(shù)

15、量指標(biāo)以描述點(diǎn)與邊之間的某些數(shù)量關(guān)系，我們常稱之為“權(quán)”。依據(jù)研究問(wèn)題的需要，權(quán)可以代表距離、時(shí)間、費(fèi)用、容量、可靠性等。通常把這種點(diǎn)或邊帶有某種數(shù)量指標(biāo)的賦權(quán)圖稱為網(wǎng)絡(luò)。與無(wú)向圖和有向圖相對(duì)應(yīng)，網(wǎng)絡(luò)又分為無(wú)向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)，如圖6-10給出了電信運(yùn)營(yíng)商vs與用戶之間的網(wǎng)絡(luò)通信圖，邊上的權(quán)重表示各點(diǎn)之間的網(wǎng)絡(luò)容量。圖6-11是從vs到vs的可通信容量。2022/10/11293、網(wǎng)絡(luò)2022/10/15302022/10/11302022/10/1531 為便于數(shù)據(jù)處理和計(jì)算機(jī)存儲(chǔ)，除了用圖形來(lái)表示圖外，還可以用矩陣來(lái)表示一個(gè)圖。 定義6-6 在圖 構(gòu)造一個(gè)矩陣 ，其中則稱 為 的關(guān)聯(lián)矩陣。關(guān)

16、聯(lián)指頂點(diǎn)與邊的關(guān)系。圖6-12的關(guān)聯(lián)矩陣圖6-12 無(wú)向網(wǎng)絡(luò)圖G2022/10/1131 為便于數(shù)據(jù)處理和計(jì)算機(jī)存儲(chǔ)，2022/10/1532定義6-7 在圖中構(gòu)造一個(gè)矩陣 ，其中則稱 為 的鄰接矩陣。鄰接指頂點(diǎn)與頂點(diǎn)的關(guān)系。圖 6-12的鄰接矩陣2022/10/1132定義6-7 在圖中圖 6-12的鄰接2022/10/1533定義6-8 在圖中其邊 圖 6-13 的權(quán)矩陣圖6-13 無(wú)向網(wǎng)絡(luò)圖G2022/10/1133定義6-8 在圖中圖 6-13 的權(quán)2022/10/15346.2 樹6.2.1 樹的概念與性質(zhì) 在各式各樣的圖中，有一類圖是極其簡(jiǎn)單然而卻是很有用的，這就是樹。例6-3 已

17、知有五個(gè)城市，要在它們之間架設(shè)電話線，要求任何兩個(gè)城市都可以互相通話(允許通過(guò)其它城市)，并且電話線的根數(shù)最少。 用五個(gè)點(diǎn) 代表五個(gè)城市，如果在某兩個(gè)城市之間架設(shè)電話線，則在相應(yīng)的兩個(gè)點(diǎn)之間聯(lián)一條邊，這樣一個(gè)電話線網(wǎng)就可以用一個(gè)圖來(lái)表示。為了使任何兩個(gè)城市都可以通話，這樣的圖必須是連通的。2022/10/11346.2 樹2022/10/1535 其次，若圖中有圈，從圈上去掉任意一條邊，剩下的圖仍然是連通的，這樣即可省去一條電話線。因此，滿足要求的電話網(wǎng)必須是：連通的；不含圈的。滿足這兩點(diǎn)要求的圖稱為“樹”。 定義6-9連通且不含圈的無(wú)向圖稱為樹。樹中次為1的頂點(diǎn)稱為樹葉(懸掛點(diǎn))，次大于1的

18、頂點(diǎn)稱為分枝點(diǎn)。2022/10/1135 其次，若圖中有圈，從圈上去掉2022/10/1536 下面介紹樹的一些重要性質(zhì)。樹的性質(zhì)可用下面定理給出。 定理 6-3 設(shè)圖 ，圖 的頂點(diǎn)數(shù)和邊數(shù)分別為 和 ，則下列命題是等價(jià)的：（1） 是一個(gè)樹。（2） 無(wú)圈，且 。（3） 連通，且 。（4） 無(wú)圈，但每加一條新邊即存在唯一一個(gè)圈。（5） 連通，但每舍去一條邊就變成不連通。（6） 中任意兩點(diǎn)，有唯一鏈相連。證明略。 定理 6-3中每一個(gè)命題均可作為樹的定義，對(duì)判斷和構(gòu)造樹極為方便。2022/10/1136 下面介紹樹的一些重要性質(zhì)。樹的性2022/10/1537 定義6-10圖 ，若 是 的子集，

19、是 的子集，且 中的邊僅與 中的頂點(diǎn)相關(guān)聯(lián)，則稱 是的 一個(gè)子圖。特別地，若 ，則 稱為 的生成子圖（或支撐子圖）。 定義6-11若圖 的生成子圖 是一棵樹，則稱 稱為 的生成樹，或簡(jiǎn)稱為圖 的樹。圖 中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。2022/10/1137 定義6-10圖 2022/10/1538 定理6-4 圖 有生成樹的充分必要條件為圖 是連通圖。 證明：必要性由定義顯然可得。 充分性的證明：設(shè)圖 是連通的。若 不含圈，則 就是其自身的一棵生成樹；若 含有圈，任取一個(gè)圈，從圈中任意去掉一條邊，得到圖 的一個(gè)生成子圖 。如果 不含圈，那么 是 的一棵生成樹；如果 仍含有圈

20、，那么從 中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖 的一個(gè)生成子圖 。如此重復(fù)，使每個(gè)圈都受到破壞，最后可以得到的一個(gè)不含圈的生成子圖 。 就是 的一棵生成樹。 上述充分性的證明，給出了一種尋求生成樹的方法，即任取一個(gè)圈，從圈中去掉一條邊，對(duì)余下的圖重復(fù)這個(gè)步驟，直到不含圈時(shí)為止，即得到一棵生成樹，稱這種方法為“破圈法”。 除“破圈法”外，還有另一種求連通圖 的生成樹的方法，稱為“避圈法”。這種方法是在圖 中，每步選取一條邊使它與已選邊不構(gòu)成圈，直到選夠 條邊為止。2022/10/1138 定理6-4 圖 有生成樹的充分必2022/10/15396.2.2圖的支撐樹（1）構(gòu)造支撐樹的算法1

21、)破圈法破圈法的思路：將連通有圈圖逐步刪除圈中的邊，直到不含圈，變成連通無(wú)圈圖。破圈法的步驟： 為連通圖， 是 的支撐子圖。步驟 1 取 步驟 2 若 不含圈，則 為支撐樹；若 含圈，取 中的任一圈，去掉圈上任一條邊，得 ， 。步驟 3 如果 ，則重復(fù)步驟 2；否則， 一定是支撐樹。2022/10/11396.2.2圖的支撐樹2022/10/1540例6-4 用破圈法求出圖6-14 的一個(gè)支撐樹。圖 6-14 破圈法求解支撐樹的過(guò)程圖2022/10/1140例6-4 用破圈法求出圖6-14 的2022/10/1541 2）避圈法避圈法的思路：將不連通的無(wú)圈圖通過(guò)邊的增加，逐步變成連通無(wú)圈圖。避

22、圈法的步驟： 為連通圖。步驟1 取步驟 2 若 連通，則 為支撐樹；若 不連通，任選圖 邊集 中的一邊 ，使 的兩個(gè)端點(diǎn)分屬兩個(gè)不同的連通分圖，得 ，步驟 3 若 ，則重復(fù)步驟 2；否則， 一定是支撐樹。2022/10/1141 2）避圈法2022/10/1542 3、圖的支撐樹 如果G1是G2的部分圖(支撐子圖)，又是樹，則稱G1是G2的部分樹（或支撐樹）。 一般圖G含有多個(gè)部分樹圖，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖 的最小支撐樹。 找最小支撐樹的易懂的方法有避圈法和破圈法 。2022/10/1142 3、圖的支撐樹2022/10/1543例6-5 用避圈法求出圖6-15的一個(gè)支撐樹。20

23、22/10/1143例6-5 用避圈法求出圖6-15的一2022/10/15446.2.3 最小支撐樹及其算法 將支撐樹的構(gòu)造與邊權(quán)的選擇相結(jié)合，將產(chǎn)生最小支撐樹的概念。最小支撐樹是網(wǎng)絡(luò)優(yōu)化中一個(gè)重要的概念，它在交通網(wǎng)、電話網(wǎng)、管道網(wǎng)、電力網(wǎng)等設(shè)計(jì)中均有廣泛的應(yīng)用。 定義6-12 設(shè)連通圖 的每一邊 有一個(gè)權(quán) ，如果 是 的一個(gè)支撐樹，稱 中所有邊的權(quán)之和為支撐樹 的權(quán)，記為 ： 如果支撐樹 的權(quán) 是 的所有支撐樹中權(quán)數(shù)最小的，則稱 是 的最小支撐樹（也稱最小樹），即 樹的各條邊稱為樹枝，一般圖包含有多個(gè)支撐樹，最小支撐樹是其中樹枝總長(zhǎng)最小的支撐樹。圖的最小支撐樹一般不唯一。2022/10/1

24、1446.2.3 最小支撐樹及其算法2022/10/1545（2）尋找最小支撐樹的算法 尋找最小支撐樹也可以利用上述介紹的破圈法和避圈法，但在刪除邊和增加邊時(shí)，需要考慮邊的權(quán)數(shù)的限制。 1）破圈法 步驟如下： 從圖 中任取一圈，去掉這個(gè)圈中權(quán)數(shù)最大的一條邊，得一支撐子圖 。在 中再任取一圈，再去掉圈中權(quán)數(shù)最大的一條邊，得 。如此繼續(xù)下去，一直到剩下的子圖中不再含圈為止。該子圖 就是的最小支撐樹 。2022/10/1145（2）尋找最小支撐樹的算法2022/10/15462）Kruskal算法 Kruskal算法是Kruskal于1956年提出的一個(gè)產(chǎn)生最小支撐樹的算法，類似于求生成樹的避圈法。

25、算法的基本思想是：每次從未選的邊中選取一條最小權(quán)的邊加入子圖T中，并保證它與已選邊不形成圈，直到選夠有 條邊為止。 Kruskal算法的基本步驟如下： 步驟1 按照權(quán)的大小對(duì)邊由小到大排序，即 令 步驟2 判斷 是否含圈。如含圈，轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟4. 步驟3 令 。若 ，轉(zhuǎn)步驟2；否則，結(jié)束，沒(méi)有支撐樹，G不聯(lián)通。 步驟4 令 。若 ，結(jié)束，T是最小樹；否則，轉(zhuǎn)步驟2。2022/10/11462）Kruskal算法2022/10/1547例6-6 下圖6-16中、代表村鎮(zhèn)，它們的連線代表各村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁的數(shù)字代表道路長(zhǎng)度?，F(xiàn)要求沿圖中道路鋪設(shè)光纖，使上述村鎮(zhèn)全部通上網(wǎng)絡(luò)，

26、應(yīng)如何架設(shè)，才能使總的線路長(zhǎng)度最短？2022/10/1147例6-6 下圖6-16中、2022/10/1548 解：這個(gè)問(wèn)題就是求圖中所示網(wǎng)絡(luò)的最小樹，用Kruskal算法求解。通過(guò)對(duì)邊由小到大排序，按照避圈法的原則，逐步增加到T中。2022/10/1148 解：這個(gè)問(wèn)題就是求圖中所示網(wǎng)絡(luò)的2022/10/15492022/10/11492022/10/15506.3 最短路問(wèn)題 最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問(wèn)題之一。很多優(yōu)化問(wèn)題可使用這個(gè)模型，比如設(shè)備的更新、管道的鋪設(shè)、線路的安排、廠區(qū)的布局等。在上一章中我們?cè)榻B過(guò)最短路問(wèn)題的動(dòng)態(tài)規(guī)劃解法，但有些最短路問(wèn)題（如道路不能整齊分段的）構(gòu)

27、造動(dòng)態(tài)規(guī)劃方程比較困難，而使用圖論方法則比較有效。 最短路問(wèn)題的一般提法是設(shè) 為網(wǎng)絡(luò)圖，圖中各邊 有權(quán) （ =表示 ， 之間沒(méi)有邊）， ， 為圖中任意兩點(diǎn)。網(wǎng)絡(luò)中有多條 的路,最短路問(wèn)題是求一條從 到 的所有路中總權(quán)最小的路。即：優(yōu)化問(wèn)題 下面我們將介紹三種求解最短路問(wèn)題的算法。2022/10/11506.3 最短路問(wèn)題2022/10/15516.3.1 Dijkstra算法 E.W.Dijkstra 于1959年提出了本算法，可用于求解正權(quán)網(wǎng)絡(luò)最短路徑。用給節(jié)點(diǎn)記標(biāo)號(hào)來(lái)逐步形成起點(diǎn)到各點(diǎn)的最短路徑及其距離值，被認(rèn)為是目前求解無(wú)賦權(quán)網(wǎng)絡(luò)的最好算法。 Dijkstra 算法也稱為雙標(biāo)號(hào)法，也就是

28、對(duì)圖中的每個(gè)點(diǎn) 賦予T標(biāo)號(hào)和P標(biāo)號(hào)兩個(gè)標(biāo)號(hào)。T標(biāo)號(hào)為臨時(shí)標(biāo)號(hào)，P標(biāo)號(hào)為永久標(biāo)號(hào)。給 一個(gè)P標(biāo)號(hào)時(shí)，表示從 到 的最短路權(quán)， 的標(biāo)號(hào)不變。給 一個(gè)T標(biāo)號(hào)時(shí)，表示從 到 的最短路權(quán)的上界，是臨時(shí)標(biāo)號(hào)，凡沒(méi)有得到P標(biāo)號(hào)的點(diǎn)都有T標(biāo)號(hào)。算法的每一步都把某一點(diǎn)的T標(biāo)號(hào)修改為P標(biāo)號(hào)，直到所有點(diǎn)都得到P標(biāo)號(hào)結(jié)束。對(duì)于有n個(gè)點(diǎn)的圖，最多經(jīng)過(guò)n-1步就可以得到從始點(diǎn)到終點(diǎn)的最短路。2022/10/11516.3.1 Dijkstra算法2022/10/1552Dijkstra 算法的基本步驟如下：（1）給起點(diǎn) 以P標(biāo)號(hào)， ，其余各點(diǎn)均給T標(biāo)號(hào)，（2）若節(jié)點(diǎn) 是剛得到P標(biāo)號(hào)的點(diǎn)。把 與有弧(邊)直接相連而且有屬于

29、T標(biāo)號(hào)的節(jié)點(diǎn)，改為下列T標(biāo)號(hào)：（3）將值最小的T標(biāo)號(hào)改為P標(biāo)號(hào)，直至終點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)為止；否則轉(zhuǎn)(2)。注意：當(dāng)同時(shí)存在兩個(gè)及以上的最小T標(biāo)號(hào)時(shí)，可同時(shí)改為P標(biāo)號(hào)。2022/10/1152Dijkstra 算法的基本步驟如下2022/10/1553例6-7 用Dijkstra算法求下圖中到的最短路。圖6-18 求最短路徑圖2022/10/1153例6-7 用Dijkstra算法求下2022/10/1554解：（1）考察以P標(biāo)號(hào)點(diǎn)v1為始點(diǎn)的弧v1v2，v1 v3，v1 v4。因?yàn)関2, v3 ,v4均為T標(biāo)號(hào)，所以修正這三點(diǎn)的T標(biāo)號(hào)如下：T(v2)=minT(v2)，P(v1)+d 12

30、=min，0+8=8T(v3)=minT(v3)，P(v1)+d 13=min，0+6=6T(v4)=minT(v4)，P(v1)+d 14=min，0+2=2在所有的T標(biāo)號(hào)中，T(v4)2最小，令P(v4)=2。這說(shuō)明從v1到v4的最短路是2。如圖6-19所示。圖 6-19 最短路徑標(biāo)號(hào)過(guò)程圖2022/10/1154解：（1）考察以P標(biāo)號(hào)點(diǎn)v1為始點(diǎn)的2022/10/1555（2）考察以新的P標(biāo)號(hào)點(diǎn)v4為始點(diǎn)的所有弧v4v3，v4v6。因?yàn)関3，v6均為T標(biāo)號(hào)，所以修正這兩點(diǎn)的T標(biāo)號(hào)如下：T(v3)=minT(v3)，P(v4)+d43=min6，23=5T(v6)=minT(v6)，P(v

31、4)+d46=min，2+2=4在所有的T標(biāo)號(hào)中，T(v6)4最小，令P(v6)=4。這說(shuō)明從v1到v6的最短路是4。如圖6-20所示。圖 6-20 最短路徑標(biāo)號(hào)修正過(guò)程圖2022/10/1155（2）考察以新的P標(biāo)號(hào)點(diǎn)v4為始點(diǎn)的2022/10/1556（3）考察以新的P標(biāo)號(hào)點(diǎn)v6為始點(diǎn)的所有弧v6v5，v6v7。因?yàn)関5，v7均為T標(biāo)號(hào)，所以修正這兩點(diǎn)的T標(biāo)號(hào)如下。T(v5)=minT(v5)，P(v6)+d 65=min，43=7T(v7)=minT(v7)，P(v6)+d 67=min，4+9=13在所有的T標(biāo)號(hào)中，T(v3)5最小，令P(v3)=5。這說(shuō)明從v1到v3的最短路是5。如

32、圖6-21所示。圖 6-21 最短路徑標(biāo)號(hào)修正過(guò)程圖2022/10/1156（3）考察以新的P標(biāo)號(hào)點(diǎn)v6為始點(diǎn)的2022/10/1557（4）考察以新的P標(biāo)號(hào)點(diǎn)v5為始點(diǎn)的所有弧v5v7。因?yàn)関7為T標(biāo)號(hào)，所以修正該點(diǎn)的T標(biāo)號(hào)如下。T(v7)=minT(v7)，P(v5)+d 57=min13，7+5=12因只有一個(gè)T標(biāo)號(hào)，令P(v7)=12，計(jì)算結(jié)束。v1到v7的最短路為v1v4v6v5v7，路長(zhǎng)為12。同時(shí)得到v1到其余各點(diǎn)的最短路。需要注意的是，Dijkstra 算法只適用于權(quán)值為正實(shí)數(shù)的情況，如果權(quán)值有負(fù)的，算法失效。前面的算法都是求點(diǎn)到點(diǎn)之間的最短路。2022/10/1157（4）考

33、察以新的P標(biāo)號(hào)點(diǎn)v5為始點(diǎn)的2022/10/15586.3.2 Ford 算法Dijkstra算法不適用于負(fù)權(quán)網(wǎng)絡(luò)。具有負(fù)權(quán)的網(wǎng)絡(luò)，可以用Ford算法又叫修正標(biāo)號(hào)法。修正標(biāo)號(hào)法的特點(diǎn)是，不但最小T標(biāo)號(hào)應(yīng)當(dāng)改為P標(biāo)號(hào)，P標(biāo)號(hào)也可以修改，修改后的P標(biāo)號(hào)同時(shí)改為T標(biāo)號(hào)。Ford 算法的基本步驟如下：（1）給起點(diǎn) 以P標(biāo)號(hào)， ；其他點(diǎn)的標(biāo)號(hào)為T標(biāo)號(hào)， 。（2）若節(jié)點(diǎn) 是剛得到P標(biāo)號(hào)的點(diǎn)。檢查與 相連的每個(gè)點(diǎn) ，看是否存在 或 ，若不存在，則保留原標(biāo)號(hào)，否則轉(zhuǎn)向（3）。（3）將點(diǎn)的T或P標(biāo)號(hào)改為新的T標(biāo)號(hào) 或者 。算法直到所有的頂點(diǎn)都是P標(biāo)號(hào)結(jié)束。2022/10/11586.3.2 Ford 算法202

34、2/10/1559例6-8 用Ford算法求下圖中到其余各點(diǎn)的最短路。 圖 6-22 有負(fù)權(quán)值網(wǎng)絡(luò)圖2022/10/1159例6-8 用Ford算法求下圖中到其2022/10/1560解：（1）考察以P標(biāo)號(hào)點(diǎn)vs為始點(diǎn)的弧vsv1，vsv2。修正這兩點(diǎn)的T標(biāo)號(hào)如下：T(v1)=minT(v1)，P(vs)+ds2=min，0+5=5T(v2)=minT(v3)，P(v1)+ds3=min，0+8=8在所有的T標(biāo)號(hào)中，T(v1)5最小，令P(v1)=5。（2）考察以P標(biāo)號(hào)點(diǎn)v1為始點(diǎn)的弧v1v3，v1v2。修正這兩點(diǎn)的T標(biāo)號(hào)如下：T(v3)=minT(v3)，P(v1)+d13=min，5+9=

35、14T(v2)=minT(v2)，P(v1)+d12=min8，5+8=8在所有的T標(biāo)號(hào)中，T(v2)8最小，令P(v2)=8。（3）考察以P標(biāo)號(hào)點(diǎn)v2為始點(diǎn)的弧v2v3，v2v4。修正這兩點(diǎn)的T標(biāo)號(hào)，T(v3) =14，T(v4) =16。因T(v3) =14最小，令P(v3)=14。（4）考察以P標(biāo)號(hào)點(diǎn)v3為始點(diǎn)的弧v3vt，T(vt) =18。因T(v4)=16最小，令P(v4)=16。（5）考察以P標(biāo)號(hào)點(diǎn)v4為始點(diǎn)的弧v4v3，v4vt，修正這兩點(diǎn)的T標(biāo)號(hào)如下：T(v3)=minP(v3)，P(v4)+d43=min14，16-5=11T(vt)=minT(vt)，P(v4)+d4t=

36、min18，16+5=18因T(v3) =11最小，令P(v3)=11。2022/10/1160解：（1）考察以P標(biāo)號(hào)點(diǎn)vs為始點(diǎn)的2022/10/1561（6）考察以P標(biāo)號(hào)點(diǎn)v3為始點(diǎn)的弧v3vt，T(vt) =15。因T(vt)=15最小，令P(vt)=15。全部計(jì)算結(jié)果見(jiàn)圖6-23，最短路長(zhǎng)為15。圖 6-23 最短路徑求解結(jié)果圖2022/10/1161（6）考察以P標(biāo)號(hào)點(diǎn)v3為始點(diǎn)的弧v2022/10/15626.3.3 Floyd-Darshall算法Floyd-Darshall算法是求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路的算法，這個(gè)算法的基本思想就是標(biāo)號(hào)修正。為計(jì)算方便，令網(wǎng)絡(luò)的權(quán)矩陣為 ，

37、為 到 的距離。FloydDarshall算法用標(biāo)號(hào)修正算法表示如下：2022/10/11626.3.3 Floyd-Darsha2022/10/1563 在FloydDarshall算法中， 是第 次迭代得到的 到 的臨時(shí)性標(biāo)號(hào)， 是在 到 的路中邊數(shù)不超過(guò) 條的路中最短路的長(zhǎng)度，是最短路長(zhǎng)度的近似。這個(gè)算法在迭代 次后，若各頂點(diǎn)對(duì)之間存在最短路，即是 到 的最短路長(zhǎng)度，臨時(shí)性標(biāo)號(hào)變成永久性標(biāo)號(hào)。如果 還沒(méi)有收斂，即存在兩個(gè)頂點(diǎn) 和 ，使得 ，這說(shuō)明網(wǎng)絡(luò)中存在負(fù)圈。 FloydDarshall算法可通過(guò)矩陣的迭代實(shí)現(xiàn)。每次標(biāo)號(hào)的修正都是一個(gè)距離矩陣的迭代和更新。2022/10/1163 在F

38、loydDarshall算2022/10/1564例6-9 求如圖6-24所示的網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路?；∨缘臄?shù)字表示弧的長(zhǎng)度。2022/10/1164例6-9 求如圖6-24所示的網(wǎng)絡(luò)中2022/10/1565解 用 表示各頂點(diǎn)對(duì)之間通過(guò)不超過(guò) 條弧所能夠到達(dá)的最短路的長(zhǎng)度矩陣，則計(jì)算結(jié)果如下：首先給出通過(guò)不超過(guò)1條弧即可到達(dá)的長(zhǎng)度矩陣v1到v2不超過(guò)2條弧即可到達(dá)的長(zhǎng)度v1到v3不超過(guò)2條弧即可到達(dá)的長(zhǎng)度v1到v4不超過(guò)2條弧即可到達(dá)的長(zhǎng)度 ；其他同樣計(jì)算。得到各頂點(diǎn)對(duì)之間通過(guò)不超過(guò)2條弧所能夠到達(dá)的最短路的長(zhǎng)度矩陣：2022/10/1165解 用 表示各頂點(diǎn)對(duì)之間通過(guò)不2022/10/

39、1566各頂點(diǎn)對(duì)之間通過(guò)不超過(guò)條弧所能夠到達(dá)的最短路的長(zhǎng)度矩陣如下：我們看到 ，則 中的長(zhǎng)度就是最短路長(zhǎng)度。2022/10/1166各頂點(diǎn)對(duì)之間通過(guò)不超過(guò)條弧所能夠到達(dá)2022/10/15676.4 最大流問(wèn)題 最大流問(wèn)題是一類應(yīng)用極為廣泛的問(wèn)題，許多系統(tǒng)中包含著流量，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；通信系統(tǒng)中有信息流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流等等。 例如，要把一批貨物從起點(diǎn) 通過(guò)鐵路網(wǎng)絡(luò)運(yùn)到終點(diǎn) ，把鐵路網(wǎng)上的車站看作頂點(diǎn)，兩車站間的鐵路線看作弧，每條鐵路線上運(yùn)送的貨物總量是有限的，我們把某線路上的最大可能運(yùn)送量稱為它的容量。如何安排運(yùn)輸方案，使得從起點(diǎn) 運(yùn)到終點(diǎn) 的總

40、運(yùn)量達(dá)到最大，而且每條弧上通過(guò)的貨物總量不超過(guò)這條弧的容量？2022/10/11676.4 最大流問(wèn)題2022/10/1568 上面這個(gè)問(wèn)題就是求鐵路網(wǎng)絡(luò)的最大流問(wèn)題。這里的“流”，是指鐵路線（?。┥系膶?shí)際運(yùn)輸量。圖6-25所示網(wǎng)絡(luò)中，每條弧旁的數(shù)字即為該弧的容量 ，弧的方向就是允許流的方向。圖6-25 鐵路網(wǎng)絡(luò)圖2022/10/1168 上面這個(gè)問(wèn)題就是求鐵路網(wǎng)絡(luò)的最大2022/10/15696.4.1基本概念與定理（1）容量網(wǎng)絡(luò)與流在研究網(wǎng)絡(luò)流問(wèn)題時(shí)，首先應(yīng)給出各弧的通過(guò)能力，如圖6-26所示各弧的權(quán)數(shù)表示弧的容量，記為 ，把標(biāo)有弧容量 的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)，記為 。一般地，對(duì)于一個(gè)容量網(wǎng)絡(luò)

41、 ，如果點(diǎn)集 中有一發(fā)點(diǎn)，記為 ，還有一收點(diǎn)，記為 ，其余均為中間點(diǎn)，且對(duì)弧集 的每條弧均賦權(quán) ，則稱這樣的容量網(wǎng)絡(luò) 為帶收發(fā)點(diǎn)的容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)。在 中，由于各弧容量的配置可能不協(xié)調(diào)，實(shí)際通過(guò)各弧的流量，記為 ，不可能處處都達(dá)到容量值 。把通過(guò)弧的運(yùn)量 稱為通過(guò)弧 的流量，所有弧上流量的集 稱為該網(wǎng)絡(luò) 的一個(gè)流。2022/10/11696.4.1基本概念與定理2022/10/1570 圖6-26中 為發(fā)點(diǎn)， 為收點(diǎn)， 為中間點(diǎn)?；∨岳ㄌ?hào)中的兩個(gè)數(shù)字 ，第一個(gè)數(shù)字 表示弧容量，第二個(gè)數(shù)字 表示通過(guò)該弧的流量，如弧 上的(5,1)，前者是可通過(guò)該弧的最大流量為 5，后者是目前通過(guò)該弧的流量為

42、1。圖6-26 某一容量、流量網(wǎng)絡(luò)圖2022/10/1170 圖6-26中 為發(fā)點(diǎn)， 為收點(diǎn)2022/10/1571（2）可行流與最大流 網(wǎng)絡(luò)流是實(shí)際能通過(guò)給定容量網(wǎng)絡(luò)的流量集合，它必然滿足以下兩個(gè)約束條件：容量約束和節(jié)點(diǎn)流量平衡條件。以上圖6-26為例，這兩個(gè)條件可用以下公式表達(dá)： 1)容量約束條件： ，即對(duì)每一條弧 的流量 應(yīng)小于等于弧 的容量 ，并大于等于零。例如， 2) 節(jié)點(diǎn)流量平衡條件： 網(wǎng)絡(luò)中的流量必須滿足守恒條件，對(duì)收發(fā)點(diǎn)來(lái)說(shuō)，發(fā)點(diǎn)的總流出量=收點(diǎn)的總流入量；對(duì)中間點(diǎn) 來(lái)說(shuō)，中間點(diǎn)的總流入量=總流出量。例如， 對(duì)一個(gè)給定的容量網(wǎng)絡(luò)，凡是滿足以上兩個(gè)條件的網(wǎng)絡(luò)流 都稱為可行流。顯然

43、，上圖6-26的網(wǎng)絡(luò)流為可行流。 2022/10/1171（2）可行流與最大流2022/10/1572 尋求網(wǎng)絡(luò)最大流就是找到一個(gè)可行流 ，使得網(wǎng)絡(luò)發(fā)點(diǎn)到收點(diǎn)的總流量 達(dá)到最大。網(wǎng)絡(luò)最大流問(wèn)題的線性規(guī)劃表達(dá)式為： 顯然，網(wǎng)絡(luò)最大流問(wèn)題是一個(gè)典型而又特殊的線性規(guī)劃問(wèn)題，一個(gè)可行流相當(dāng)于線性規(guī)劃中的一個(gè)可行解，而尋求最大流就相當(dāng)于求網(wǎng)絡(luò)容量的最優(yōu)解，自然可用介紹過(guò)的單純形法進(jìn)行求解。但利用單純形方法得到網(wǎng)絡(luò)最大流問(wèn)題的解，計(jì)算量過(guò)大。由于這一問(wèn)題的特殊性，用網(wǎng)絡(luò)模型方法求解，更方便、直觀。2022/10/1172 尋求網(wǎng)絡(luò)最大流就是找到一個(gè)可2022/10/1573（3）增廣鏈設(shè)網(wǎng)絡(luò) 中，有一可行

44、流 ，按每條弧上流量的多少，可將弧分為飽和弧、非飽和弧、零流弧、非零流弧4 種類型。飽和弧非飽和弧零流弧非零流弧在上圖6-26中， 是飽和弧，也是非零流弧， 是零流弧，其他各弧均為非飽和弧，也是非零流弧。2022/10/1173（3）增廣鏈2022/10/1574 若 是網(wǎng)絡(luò) 中從 到 的一條鏈，沿此方向 上的各弧可分為兩類，一類是與鏈的方向一致的弧，稱為前向弧，前向弧的全體記為 ；另一類是與鏈的方向相反的弧，稱為后向弧，后向弧的全體記為 。如圖6-26所示，在鏈 中， 對(duì)于可行流 ， 是一條從 到 的鏈，如果 中的每條弧均為非飽和弧，且 中的每條弧均為非零流弧，則稱鏈 是關(guān)于 的增廣鏈。上述

45、條件也可用其反義來(lái)表達(dá)：正向飽和弧和反向零流弧都不是增廣鏈。如圖6-26中 就是一條增廣鏈，而卻不是增廣鏈。不難理解，如果 是一條增廣鏈，那么在 上可以增加一定的流量，從而增加可行流的流值。2022/10/1174 若 是網(wǎng)絡(luò) 中從 2022/10/1575 圖6-26中這條增廣鏈（加粗線所示）可以沿正向弧增加流量，即增廣鏈上存在增大輸送能力的潛力，相應(yīng)的，逆向弧上減小流量，以保持中間節(jié)點(diǎn)的流量平衡。例如，對(duì)所有前向弧增加流量1個(gè)單位；對(duì)所有后向弧減少流量1個(gè)單位，也就是說(shuō)，沿增廣鏈方向調(diào)整1個(gè)單位流量，變成新流 ， ， ， ，則上圖的新網(wǎng)絡(luò)流仍是可行流，但總流量 增加了1個(gè)單位。增廣鏈的這個(gè)

46、性質(zhì)提示我們，可以利用增廣鏈來(lái)調(diào)整當(dāng)前流，以求最大流。若可行流 不存在增廣鏈，那么它就不能再調(diào)整增大，就可斷定它就是最大流。 增廣鏈起的作用有兩個(gè)，一是目前的可行流是否是最大流？如果不是最大流，如何通過(guò)增廣鏈找到更大的可行流？增廣鏈起的作用與線性規(guī)劃中檢驗(yàn)數(shù)起的作用相同。2022/10/1175 圖6-26中這條增廣鏈（加粗2022/10/1576（4）截集和截量 一個(gè)容量網(wǎng)絡(luò)，由于各弧容量配置得不合適，有的地方能通過(guò)較大流量，有的地方能通過(guò)的流量卻較小。小的地方就限制了最大流的上限值，成為網(wǎng)絡(luò)流的“瓶頸”。因此，研究從起點(diǎn)到終點(diǎn)的流徑中，哪些弧容量起了限制最大流作用，就具有實(shí)際意義。截集就是

47、研究網(wǎng)絡(luò)流“瓶頸”的一種工具。2022/10/1176（4）截集和截量2022/10/1577 從直觀上說(shuō)，截集的所有弧是到的必經(jīng)之路，若把截集從網(wǎng)絡(luò)中去掉，則從到就不存在路了，自然也就沒(méi)有流量了。圖6-27 某一容量、流量網(wǎng)絡(luò)圖2022/10/1177 從直觀上說(shuō)，截集的所有弧是到2022/10/15782022/10/11782022/10/1579 定理6-5 可行流 是最大流的充分必要條件是網(wǎng)絡(luò)中不存在關(guān)于 的增廣鏈。 證明若可行流 是最大流，則顯然網(wǎng)絡(luò)中不存在 到 的增廣鏈。否則，若有增廣鏈，則增廣鏈上的前向弧增加流量，后向弧減小流量，則新可行流的流值增加了，找到了一個(gè)流值更大的可行

48、流，矛盾。 定義頂點(diǎn)集合 。因?yàn)榫W(wǎng)絡(luò)中不存在 到 的增廣鏈，則有 ，因此 形成一個(gè)截集。 ，則有 ，否則，若 ，則 可以延伸到頂點(diǎn) ，這與 矛盾。 ，則有 ，否則，若 ，則 可以通過(guò)逆向狐延伸到頂點(diǎn) ，這與 矛盾。2022/10/1179 定理6-5 可行流 是最2022/10/1580 最大流最小截集定理：任一容量網(wǎng)絡(luò) 中，最大流的流量等于最小截集的截量。 利用截集的截量來(lái)判斷一個(gè)容量網(wǎng)絡(luò)的最大流通過(guò)能力是一種截集枚舉法。在復(fù)雜、大型網(wǎng)絡(luò)中它不是一種簡(jiǎn)便的方法。實(shí)際上我們是通過(guò)另外一種途徑即用最大流標(biāo)號(hào)法求最大流，速度更快，可靠性更大。當(dāng)發(fā)現(xiàn)當(dāng)前流圖是最大流時(shí)，同時(shí)也就發(fā)現(xiàn)了最小截集。其思想

49、是通過(guò)最大流找最小截集，而不是通過(guò)最小截集找最大流。 從以上增廣鏈和截集的概念及定理知道，要判斷一個(gè)可行流 是否為最大流，有兩種途徑： 一是能否找出 到 的增廣鏈，若能，則說(shuō)明 不是最大流；否則 就是最大流。 二是看 是否等于最小截量。若相等，則 是最大流，否則不是最大流。在上述概念和定理的基礎(chǔ)上，下面介紹尋求最大流的 Ford-Fulkerson標(biāo)號(hào)算法。2022/10/1180 最大流最小截集定理：任一容量2022/10/15812022/10/11812022/10/15822022/10/11822022/10/1583例10 試用 FordFulkerson標(biāo)號(hào)法求圖6-28所示的網(wǎng)

50、絡(luò)最大流，括號(hào)中第一個(gè)數(shù)字是容量，第二個(gè)數(shù)字是流量。圖6-28 某一網(wǎng)絡(luò)圖2022/10/1183例10 試用 FordFulker2022/10/1584解第一步：標(biāo)號(hào)過(guò)程。首先給 標(biāo)以(0，+ )。檢查點(diǎn) ：弧 ，為飽和弧，所以對(duì) 不標(biāo)號(hào)?；?，為非飽和弧，所以給點(diǎn) 標(biāo)號(hào)， 。其中檢查點(diǎn) ：弧 ， ，為飽和弧，所以對(duì) 不標(biāo)號(hào)?；?， ，為非零流弧，所以給標(biāo)號(hào) ， ，其中2022/10/1184解第一步：標(biāo)號(hào)過(guò)程。2022/10/1585檢查點(diǎn) ：弧 ， ，為非飽和弧，所以給點(diǎn) 標(biāo)號(hào)， ，其中弧 ， ，為非零流弧，所以給 標(biāo)號(hào)， ，其中檢查點(diǎn) ：弧 ， ，為非飽和弧，所以給點(diǎn) 標(biāo)號(hào)， ，其中

51、由于 已標(biāo)號(hào)，不需再檢查 。2022/10/1185檢查點(diǎn) ：2022/10/1586第二步：調(diào)整過(guò)程利用各點(diǎn)已標(biāo)號(hào)的第一個(gè)分量，從 反向追蹤得增廣鏈 ，如圖中粗箭頭線所示，其中 ， 。由 標(biāo)號(hào)的第二個(gè)分量知 ，于是在 上進(jìn)行調(diào)整：2022/10/1186第二步：調(diào)整過(guò)程2022/10/1587 調(diào)整后的可行流如圖6-29所示。對(duì)這個(gè)新的可行流重新在圖中進(jìn)行標(biāo)號(hào)，尋找新的增廣鏈。圖6-29 增廣后的新可行流2022/10/1187 調(diào)整后的可行流如圖6-29所示。2022/10/1588第三步：再標(biāo)號(hào) 同上述第一步標(biāo)號(hào)，易見(jiàn)，當(dāng)給 標(biāo)號(hào) 后，無(wú)法再進(jìn)行下去。因此，目前所得到的可行流就是最大流，

52、最小截集 最大流量為 從上例可以看出，最小截集中各弧的容量總和構(gòu)成最大流問(wèn)題的瓶頸，在實(shí)際問(wèn)題中，為提高網(wǎng)絡(luò)中的總流量，必須首先著力改善最小截集中各弧的弧容量。2022/10/1188第三步：再標(biāo)號(hào)2022/10/15896.5 最小費(fèi)用最大流 在上節(jié)最大流問(wèn)題中，每一個(gè)可行流在現(xiàn)實(shí)生活中，還對(duì)應(yīng)著一定的費(fèi)用，許多情況下優(yōu)化目標(biāo)不但要求流量盡可能的大，還要求費(fèi)用盡可能的小。在一個(gè)網(wǎng)絡(luò)中每條弧在“容量”和“費(fèi)用”兩個(gè)限制條件下，尋求 到 的最大流，使該最大流在所有最大流中費(fèi)用達(dá)到最小。 給出網(wǎng)絡(luò) ，其中C是容量，B是費(fèi)用，即對(duì)于每條弧 ，有容量 ，有費(fèi)用 。對(duì)于D的一個(gè)可行流 ，定義其費(fèi)用為 下

53、面我們介紹求解最小費(fèi)用最大流問(wèn)題的方法，其基本思想是在尋求最大流的算法過(guò)程中，不但通過(guò)增廣鏈?zhǔn)沽髁恐鸩皆黾?，還要考慮費(fèi)用的約束，即每次可行流的調(diào)整都使費(fèi)用增加最小。2022/10/11896.5 最小費(fèi)用最大流2022/10/1590 尋求最大流的方法是從一個(gè)可行流出發(fā)，找出增廣鏈，通過(guò)增廣鏈上弧的流量的調(diào)整，使流值不斷增加，如此循環(huán)進(jìn)行，一直到找不出增廣鏈，從而得到最大流。在最大流增加的過(guò)程中，流的費(fèi)用也會(huì)變化，前向弧上增加流量，從而增加費(fèi)用；后向弧上減小流量，從而減小費(fèi)用。 當(dāng)沿著可行流 的一條的增廣鏈 ，以 調(diào)整 ，得到新的可行流 時(shí)， 比 增加：上式是流值 增加時(shí)，費(fèi)用的增加量。1時(shí)，

54、費(fèi)用的增加量是 ，這個(gè)數(shù)值反映了增廣鏈的好壞，這個(gè)數(shù)值越小，這條增廣鏈就越好。我們把 稱為增廣鏈的費(fèi)用。2022/10/1190 尋求最大流的方法是從一個(gè)可行流出2022/10/1591 若 是流值為 的所有可行流中費(fèi)用最小者，而 是關(guān)于 的費(fèi)用最小的增廣鏈，那么沿 去調(diào)整可行流 ，得到可行流 ，新可行流就是流值為 的所有可行流中費(fèi)用最小的可行流。 上述分析尋求到一種尋找最小費(fèi)用最大流的方法，即確定一個(gè)最小費(fèi)用可行流，然后找出最小費(fèi)用增廣鏈，按照最小費(fèi)用增廣鏈調(diào)整可行流，直到找不出增廣鏈為止，這樣得到的可行流即為最小費(fèi)用最大流。由于 ，故零流（ 0）是流值為0的可行流中的費(fèi)用最小者，因此零流總

55、可以作為我們的初始點(diǎn)。剩下的任務(wù)是尋找最小費(fèi)用增廣鏈。如何尋找最小費(fèi)用增廣鏈呢？2022/10/1191 若 是流值為 2022/10/1592 為了尋找最小費(fèi)用增廣鏈，我們以原可行流 為基礎(chǔ)，構(gòu)造一個(gè)新賦權(quán)圖 。 的頂點(diǎn)為原網(wǎng)絡(luò)D的頂點(diǎn) ，把D中的每條弧 變?yōu)閮蓷l方向相反的兩條弧 ，形成弧集合 ?；〉馁x權(quán)原則如下： 對(duì)于弧 ，有 對(duì)于弧 ，有 當(dāng)然，長(zhǎng)度為+的弧可以略去。 顯然原網(wǎng)絡(luò)中的增廣鏈對(duì)應(yīng)于 中的路；原網(wǎng)絡(luò)中的最小費(fèi)用增廣鏈對(duì)應(yīng)于 中的 最短路。這樣最小費(fèi)用增廣鏈的尋找即變成了 中最短路問(wèn)題的尋找，而最短路問(wèn)題我們已經(jīng)給出了算法，因此最小費(fèi)用增廣鏈問(wèn)題即已解決。2022/10/119

56、2 為了尋找最小費(fèi)用增廣鏈，我們以原2022/10/1593由以上討論可得出求最小費(fèi)用最大流的算法：（1）取零流為初始最小費(fèi)用可行流，記為 。（2）若第k步得到最小費(fèi)用可行流 , 則構(gòu)造一個(gè)新賦權(quán)圖D( ) ,在D( )中尋求從 最短路。若不存在最短路，則目前的可行流F(k)即為網(wǎng)絡(luò)D的最小費(fèi)用最大流；若存在最短路，則在原網(wǎng)絡(luò)D中得到了相應(yīng)的最小費(fèi)用增廣鏈 ，對(duì)F(k)進(jìn)行調(diào)整，調(diào)整量為（3）調(diào)整方法如下：重復(fù)進(jìn)行上述步驟，直到找不出增廣鏈為止。2022/10/1193由以上討論可得出求最小費(fèi)用最大流的算2022/10/1594例11 求圖6-30的最小費(fèi)用最大流，弧旁的數(shù)字為2022/10/

57、1194例11 求圖6-30的最小費(fèi)用最大流2022/10/1595解（1）取f(0)=0為初始可行流。弧旁的數(shù)字為 如圖6-31。2022/10/1195解（1）取f(0)=0為初始可行流。2022/10/1596 在零流中，每條弧只能做前向弧，因此新賦權(quán)網(wǎng)絡(luò) 見(jiàn)圖6-32。 中最短路見(jiàn)圖6-32中的粗線所示，由此找到最小費(fèi)用增廣鏈，見(jiàn)圖6-31中粗線所示。 利用最小費(fèi)用增廣鏈對(duì)可行流進(jìn)行調(diào)整，調(diào)整后的新流見(jiàn)圖6-33。2022/10/1196 在零流中，每條弧只能做前向弧2022/10/1597（2）繼續(xù)進(jìn)行可行流的調(diào)整： 在圖6-33中 只能作為后向??； 既可以作為前向弧也可以作為后向弧，其他弧只能做前向弧。 2022/10/1197（2）繼續(xù)進(jìn)行可行流的調(diào)整：2022/10/1598 因此，新賦權(quán)網(wǎng)絡(luò)見(jiàn)圖6-34所示： 圖6-34中的最短路見(jiàn)粗線所示，因此找到最小費(fèi)用增廣鏈，見(jiàn)圖6-33中粗線所示。 利用最小費(fèi)用增廣鏈對(duì)可行流進(jìn)行調(diào)整，調(diào)整后的新流見(jiàn)圖6-35。2022/10/1198 因此，新賦權(quán)網(wǎng)絡(luò)見(jiàn)圖6-342022/10/1599（3）繼續(xù)進(jìn)行可行流的調(diào)整：2022/10/1199（3）繼續(xù)進(jìn)行可行流的調(diào)整：2022/10/15100 以圖6-35中的可行流為基礎(chǔ)，得到新賦權(quán)網(wǎng)絡(luò)，見(jiàn)圖6-36。 上圖已經(jīng)找不出 的路，因此也沒(méi)增廣鏈了，即圖6-35所示的可行