【天津大學】《運籌學》(精品課) P37 - 36. 網絡最大流問題 教學錄像(3)

长安书院_
146粉絲
2026年11月21日
AI 生成·可能包含錯誤
今天我們繼續來學習網絡分析的最大流問題
那麼在前一次的課程中
我們給出了最大流求解的標號算法
那麼這種方法
它的基本思想就是在網絡圖中
尋找是否存在陣亡鏈
具體的來說
就從起點開始標號
尋找看看流出去的有沒有未飽和的湖
流入的有沒有非零的湖
如果從起點開始標
標到終點
我們就可以說尋找到了一條陣亡鏈
那麼當前的可行流就不是最大流
需要沿着陣亡鏈進行調整
那麼重新標號
直到不存在陣亡鏈
這時候我們就可以說流就是最大流了
下面我們一起來看一道練習題
那麼這是書上129頁的習題5.5
這是一個網絡圖
圖中有六個節點
每一條湖上標了些數字
其中外邊的數字是相應的容量
而括號裏邊是這條湖上的流量
有一些括號裏邊數字並沒有給出
我們看具體的問題
考慮如上圖所示的網絡最大流問題
其中湖上的數字是容量
括號內的數字爲流量
有這麼三問
第一問
要求在括號內填上適當的數字
使其構成一個可行流
第二問
若像這樣的表格中選擇點擊V1和V2
那麼要求填出相應的階級和階量
第三
那麼我們要求用標號的方法求出最大流和最小階級
那麼我們把這個圖形再來給出來
請同學們來思考一下這個問題
第一問呢
就是如何在括號裏邊標上一些數字
使得形成一個可行流
好我們一塊來分析一下
第一問
填上初始的一個可行流
根據可行流的定義呢
我們知道
這個流量要滿足兩種條件
第一個流量要小於或者等於容量
第二條呢
對於每一箇中間節點來說
這個流量要保持平衡
換句話說
就是每一箇中間節點來說
流入這個節點的流量之和
應該等於流出流量之和
所以我們逐個節點來分析
看二號節點
流入二號節點的流量
只有一條湖
那就是這個湖上的流量六
所以流出也應該是六
那麼我首先就可以在這條湖上
把這個流量六填上
填完以後呢
我們繼續來看四號節點
四號節點流入流量之和呢
是六
流出呢有兩條湖
一個是四號到三號這個湖
再一個是四號節點到六號節點
那麼這個流量六
在這兩條湖上怎麼來進行翻配呢
可能同學們就會說了
有好多種翻配方案呢
具體可以翻成六零五一等等
有許多方案
好像目前來看的不好
臨時來確定這個具體的翻配方案
那麼沒關係
我們繼續往後看可以
比如說我們看五號節點
那麼可能也想到這一條了
五號節點的流出的流量
已經給出來了
那就是六
所以流入到五號節點流量
也應該是六
那麼我就可以先把這條湖上
這個流量六給填上
這樣的話我們繼續來看三號節點
三號節點流入到三號節點流量是六
流出是六
所以這條湖呢應該是零
好所以三號節點也就保持平衡了
最後這個我們再回頭來看四號節點
那麼相應的翻配方案也就給出來了
因爲這條湖上是零了
所以這條湖上的流量應該就是六
這樣的話我們可以經過簡單的檢驗
就會發現
這確實是一個滿足條件的可行流
那麼其實這個可行流的給出
剛纔我們是按照這樣的方法給出
也可以按照其他的一些方法
也會得到這樣的答案
比如劉同學可能一上來
就可以先在這條湖上填上這個六
這是怎麼想的呢
因爲通過這個網絡的總流量是確定的
目前來說從一號節點流出的流量之和是六加六是十二
所以我們說這可行流的流量應該是十二
那麼這個十二呢
也應該等於流入到終點六號節點的流量之和
我看現在有一個六了
所以這條湖也應該是六
才能保證這個流量是十二
這樣這個六確定了
這個翻配方案這個零
還有相應的下面的六都可以確定了
這也是一種方法
同樣找出這樣一個可行瀏覽
好這是第一萬
我們繼續來看第二萬
第二萬呢
就是說給定這樣的節點劃分方法
V1集合包括一號和三號兩個節點
而V2集合呢
包括二四五六的三個節點
那麼要求填上
第一這個V1V2表示什麼來着
表示的是當前劃分情況下的節集是什麼
最後這一項呢
要求填上節量是多少
好先請同學們想一想
節集應該包括哪些湖
節量又是多少
按照節集的定義
那麼節集應該是從第一集合中
任何一個節點正向指向第二集合
任何一個節點所有湖的集合
所以我們看在當前的劃分情況下
這個滿足條件的湖應該有兩條湖
一個是一到二號這條湖
再一個呢是三到五這條湖
所以這是節集
那麼節量呢就應該是節集上的容量之和
容量之和
好了節集有這兩條湖
一個是一到二再一個是三到五
那麼他們倆的容量分別是八和八
所以節量就是八加八等於十六
這是第二問
第三問要求同學們在這個圖形的基礎上
通過標號的方法來求數最大流
好按照我們在前面講過的最大流的標號算法
我們從起點開始標號
起點標應該是無窮大位一
在這位一呢我就特指一號這個節點了
然後再觀察一下從一號節點流出去
看看有沒有未飽和的湖
當然有兩條湖
一到二和一到三呢都是未飽和的
我們只需要認選其中的一條
比如說我選擇了一到三這條湖
那麼我們就可以給這條湖
發現它是未飽和的湖
那麼就說相應的要給三號節點標號
標多少呢
調整量是七減去六是一
所以應該是一位一
目前標號是一和三號節點
那麼繼續觀察從一三兩個節點出發的
有沒有未飽和湖
或者流入到這一三兩個節點
有沒有非零的湖
好經過分析發現
三到五號這條湖呢
是一個流出去的未飽和湖
所以我們繼續給五號節點標號
五號節點標應該是二位三
繼續來分析
看有沒有流出去的未飽和湖
有一條五到六號這條湖
所以那麼最後呢
我們給六號節點標上了號
七減六是一
所以是一位五
這樣從七點標到終點
我們就得到了一條增廣鏈
具體來說就是一三五六
那麼這個增廣鏈呢
都是正向湖
都是正向未飽和湖
我們可以沿着這條增廣鏈進行調整
調整量呢
我們可以選取最終是
各個節點上的標的
這個調整量的最小值
所以是一
好經過調整
也就是說在正向湖上加流量
反向湖上減流量
由於都是正向湖
所以同時都可以加上
剛纔選定的總的調整量
調整量一就行了
這是調整完以後的
得到一個新的可行流
好我們繼續標號
一號節點標
五清道爲一
然後呢從一號節點流出去
有沒有未飽和的呢
還有就一到二號這條湖
所以繼續給二號節點標號
應該是八點六十二
所以二爲一
標到這兒
同學們可以看出來
從以標號正向流出去的
湖呢都已經飽和了
沒有反向流回的湖
所以標號結束
那麼由於沒有標的重點
說明不再存在增廣鏈了
那麼我們就可以說
調整完以後的這個可行流呢
已經是最大流了
好最後結論就是
最大流量是七加六是十三
那麼我們還要求同時求出最小節
我們說這個最大流標號算法
不僅能夠求出最大流
而且同時能夠找到最小節
具體的最小節的求解方法就是
在最後一次標號過程中
以標號節點作爲第一集合
以剩下的沒有標號的節點呢
作爲第二集合
所形成的這樣一個劃分
對應的節集
那麼具體的來說
當前的節集應該包括兩條湖
那就是一到三這一條湖
和二到四這條湖
這兩條湖形成的集合
爲最小節集
節量最小
那麼經過檢驗
這個節量呢也是六加七是十三
恰好等於最大流量
進一步的驗證了最大流
最小節定力
好這就是這道
聯繫題
那麼接下來呢
我們將要介紹一些最大流
和最小節這些方法
模型在實際中的一些應用舉例
那麼最大流最小節
這一塊方法呢
在實際中還是非常實用的
一塊模型方法
那麼接下來呢
我將通過一些例題
來具體的說明
看看最大流模型
在實際中都是如何來應用的
先來看這樣一個例題
有三個發電站
V1和V3
他們的發電能力
分別是十五十和四十兆瓦
現在要經過這樣一個電網
把電力輸送到八號地區
就是通過這樣一個電網
把最終電力輸送到八號地區
電網能力如圖所示
就是我們在這個電網的每一條弧上
都標了一些數字
這些數字呢
表示相應的這個運輸
輸送電力的這個相應的線路上
它允許的最大通過能力
比如說
V4到V6這條線路
單位時間最多允許通過
輸送十五兆瓦的電力
是這樣一個意思
其他的數字呢
都表示同樣的含義
現在問題是
求三個發電站輸送到該地區
也就是說八號地區的
最大電力是多少
就這樣一個問題
請同學們稍微思考一下這個問題
如何來求解
那麼我們會看到
這顯然是一個非常典型的
最大流問題
最大流問題就是說
給定網絡每一條邊上
都有一個容量
如何來求從網絡的起點
流向終點的最大流量
但是呢
這個問題啊
跟我們在前面遇到最大流問題
有一個區別在哪裏呢
就是它的起點並不是唯一的
而我們在最大流問題
這個模型
它的應用過程中
要求這個網絡圖
必須是唯一的起點和唯一的終點
那麼如果實際問題
可能不是唯一的起點
或者不是唯一的終點
那怎麼辦呢
常用的解決辦法
可以這樣來處理
那就是像這個問題
有多個起點的話
我們可以虛設一個總的起點
就是在這三個起點之前
再虛設一個節點
位0
位0呢
我們在這個具體問題中
可以把它理解爲
一個更大的發電站
它往這三個V1 V2 V3
小的發電站輸送電力
所以這樣的話
這個構造上一個節點以後
得到的這個新的網絡圖
就符合最大流問題的要求
畫完以後呢
還有三條弧
它上面的全數呢
並沒有標上
那麼請同學們想一想
這三條弧上
應該標上多大的容量呢
可能有的同學已經看到了
實際上我們在題目中給出的
三個發電站的發電能力
在這個原來的網絡圖中
這三個數字並沒有體現出來
注意在這裏邊
像這些數字
40 15還有30
並不是三個發電站發電能力
在這也巧合了
有40 10什麼這些數字
跟發電能力都是一樣的
實際上這些數字表示的是
這些線路的最大通過能力
並不是這三個發電站的發電能力
那麼正好
三個發電站發電能力
在原來網絡圖上沒有體現
我們是不是確實可以把它添加到
剛虛設的這三條弧上去呢
沒問題
V0到V1
把這條弧上添加了15
這個15呢
恰好是V1這個發電站的發電能力
還有其他兩條弧也是類似
這樣的話
確實是我們這樣
由於這三個發電站的發電能力
是給定的一個量
15 10 40
那麼正好這三條線路呢
我們就可以理解爲
一個更大的總當發電站
往三個發電站最大輸送的能力
不恰好就可以填上
這三個發電站的發電能力嗎
沒問題
好這樣的話
我們就得到了一個
完善的最大流量問題
所需求的這個網絡圖了
那麼接下來我們就需要按照
我們在上節課給出的最大流算法
標號算法來求出這個網絡的最大流
在這我們還是要說明另外一個問題
什麼問題呢
就是在最大流算法中
有一個最基本的要求
就是必須得有一個初始的可行流
因爲我們回顧一下增廣鏈的定義
增廣鏈的定義
它就是基於某個可行流而言的
是關於某個可行流的增廣鏈
如果這個網絡初始的可行流
沒有給出來的話
談不上增廣鏈
我們也沒法尋找這個增廣鏈
從而來進行調整或者擴充
從而使得這個總流量進入擴大
或者甚至檢驗
是不是當前這個流量是不是最大
沒有這個初始可行流
所有這些工作都談不上
而像這個問題
實際問題啊
給的這網絡圖
可能初始可行流確實是沒有的
所以我們就面臨這樣一個問題
在實際應用過程中
初始的可行流怎麼樣給它標上
那麼我們也容易想到
可能有兩種方法
帶着我一塊來介紹一下
最容易想到的這種方法呢
就是對任何的最大流網絡
都普遍適用的一個初始的可行流
那就是什麼呢
也是最簡單的一個可行流
可能有同學想到了
在每一條湖上都標上零的流量
不就行了嗎
確實
這顯然是一個初始可行流
就是說所有的湖上的流量
都讓它等於零
當然是一個可行流了
因爲這個零這個流量
小於等於任何的肥滬的流量
而且對於任何中間節點
都是滿足平衡的
所以是一個可行流
而且是一個最簡單的可行流
任何網絡圖都可以適用
但是顯然我們並不推薦這種方法
爲什麼呢
因爲這種可行流啊
所有流量都爲零的可行流
它的水平太低了
它的總流量就是零
那我們需要不斷地調整調整
可能基於這樣一個零流的流量
這樣的初始可行流來調整的話
調整的步驟可能是非常的麻煩
可能要調整多次
那麼我們在這就給出另外一種方法
除了這樣一種最簡單的
初始可行流的給定方法以外
我們還可以按照一種所謂的探索的方法
來自己摸索地標上一個初始的可行流
怎麼來摸索地標呢
基本想法就是
在各條湖上任意地往大里
儘量往大里標上一個可行流
但是在標的時候呢
要保證滿足可行流的那兩個條件
那就是不能超過容量
第二個呢
滿足平衡條件
然後我們儘量往大里標
這樣得到這個初始可行流呢
有的時候還比較容易成爲一個最大流
當然是不是最大流
還需要經過標號算法來驗證
就看看是不是存在增廣鏈
如果不存在增廣鏈的話
那我就說是最大流了
即使我們可能初始標上的可行流
不是最大流那也沒關係
可能可以經過簡單的調整呢
就能夠很容易地得到最終的最大流
所以我們更推薦
這兩種方法的第二種方法
就是用探索的方法
或者摸索的方法
來根據可行流的條件
兩個條件來標上一個初始的可行流
好了
下面我們就以這個例題爲例
來具體地演示一下
這個初始可行流的標定方法
我們只需要從前面的湖一次分析起就行了
像第一條湖
V0到V2
那麼這條湖上標多大流量呢
當然我們儘量往大的標
可以標個10試一試
好標上10了
標上10
那麼V2這個節點要注意了
V2節點有兩條流入的湖
一個是V5到V2
再一個就是V0到V2
有一條流出去的湖
那就V2到V7
好
那麼這條流入的湖
我們也可以把它的流量標上10
這樣V2節點的總流入的流量就是20了
所以流出的也應該是20
那V2節點就平衡了
我們進一步來看V5節點
V5節點有一條流出的湖流量是10了
還有一條流出的湖
最大也可以標上10試一試
這樣V5的流出的總流量也是20
所以流入也要保證是20
20沒問題
滿足這個可行流的條件
所以V5節點也是平衡到了
這樣上一條線
我們就標完了
就這樣不斷的往下標
在標的過程中
可能會出現個別的小的錯誤
沒關係
我們擦掉再往回重新來一把
我們再來看下面這條線路
V0到V1可以標個15
V1到V4也可以標個15
這個都是單線的
單入單出的都比較簡單一些
好
V4到V6也標了個15
現在我們來分一下V6節點
V6節點比較複雜一些
V6節點有兩條流出去的湖
分別是V6到V5和V6到V7
這兩條湖
由於有一個流出的流量已經是20了
這個流出的流量最大可以到15
這樣假設我們這條湖流量填15的話
流出的總流量也就是35了
流入來看有一個15了
還有一條湖是V3到V6
爲了保證也是35
所以這條湖應該填20
那麼V0到V3也就填20了
這20是經過我們好幾步的分析
纔得到了一個20
可能有同學上來就說
我先填個40
填個40以後呢
這條湖這個容量條件還是滿足的
但是到下面這條湖就不行了
所以有同學又說了
我先填個30
填了30這地方都還行
但到了V6節點又不行了
我們沒關係
前面可以試着先填上40或者30
後來經過不斷的往上填
會發現到了後面節點
可能不滿足這個條件了
那我就再把這幾個40 30
剛填的幾個數再擦掉再重來
這樣的話就經過摸索的
這樣不斷的往上填
就能得到一個初始科學流
好我們繼續往後看
剛纔說到了V3到V6這條湖流量可以填個20
好V6節點流入35
流出也應該是35
這樣就平衡了
最後來看
還有V7到V8這條湖沒有填流量
那我就分析V7節點
V7節點有兩個流入
一個是V2到V7
再一個是V6到V7
流入的流量之和應該是20 25 35
所以V7到V8這個流出
作爲V7節點的流出流量也應該是35
這樣我們從頭到尾啊
就填上了一個初始的可行流
可以簡單的驗證一下
比如說我們從起點看
這個可行流的流量是多少呢
10加15加20是45
然後我們再看一下終點
流入到終點的流量之和是10加35
也是45
那基本上就可以說
我們得到這個流啊
確實是可行流
好這是第一步
我們用一種所謂的探索的方法
標上了一個初始可行流
那麼說這個問題
最終要求一個最大流
那接下來怎麼辦呢
就標號法來求一下最大流
從起點開始標號
胡青大V0
然後從起點流出去
有沒有微飽和的呢
有一條V0到V3
所以接下來給V3節點標
40加20是20V0
然後這兩個以標號節點流出去
有一個微飽和胡
就V3到V6
所以接下來繼續給V6節點標
標什麼呢
10V3
這個10是30加20
標了這三個節點
就是V0V3和V6以後
接下來請同學們再仔細觀察
看有沒有滿足條件的
繼續往後標號的胡呢
可能不大容易觀察出來
實際上經過仔細觀察
應該還有一條胡
還要繼續標號
哪條胡呢
有V4到V6
這條胡屬於一個反向的非0胡
是屬於未標號直向
以標號節點流量是15
不是0
是一個非0胡
所以按照我們前面標號算法
流入非0胡
也要繼續往後進行
所以接下來應該給V4標
V4標的內容就是15-V6
標完這個以後呢
又有一個流入
V1到V4的流入非0胡
所以繼續給V1標號
標的是15-V4
標到這兒爲止
再來看
沒有了
就流出去的胡都飽和了
流入的胡呢
也不再存在了
所以標號結束
我們發現這個標號
並沒有標到終點
換句話說
不存在增廣量
所以剛纔我們通過探索法
來標上的一個初始可行流
確實經過驗證
就是一個最大流了
那最後的結論
我們也就有了
從這三個發電站
輸送到八號地區
最大的輸送電力是多少呢
算一算
10加15加20
就當前這個可行流的流量
是45
好
這就是這個問題
輸送到八號地區的
最大電力是45
在這個問題的基礎上
下面我提一個問題
請同學們進一步的來思考
在當前的網絡能力下
輸送到八號地區
確實就是45兆瓦的電力了
那麼如果八號地區
對於這個45兆瓦
這個電力需求
它是不夠的話怎麼辦
或者說45兆瓦的電力
對於它來說是不夠用的
比如說它這個八號地區
實際上需要50兆瓦的電力纔夠
那麼當前這個網絡已經不行了
當前網絡能最大通過的流量
也就是45了
還差五個單位
沒有滿足它的需求
那麼問題就是
如何來對現有的網絡進行擴容
可以使得達到50兆瓦的送送電力
注意大家說的是擴容
並不是擴流量
擴容就是對線路的
基本條件進行擴充
就它目前各條線路能力
是確定的
比如說10
或者是其他的一些數量
那麼我們能不能在現有基礎上進行擴容
使這個容量再進一步擴大
這樣的話
有可能這個網絡的最大流量
也會進一步擴大
那麼現在問題是
在哪些路段上擴容是有意義的
就可以最終確實能夠保證
從三個發電站
輸送到八號地區的電力
能夠進一步的擴大
因爲我們看
顯然有一些線路擴容
是沒有意義的
比如說V3到V6這條線路
本身原來的容量30
就沒有最大利用
它這條線路上最多
目前來說就安排了20的流量
本來就沒有充分利用
那麼原來30這個容量
就沒有必要再擴充了
那麼滿了的是不是就有意義呢
我們怎麼來分析這個問題呢
怎麼來分析這個問題
在哪些線路擴容
可以確實能夠提高最大流量
請大家思考一下這個問題
這就聯想到了
我們在上次課中
給出一個非常重要的定理
那就是最大流最小節定理
這個同學們可能還記得
怎麼叫最大流最小節定理呢
就和網絡的最大流量
等於最小節量
能不能進一步來思考
這個定理說的什麼意思呢
就是說
要想提高最大流量
怎麼辦
提高最小節量就行了
最小節量提高的話
最大流量也就跟着提高了
從這可以看得出來
最小節級那些湖
實際上成爲
制約最大流量的一個瓶頸了
也就是說
要想擴充
現有網絡的通過能力的話
必須擴充這個瓶頸
但其他的線路擴充
可能沒有意義
瓶頸是什麼呢
剛纔說是最小節級
只要最小節級上的容量提高了
那麼最小節量也提高了
提高了以後呢
這個相當於
最大流量
又跟着往上提高了
所以這個問題的關鍵
我們就把最小節級
找出來實際上
而如何來找最小節級呢
我們說這個標號算法
它的一個優點就是
在標數最大流的同時
也能夠找到最小節級
我們看
在這次標號
沒有增廣鏈這次標號中
以標號節點是
位0
位3
位4和位6這四個節點
其他的節點都沒有標號
我們做這樣一個劃分
以標號節點和位標號節點
形成的一個劃分
在當前這種劃分下的節級
應該就是最小節級
所以
我們可以把最小節級
給標出來
一共有三條弧
分別是位0到位2
位6到位5
以及位6到位7
那麼也就是說
在這三條弧上
在這三條弧對應的線路上
進行擴容
是有意義的
能夠使得總流量進一步的擴大
好
這就是這個問題
下面我們繼續來看一個例題
圖中
ABCDEF
是一些陸地或者是島嶼
那麼一共有14座橋樑
1 2 3
一直到14
這樣的編號
河的兩岸
分別互爲敵對的雙方部隊所佔領
問題是
至少應該切斷幾座橋樑
具體的要求指出切斷橋樑的一些編號
才能夠達到阻止敵方部隊過河的這樣一個目的
是用圖論的方法來進行分析
這樣一個問題
也是先請同學們思考一下
怎麼來分析這個問題
好
我們一塊來分析
那麼同學們可能看到這個圖就想到了
我們在這一章開頭所提到的一個問題
哥尼斯堡橋問題
確實這個圖有點像哥尼斯堡橋問題
那麼
用圖論的方法來求一個解決這個問題的方法
首先就應該把這樣一個實際問題
畫成一個由點和線組成的圖形來表示出來
而在哥尼斯堡橋問題
我們當時也有了一套處理辦法
那就是把陸地或者島嶼用節點來表示
而把橋樑用邊來表示
但是在這有這麼一個問題
如果兩個節點之間有多座橋樑
那麼可能同學們容易想到
那麼有五座橋就得畫五條邊了
這也是我們前期在哥尼斯堡橋問題裏面
確實是這麼來處理的
那麼還有一種想法
可能可以簡化這種畫圖的方法
什麼想法呢
假設兩個陸地之間有多座橋
比如說有五座橋
那麼我們無論有多少座橋
就畫一條邊
而橋樑的數目
我們可以用邊上一個全數來表示
這樣的話就可以簡化這個圖形
就是用全數來表示兩點之間
這個橋樑的數目
好
我們就試着來這樣來畫圖
在畫圖的時候還有一個問題
那就是
如果我們想用這一節最大流最小節問題的方法
來分析這個問題的話
這個最大流模型要求的網絡圖
一定是有向網絡圖
而像剛纔這個實際問題
由於這個邊它表示的橋樑是沒有方向的
所以我們還需要把這個無向圖轉化成有向圖
如何來把無向圖轉化成有向圖呢
其實很簡單
那就是把每一個無向邊
用一對雙向的有向邊來代替就行了
每一條無向邊用一對方向相反的
有向邊來代替它
這樣就可以把任何一個無向圖
來等價的轉化成一個有向圖
也就是說實際上無向就是雙向
雙向就是無向
那麼在這個轉化過程中
你看我在這實際畫了一下
A F表示河的兩岸
B C D E表示河中的島嶼
在畫這個圖的時候
我還做了一個簡化處理
那就是除了B C D E這四個島嶼之間
確實是用雙向的有向邊來表示以外
那麼關於河的兩岸關聯的這些邊
我都只畫了一個方向
實際上這是一種簡化
那麼結合這個具體問題
它的實際意義是這樣的
我們假設A這一岸是居住的敵方
那麼F這一岸是居住我方
那麼敵方想通過這個橋樑過河
那麼當它通過某些橋樑到達了這個島嶼
然後進一步想過河的這個過程中
顯然如果它到了C島嶼
沒有必要再返回去了
同樣從C到了F以後
它就完成目的了
也沒必要往回返了
所以我們看到跟河的兩岸關聯的這些邊
畫成一個大的方向就行了
我在這畫的從A到F這個方向
而島嶼之間這些邊不好確定方向
我們都是用雙向的有向邊來代替的
這樣就轉化成這樣一個網絡圖
每一條湖上的全數
表示相應的兩點之間的橋樑的數目
下面我們繼續來分析
這是一個什麼問題呢
就是說要想達到阻止敵方部隊過河這樣一個目的
怎麼樣來截斷橋樑
可以實現這樣一個目的呢
我就想到了截擊這樣一個概念
截擊我們曾經在上幾次課中也提到過
它的概念指的就是
在一個劃分條件下
從第一集合指向第二集合的所有湖的集合
截擊的意義呢
就是能夠實現從起點到終點
對這個從起點到終點這個流的截斷
換句話說
只要我們把任何一個截擊給從圖中刪掉的話
從起點到終點再也沒有通路了
而這個不正好符合我們的要求嗎
我們現在要求的就是阻止敵方部隊過河
那我們只要刪掉或者說
炸掉任何一個截擊所代表的橋樑
那麼從起點到終點就不再存在這樣一個條通路了
它就無法過河了
所以啊
我們就考慮截擊
那麼又話又說回來
不同的截擊都可以實現這樣一個目的
都可以達到阻止敵方部隊過河的這樣一個目的
而不同的截擊
比如說我這樣截
以A節點作爲第一集合
剩下的節點作爲第二集合
它對應的截擊應該是這三條湖
A B A C A E
這樣截的話
需要炸幾座橋呢
那應該就是把這些湖上所代表橋樑總數加起來
應該是全數2加1加1
有4
這個全數換句話說就是這個當前的截量了
表示的就是這種截斷方法
如果來炸橋的話
它的一個代價
或者說需要炸掉的橋樑數目
我們看到不同的截擊有不同的截量
這個截量呢
表示相應的截擊
這種截斷方法所需要炸的橋樑數目
那怎麼樣來炸橋樑
可以使得總的橋樑數目最少呢
那這就不是一個最小截的問題嗎
所以這個問題就轉化爲
求這個網絡圖的最小截擊問題了
那怎麼樣來求最小截擊呢
我們還是可以參考
用標號方法標上一個初始可行流
然後呢
再來求最大流
在求出最大流的同時呢
我們找到最小截擊
像這個問題
我們對最大流量倒不是特別關注
我們最關注的就是最小截擊
也就是說這個標號的副產品
我們要的是那一個半量
像這個問題
它的最大流量
可能實際的意義不是特別明顯
我們更關注最小截擊
好
具體的求解過程呢
我們就不再詳細的給出來了
同學們課下可以自己求一求
就是首先標上一個初始可行流
然後從起點開始標號
直到標到得到最大流
經過驗證
最小截擊應該是這樣截斷
就以ABC作爲第一集合
以DEF作爲第二集合
形成一個劃分
在這個劃分下
對應的階級是這三條弧
AE CD CF
節量是3
所以最少需要炸掉三座橋
這三座橋分別是
A到E C到D和C到F
對應的三座橋
編號應該是6 7 12
對於這個答案
可能有同學事先已經觀察出來了
那麼當然我們在這
是通過圖論的方法
非常嚴密的來推導求解出來的
這是這個問題
這個題屬於最小截擊的
一個典型的應用
下面繼續來看另外一個例題
例25
有一批人從我國A城
要赴俄羅斯B城
可能的旅行路線如圖
現在邊防隊
你建立足夠數量檢查站
以便使每輛汽車
至少必須經過一個檢查站
建立檢查站費用
根據路段條件有所不同
那麼在這裏邊
各個權術就表示這個費用
求最小費用解
這個問題
請同學們思考一下
如何來求解
好 我們一會來想一下
分析一下
注意這塊建檢查站
要求是在路段上建檢查站
這樣的費用
也相應的給標出來了
那怎麼樣來建立檢查站
使得每輛汽車
都必須至少經過一個檢查站呢
這同樣是階級
所能夠實現的一個目的
能夠達到這樣一項功能
我們說
在不同的階級上來建檢查站
都能夠實現
任何一個汽車
必須得經過這個階級上的
所有的路段中的
任何一條
至少得經過其中的一條
而不同的建檢查站的
階段方法
有不同的階級
它有不同的節量
這個節量又表示什麼含義呢
比如我這樣階級
以左邊這些節點作爲第一集合
以右邊這些節點作爲第二集合
它的節量呢
是2加5加7是14
這14是不是恰恰表示
相應的階段方法
所需要的總費用
確實是這樣的
那不同的階級呢
它有不同的節量
所需要的費用呢
也就相應的可以計算一下
那麼最小費用的階段方法
或者說建立檢查站的方法
是什麼呢
顯然也是一個最小階級問題
那這個問題
如何來求最小階級呢
就跟剛纔的例題一樣
我們也需要初始地標上一個可行流
然後呢
不斷地標號來求出最大流
同時找到最小階
我們也是關注的是最小階在這
這是這個例題
好
同學們先下課休息一下
