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

长安书院_
146粉絲
2026年11月16日
AI 生成·可能包含錯誤
同學們好
這節課我們繼續來學習網絡分析的最大流問題
那麼我們在上一節課中
介紹了關於網絡最大流問題的一些重要的概念和定理
比如說其中一個重要的概念是增廣鏈的概念
我們一塊來回顧一下
什麼是一個增廣鏈呢
所謂一個網絡的增廣鏈呢
指的是從起點到終點的一條鏈
如果這樣一條鏈
它的正向弧都是未飽和的
反向弧都是非零的
這樣一條鏈叫做一個增廣鏈
第二個重要的概念是節集和節量的概念
所謂節集是相對於對節點的一個劃分而言的
如果我們把一個節點集做了一個劃分
其中起點屬於第一集合
終點屬於第二集合
那麼在當前這個劃分情況下
節集指的是從第一集合任何一個節點
指向第二集合任何一個節點
所有可能的弧構成的集合
那麼這些弧上的容量之和呢
就稱作當前這個節集的節量
我們還給出了一個非常重要的定理
那就是最大流最小節定理
主要說的就是網絡的最大流量等於網絡的最小節量
上節課最後呢
我們還給了這樣一個例題
介紹瞭如何來求針對一個網絡的一個劃分情況下
求出它的節集和相應的節量
好 這是上節課的主要的內容
下面就請同學們來理解一下
我們爲什麼在這要定義這樣一個概念
節集還有節量的概念
節集到底是起到一個什麼樣的作用
可能我們從數學上這樣來定義這樣一個概念
對於數學的這個集合的一種表示方法
可能都已經理解了
基於這個例題呢
我們也能夠找到這個任何一種劃分情況下它的節集
但是基於它的實際意義呢
可能同學們還有點疑惑
到底爲什麼這樣來定義節集
反向的弧爲什麼就不算呢
我們再來基於這個例題來解釋一下節集它的具體的含義
看一看
實際上這個節集
任何一個節集
當然這就是其中一個節集了
任何一個劃分對應的任何一個節集實現了這樣一個作用
我們可以反着想這個問題
節集它這個字面意思有節段的意思
反着怎麼想呢
如果我們把節集這相應的弧從網絡中刪除的話
同學們可以觀察一下會導致一個什麼樣的後果
假設啊
這個網絡把這兩條弧比如說給刪除了
導致的後果就是從起點vs到終點不再存在任何的通路了
不再存在任何的路了或者說
可以檢驗一下
比如說把這兩條弧去掉
從起點vs到終點不再存在路了
這就是節集的作用
比如說我只要把這個節集砍掉
那麼起點vs到終點就不會存在任何一條路
當然這是這個節集
有同學說我別的節集行嗎
任何一個節集都能夠實現這樣一個目的
或者說達到這樣一個目的
比如說我還可以這樣來做劃分
對節點集
第一個集合只包含起點
第二集合呢
包含剩下的所有的節點
那麼如果這樣
也就是說這樣來劃分的話
我們會看到節集的話
包含兩條弧
一個是vs到v1
再一個是vs到v2
那麼當前這種節集
我們也可以試着把它給刪掉的話
同樣是起點到終點不再存在任何通路
還有其他的節集都能夠達到這樣一個作用
這就是節集
或者我們還可以從另外一個角度來考慮
我們可以形象地想一想
比如說從起點
假設代表了一個水源
然後每一條弧表示一條河流
終點是一個目的地
那麼這個水流從起點這個水源開始往終點流入
在流到終點的過程中
可能要經過任何一條河流
如果我們把任何一個節集上給建上一個大壩的話
比如說把這兩條弧給建上大壩
是不是咱們同學想想
就可以保證截住所有起點到終點的所有的水流
確實是可以這樣的
就是說從起點到終點
我要想給截住所有起點流向終點的水的話
那麼只要在這個節集上進行截斷就行了
能夠截住起點到終點的所有的流
當然其他的節集也能夠實現這樣的一個目的
這樣的話我們看節集爲什麼叫節集
就是截斷的含義
那麼在最大流問題底
我們前面講到了流量
在這又講到了節集和節量
這兩者之間確實是有一個矛盾的關係
流就是想從起點流向終點
而節集就想截住這股流
那麼它們之間在大小上是不是也存在一定的關係
下面我們就來討論這個問題
關於流量和節量的關係問題
好
我們直接給出結論線
可以這樣來描述
任何一個可行流的流量都不會超過任何一個節集的節量
要注意這個結論中這兩個刃一
刃一可行流
後面有個刃一節集
我們先來理解一下前面這個刃一
我們在上節課通過介紹可行流的定義可以知道
一個網絡
那麼它的可行流可能有多個
甚至有無窮多個
它就相當於當時我們建立的線性規劃模型的任何一個可行節都叫做一個可行流
那麼比如說我在這個網絡圖中當前我填了這樣的流量
每一條湖上都填了這樣的流
那麼這就形成了一個可行流
它滿足容量約束跟平衡約束就叫做一個可行流
那麼還可以填其他的可行流
好
第一個刃一就說有多個可行流
我們任選一個
再看第二個刃一
刃一節集
那麼我們在剛纔複習節集的概念也提到過了
節集也不是唯一的
那就看咱們對整個節點集合如何來做劃分
當然在這劃分過程中要求起點屬於第一集合
重點屬於第二集合
只要滿足這條件
我們對這個節點集合任何一個劃分都會對應任何一個節集
所以節集也有多個
當然它不是無窮多個了
它是有限多個
不管怎麼說
那麼也是多個
所以這地方刃一是指從多個節集中任選一個
那麼它們的對應的量的關係就是
可行流的流量都不會超過任意節集的節量
我們可以檢驗一下
基於這個例題
我們繼續來檢驗一下
任何一個可行流
在這個網絡圖上我們標了一個可行流
它的流量是多少呢
同學們再來想一想
怎麼叫一個可行流的流量來的
想出來了吧
可行流的流量指的是
我們可以從起點看
起點流出的所有湖上的流量之和
那就是2加3等於5
或者是從終點看也行
流入到終點的所有湖上的流量之和
你說當前可行流的流量是5
我們再來看任何一個節集
我們還是拿剛纔這個例題這種劃分
那麼它對應的節集是這兩條湖
這個節集上的容量之和
或者說當前這個節量是多少來的
是7剛纔算出來了
剛纔流量是5節量是7
所以5小一點的7
經過驗證確實滿足這個性質
那麼我們同學也可以在課下
任意的找出網絡的其他的一些可行流
或者是在任意找其他的一些節集
可以經過檢驗
都滿足這樣一個性質
那麼這個性質是爲什麼成立呢
下面我們給出一個簡單的證明
我再簡單推證了一下
這是因爲vf表示vf這個可行流的流量
流量在這之前我們給出的計算方法
都是從起點或者是終點來計算
起點流出的流量之和
或者是流入到終點的流量之和
那麼爲了證明這個性質
我們實際上也可以從另外一個角度來算流量
就是從劃分節點級這種角度來計算流量
具體的我們可以這麼來計算
就是fv1v2-fv2v1
這是什麼意思呢
fv1v2指的是從一個節點級的劃分情況下
從v1節點級指向v2節點級的所有湖上的流量之和
減去返回來流回去的
從v2流到v1的所有的流量之和
比如說我們還是以這個例子爲例
剛纔我們算的這個當前可行流流量是5
是這麼算的
是2加上3
實際上也可以另外一種角度
就按照剛纔說的這種方法來算
具體怎麼算呢
好
基於這個劃分
這個橫斷面
我們從這橫斷面開始考慮
正向穿過這個橫斷面的
湖上的流量之和是多少呢
是這兩個吧
這兩條湖
一個是vs到v2
它對應的流量是3
還有一個是v1到vt
它對應的流量也是3
這倆加起來是3加它等於6
這是正向穿過來的
就第一個式子
fv1v2
那麼返向流回去的流量是多少呢
換句話說
從v2點擊指向v1點擊上的所有的湖
它上面的流量之和是多少呢
返回指向去的湖有兩條
實際上是v2到v1和v3到v1
這兩條湖的流量之和
我看1和0
也就是加起來是1
剛纔我們記住了
正向穿過來的流量之和是6
返向流回去的又是1
這兩個數再一減
6減去1
大概就等於5了
這個5恰好就是我們當前可行流的流量
流量我們原來從7點算
不也是2加3等於5嗎
這不是一個巧合
這是一種必然
你說流量還可以這麼來算
確實是也很好理解
就是說基於一個橫斷面
正向流過去的
減去返向流回去
那這一減不就是淨流量
或者說可行流的流量
沒錯
好
繼續往後看
這個式子
我們把最後面這一項給刪掉
所以就小於等於fv1v2
這個沒問題
這一項很簡單
而fv1v2
當然就小於等於cv1v2
因爲fv1v2特質就從v1正向穿過去
指向v2的所有是湖上的流量之和
而這個節量
最後這一項是節量
對吧
節量不也正是從v1節點級正向穿過去
指向v2節點級的所有湖上的容量之和嗎
而每一條湖上的流量
都會小於這條湖上的容量
所以加起來還是會小於等於的
所以這個結論又成立了
經過這樣一系列推導
我們就得到了可行流流量和節級節量的這種關係
這個關係非常重要
我們進一步繼續來看這個關係
請同學們來想一想
假設如果一個可行流的流量
恰好能夠跟某一個節級的節量達到相等的話
那麼會出現什麼樣的結論呢
給他們思考一下這個問題
剛纔說到了可行流流量都小於或者等於任何一個節級的節量
如果恰好有一個可行流流量正好等於了某一個節級節量
沒錯
那麼流量是不是就達到最大了
而節量就達到最小了
那麼這就是我們這一節課
也是給出了一個非常重要的定理
叫最大流最小節定理
簡單的來說就是網絡的最大流量等於最小節量
這個定理也請同學們來記住它
好
那麼剛纔說了這麼多了
介紹了流量介紹了節量
還介紹了流量和節量之間的一些定量關係
那麼同學們可能對於這麼複雜的一些概念
甚至一些定理或者性質
覺得有點可能接受起來比較困難
或者定理或者這些概念的學起來有點混亂
爲此我們一塊來看一道例題
這個例題是比較綜合的來複習一下
我們下面給出的這項一些重要的概念和性質和定理
好
我們一塊來看
這是一個網絡圖
那麼這個網絡圖每一條邊上掉了兩個數
分別是容量和流量
這個跟前面沒什麼區別
有三個問
第一問
確定所有的節級
我們就試着把所有節級來找出來
第二問
求最小節級的容量
節量最小的節級把它找出來
第三個
就證明一下圖中給的流就是最大流
這個問題先請同學們稍微思考一下
我們一問一問的來求
先來看第一問
要確定當前網絡圖所有的節級
所謂所有的節級剛纔也多次提到過
那就看有多少種對於節點級的一個劃分方法
這個劃分要求起點屬於第一集合
週年屬於第二集合
我們看看有多少種劃分
好
一塊來
每一舉出來
爲此我們就只需要把V1這個集合定義好了就行了
因爲V2集合就是剩下的節點了
對吧
好了
V1集合可以只包含一個節點
那就是起點
因爲起點必須屬於V1集合
就是說令V1如果等於Vs這個節點構成的集合的話
節級我們可以找一找
由V1集合正向直向V2集合的弧有兩條
一個是Vs到V1
再一個是Vs到V2
那麼這兩條弧上的容量之和或者說節量是多少
2加4是6
這是第一個節級
那麼V1集合包含一個節點的情形也只有這一種情形
接下來我們繼續來討論或者說列舉出左右包含兩個節點的情形
Vs和V1這兩個節點可以構成第一集合吧
沒問題
Vs和V1構成第一集合
那麼這時候的節級呢
我們會看到
從第一集合正向直向第二集合的弧一共有兩條
分別是Vs到V2和V1到Vt
那麼這兩條弧上的容量之和
我們繼續來看
V1集合還可以包含Vs和V2這兩個節點
就是這兩個節點
請同學們觀察一下
如果這樣來劃分的話
節級有哪些弧
我在這就沒有具體寫出來了
同學們可以思考一下
看看包括幾條弧
一共有三條弧
Vs到V1
然後V2到V1和V2到V3
一共這三條弧
這三條弧上的容量之和是2加3加2
是7
好 節量是7
V1集合包含兩個節點還有一種情形
那就是Vs和V3這兩個節點也可以構成第一集合
沒問題
也符合條件
那麼這時候的節級呢
也可以請同學們觀察一下
看看有幾條呢
有4條
分別用黃色的線來突出出來了
Vs到V1這一條
還有Vs到V2這一條
還有V3到V1
以及V3到Vt
那麼經過檢驗
這四條弧上的容量之和是12
所以當前的節量是12
這是第四個節級了
我們看到V1集合包含兩個節點的情形
已經全部列舉出來了
因爲終點不能屬於第一集合
就是說Vs和Vt不能包括在第一集合裏面
那我們繼續來列舉
V集合包括三個節點的情形有哪些呢
就是說可以前三個節點Vs V1和V2
這樣來做劃分
那麼我的節級也沒有具體給列出來
爲的是讓同學們來自己思考一下
看看這時候的節級有幾條
好
這時候節級顯然有兩條弧
一個是V1到Vt
再一個是V2到V3
它的節量是3加2等於5
等等
還有幾個節級
我並沒有把它全部列出來
下面給同學們一些時間
請同學們把剩下的節級具體的都來給找出來
並且分別來計算一下它們的節量是多少
同學們應該做的差不多了
剩下的節級我們繼續來看
還有幾個應該說V1集合包含三個節點的情形
比如說V1集合如果包含Vs V1 V3這三個節點的話
你們算出它們當前的節量是多少嗎
Vs V1 V3節量應該是12
還可以Vs V2 V3
那麼包含在第一集合的話
當前這樣來劃分的話
節級是多少
節量是多少
節級同學們可以自己很容易列出來
它的節量經過計算是11
這是包含三個節點的情形
那麼最後還有一種情形
就是V1集合包含四個節點
分別是Vs V1 V2 V3
就是說前四個節點
當前的節級顯然是V1到Vt和V3到Vt這兩條弧
那麼節量經過計算是8
到此爲止
那麼我們所有的節級已經都列出來了
一共有八個節級
我在課件裏邊列了五個
同學們在課下自己也應該列出其他的三個了
那就是他們的節量分別是V12 V11和V8
記住了V12 V11和V8
並且我們要觀察一下
看看所有的節量中最小的是哪個
我們就可以進入第二門了
顯然最小的是第五種情形
節量爲5的這個節級
所以第二門就相應的出來了
最小節量是5
第三門要證明一下當前這個流它就是最大流
那麼在這我們顯然要用一下最大流最小節定理
因爲根據最大流最小節定理的描述
最大流量等於最小節量
最小節量已經計算出來了就是5
那麼就看看當前這個可行流它的流量是否也恰好是5
是5的話那麼就是最大流了
顯然經過計算
當前的可行流的流量就是2加3是5
正好是等於最小節量
所以這個可行流就是最大流了
那麼同學們經過這樣一個例題
我們就對節級節量以及流量
還有流量和節量之間的關係
一直到最大流最小節定理
這樣一些重要的概念性質和定理
應該說掌握得比較清楚了
好
這是這道例題
下面講了這麼多的概念
還有些性質和定理的準備
那麼我們說要基於這些概念和性質定理
我們最終要介紹一套求最大流的方法
而圖論特色的方法顯然就是標號法
在這求網絡最大流問題我們給的方法也是標號法
爲此我們先來看一看這個方法
它的一個理論依據就是我們在前面曾經介紹過的一個非常重要的概念
增廣鏈的概念
它的理論依據可以這麼來敘述
可行流F是最大流
充分必要條件是不存在關於F的增廣鏈
關於這條性質
我們實際上在前面剛纔複習增廣鏈的概念的時候也已經提到過了
比如說只要網絡中存在着增廣鏈
那麼當前這個流就不是最大流
什麼時候就是最大流
再也找不到網絡的增廣鏈爲止
這是這樣一個方法的理論依據
所以既然這麼樣的話
那麼我們標號法的想法也就出來了
基本上就是不斷的尋找網絡中看看是不是存在增廣鏈
只要有增廣鏈
那麼我們就可以說當前的流量不是最大流
就需要調整
調整完以後再檢驗看看還有沒有增廣鏈
如果什麼時候調的增廣鏈不再存在爲止
那最後我們就知道了
當前這個流就已經是最大流了
所以接下來我們就給出標號法的具體的思路
從10點開始標號
尋找是否存在增廣鏈
所以剛纔我們提到過的
具體的來說需要給每一個節點vz標號
它的標號有兩部分內容
一個是θz再一個是vi
那麼這兩部分標號內容各有它們的含義
其中θz是什麼呢
是可能的調整量
就是說假設有增廣鏈
說明當前流不是最大流的話
需要對當前的可行流進行調整
那麼在每一條湖上最多可以調多少呢
那麼相應的我標一個數
θz表示相應的調整量
第二層標號內容vi是一個什麼樣的含義呢
表示當前要標號這個節點
vz的前一個節點是vi
這就是標號法的思路
那麼通過θz我們可以得到可行流的調整量
而通過vi這個節點信息它有什麼樣的作用
我們可以反向追蹤找出增廣鏈
因爲你有了調整量到底在哪裏調
得在找到這條增廣鏈上進行調整
也是通過反向追蹤的方法
這一點有點類似於最短路算法的迪克斯拉標號這個過程
迪克斯拉算法中也是每一個節點標號標的其中
那個數大家表示的起點到該點的最短距離
而這個節點信息也是該節點它的上一節點
是什麼的上一節點
最短路上的上一個節點
前一個節點或者說
而求最大流的這一套標號方法
每一個節點標的節點信息
它是指的是增廣鏈上的前一個節點
好
這就是基本的思路
就是說需要不斷的來尋找是否存在增廣鏈
那麼接下來我們就結合一個例題
來具體的介紹標號法的方法步驟
在這例題中給了一個網絡圖
這個網絡圖每一條湖上它標的兩個數
分別是Cij和Fij
現在用標號法來求最大流
我們說了標號法
它的想法就是不斷的在網絡中尋找
看看是否存在增廣鏈
增廣鏈的定義
我們再一塊來複習一下
那就是從起點到終點的一條鏈
如果所有的正向湖都是非飽和的
反向湖都是非零的
那麼這樣一條鏈就叫增廣鏈
所以我們就衝着這個目標來尋找增廣鏈
首先給起點Vs標號
Vs標號的內容比較特殊
我們看第一個標號內容
它是標了個無窮大
無窮大是什麼意思呢
這一點目前還不能解釋
我們到最後再來解釋
第二個標號內容Vs
這個同學們好理解
那就是當前節點增廣鏈的前一個節點
Vs它的前一個節點沒有別的
就它自己了
好
所以首先我們給起點標的號了
無窮大Vs
接下來需要幹什麼呢
需要選擇與Vs關聯的
這樣兩種可能的湖
第一種是流出去的未飽和湖
如果有的話
則相應的給Vz標號θjVi
其中這個θj
注意它的計算是cij-fij
第二種情形
也可能是流入的非零湖
就流量不等於零的湖
這時候給Vz的標號是θj-Vi
這個-Vi在這先強調一下
它並沒有正負的含義
指的是這條湖是一個反向湖
這時候的調整量由於是反向湖
所以就是流量本身
因爲它要在原來基礎上減
最多能減多少就是流量
我們再來理解一下這兩個不同的情形的湖
實際上這就是衝着增廣鏈的定義
來尋找這樣的一些湖
我想增廣鏈不是正向要求非飽和
反向是非零嗎
那麼怎麼算正向呢
從以標號流出去的湖那就算正向
正向湖標的調整內容怎麼來算
我們前面曾經提到
我正向湖需要在原來的流量的基礎上
要加上一個流量進行調整
假設存在增廣鏈
我們這麼來調整
那麼最多可以調多少
顯然就是流量跟容量之間還差了多少
這是它的最大的調整量
所以調整量可能的數就是cij-fij
所以我們在cij只是可能的調整
最大也就調這麼多了
相應的這條湖
至於最後總的調整量
我們後面還會具體的來說明
反向湖就是流入的非零湖
具體的調的流量應該是
反向湖要減去流量
所以最多的調整量就是流量本身
再減多了不就減出負數來了嗎
不可行了
好
這是這樣一個尋找增廣鏈的方法
我們具體的來演示一下
現在從起點Vs
我們一塊來找一找
看看流出去的
有沒有未飽和的
或者流
當然起點現在看來只有流出去的湖
我們流出去的湖
流出的湖就要檢驗
是不是有未飽和的
有沒有
確實是有一條
那就是Vs到V1這條湖
這條湖5和1並沒有飽和
那麼將來這條湖
最大的調整量是多少
容量是5
流量是1
最多還可以在1的基礎上加4
就達到飽和了
所以調整量就是Cij-Fij
就是5-1
所以我們接下來就要給V1標號
標什麼呢
標的節點
那就說V1是從哪個節點來的
是從Vs指過來的
所以就要給V1標的是4Vs
4表示的是調整量
Vs是從Vs指過來的
好
這是第一步
我們繼續來看第二步
第二步有點類似於
在最短路算法中的第二步
那就是把節點集做一個劃分
把節點集V分成兩塊
Va是以標號點擊
Vb是未標號點擊
做成這樣一個劃分
這一步並沒有實質的標號工作
只是做一個節點集的劃分
我們就劃分一下
以標號節點
現在是Vs和V1這兩個節點了
剩下的所有的節點還沒有標號
關鍵進入第三步
考慮所有
Va集合和Vb集合關聯的弧
我們在這剪輯了一下
可以Va指向Vb
也可以Vb指向Va
所有這樣的弧
若該弧爲流出去的未飽和弧
這有點類似於第一步那個想法
那麼需要給Vj標號θjVi
θj跟第一步類似
一樣就Cij減去Fij
就容量和流量之差
如果是流入的非零弧
那需要給Vj標號θj-Vi
θj是流量的本身
就覺得可以調這麼多
好
我們具體來找一找
現在
從Va就這兩個節點
跟Vb關聯的弧裏邊看一看
正向的流出去的
有沒有未飽和的
流出去在這有兩條弧
一個是Vs到V2
再一個是V1到V3
這兩條弧我們可以很容易看到
確實是已經都飽和了
飽和的話
我們繼續來找
看看有沒有滿足第二種情形的弧
就是說反向的流入的弧
從V2到V1
屬於滿足這樣一個條件的弧
反向流回來的弧
我們檢驗的並不是飽不飽和
而是是不是非0
經過檢驗流量是1
確實是非0的
好
滿足這個條件
所以接下來就要給Vj標號
標號θj-Vi
其中θj是Fij
也就是說
接下來我們要給V2標號
那麼V2標多少呢
V2相應的這條弧
就V1到V2
V2到V1這條弧
最多可以調整多少呢
流量本身1
最多可以減1
所以它的調整量是1
那麼它是從哪個節點來的呢
上一個節點是誰呢
原來是V1
並且我們看到
是從V1反向指過來的
它是一個反向弧
所以要給V2標的是
1-V1
這個-我們前面說過
它沒有真正的正負的含義
它只是表示一個方向
反向指過來的
好
這就是第三步
好
我們進入第四步
就這樣不斷的重複二和三
依次進行的結局
有這麼兩種可能
第一種可能
Vt已經標號
這時候實際上是一個不好的消息
爲什麼這麼說呢
我們就可以這麼說
得到了一條增廣鏈U
得到增廣鏈
我們前面說過了
就說明當前的流不是最大流
所以我們把它叫做不好的消息
具體增廣鏈怎麼來找出來
就反向追蹤
接下來需要轉入第五步
第五步幹什麼
同學們可以猜得到
既然有增廣鏈
當前流不是最大流
第五步肯定是要在原來的基礎上進行調整
這是第一種情形
還有第二種情形
Vt未標號
就是說終點沒有標號
並且無法再標號
什麼意思呢
就是說我們在前面標號不斷往後推進的過程中
並沒有標到終點
標到中間的時候
這個標號就截住了
怎麼樣就結束了呢
我們前面不斷地尋找兩種弧
一個是正向流出去的未飽和的
再一個是反向流回來非零的
如果這兩種弧都沒有了
沒有再滿足這兩個條件的弧了的話
實際上標號沒法往後進行了
就這意思
這說明不再存在增廣鏈了
所以我們就可以肯定地說
此時的流已經是最大流了
此時的流是最大流
同時要注意這樣一個結論
此時的階級爲最小階
這個算做標號法的一個副產品
就是說這個標號法它有個優點
不僅找到了我們需要找的最大流
而且同時找到了最小階級
但是我就要解釋一下什麼叫此時的階級
所謂此時
就是說我們不是說到標號進行到中間過程
突然截住了嗎
無法繼續往後進行
這時候肯定就有一個位A和位B的劃分
其中位A是以標號節點
而位B是位標號節點
那麼此時的階級也就這個時候的階級
就這樣來劃分
以標號節點作爲第一集合
位標號節點作爲第二集合形成的劃分
所對應的階級就是最小階級
這個我們後邊基於這個例題
我們還會繼續來解釋
因爲現在還沒有進行到這一步
現在我們要繼續地不斷地重複二和三
第二步做節點劃分
第三步標號
好
現在進入第二步
重新地看看以標號節點集
是這三個節點了
第三步
從以標號節點正向流出去的有沒有位保和弧呢
找到了
V2到V4
這條弧是一個位保和的弧
同學們可能也看到了
不止有這樣一條滿足條件的弧
還有一條就是V3到V2這樣一條反向弧也滿足條件
它是一個反向弧
並且流量不等於零
滿足條件
同學們可能就有想法了
到底這時候滿足條件的弧不止一條
那麼接下來該給誰標號呢
我們在算法中
大家說明一下
並沒有具體的給出區別
至於下面該給V4標還是給V3標
我們只需要任選一個就行了
好吧
我們比如說選了這條弧V2到V4
比如說接下來給V4標
標多少呢
它是一個正向流出去的弧
所以調整量是4.3是1
並且是從V2過來的
所以是標1V2
這樣就又進行了一次循環
再來重複二和三
重新的做節點級劃分
從這個劃分情況下
我們會看到
正向流出去的有一條非飽和弧
反向流回去還是有非零的
比如說滿足條件的仍然不止一條
那麼接下來按照剛纔說法
應該任意選一條就行了
但這要注意一下了
同學們要注意什麼呢
比如說我們看到
如果選這條弧的話
馬上就可以給終點標上號了
而如果選這條弧
還需要經過給V3標
可能再經過幾步才能標到終點
那麼你們來說一下
這兩條弧選哪一個更好呢
當然選直接能給終點標上號的
這樣一條弧應該更好一些
爲什麼說呢
因爲我們看到了
終點肯定要標上號
就是說增廣鏈的存在
它是客觀存在的
不可避免的
在當前的可行流條件下
那麼既然這樣的話
我們就不用再磨蹭了
我還再標到V3
再把VT標上
我們只需要儘快的
把這個增廣鏈給找出來
所以我們的思路就是
什麼時候能儘快的
把這個增廣鏈找出來
這樣的一個方法
我們就儘快的給標上
好
下面我們就考慮
V4到VT的條弧
VT標什麼呢
5-3是2
所以2
V4
這樣的話我們就屬於
第四步的第一種情形了
VT已經標上號
得到了一條增廣鏈
具體的增廣鏈
可以通過反向追蹤的方法
來追蹤出來
並且需要轉入第五步
好
我們先把增廣鏈找出來
VT它的上一個接點是V4
V4的上一個接點是V2
V2的上一個接點
是負的V1
你說它這個反向弧
到V1
V1的前一個接點是VS
增廣鏈
VS到V1到V2
到V4到VT
經過檢驗
在這條增廣鏈裏邊
有三個正向弧
第一條
第三條和第四條
它們都是非飽和的
而有一個反向弧是非零的
所以確實是滿足增廣鏈的定義
我們只不過在這是按算法
一步一步來給找出來了
那麼有增廣鏈
我們說就不是最大流
需要進入第五步
第五步是一個調整的過程
具體怎麼調呢
就按照剛纔我們複習到的
增廣鏈的定義中所提到的
當時的一個給出的一個想法
就是正向弧要加上一個θ
反向弧要減去θ
而不在增廣鏈上的弧
就不要
變了
它的流量不會變
至於這個θ怎麼來確定
就是說整個的這條增廣鏈
進行調整的時候
這個流量
總的是一個統一的流量
不能說這條弧加三
那個弧減四
要選擇同一個流量
這個流量
我們就考慮了
這條增廣鏈每個節點
都標了不同的可以調整的
量
最終總的調整量
請通常想一想是就低呢
還是就高呢
當然是就低了
我們只能在這些數中選擇最小值
在這
是在θj中選最小值
哪些θj呢
vj屬於右
右是剛纔找的這條增廣鏈
就是說右上增廣鏈上這些節點中
標的調整量中選最小值
作爲總的最後的總的調整量
那麼像這個題顯然
最小值是1
好
下面就可以解釋前面遺留的一個問題
就起點爲什麼要標無窮大
我們看到最終調整量的確定
跟起點標那個數是沒有關係的
我們怎麼也求不到它那和那個數
所以標上一個無窮大
不影響最後的求最小值
我們繼續來看算法
在正向弧右加中要加上θ
反向弧中流量要減去θ
我們按照這個算法來調整一下
正向弧原來是1
調整量也是1
就是說在1的情況加上1是2
反向弧減1是0
正向弧加1原來是3變成4了
這個3變成4了
得到一個新的可行流
經過檢驗
新的可行流的流量是多少呢
3加2是5
要比原來3加1是多了1
所以通過這樣一次標號過程
我們得到了增廣量
並且進行了調整
調整完以後流量要比原來多了
多了1
那麼得到新的可行流了
這個新的可行流是不是一個最大流了呢
那麼我們誰也不敢說這樣一個結論
還需要轉入第一步
進行重新的標號
好 我們在調整完後的網絡圖上重新的標號
起點標無窮大VS
然後流出去的弧
看看有沒有未飽和的呢
有一條
所以給V1標號
3VS
經過這樣一次標號
我們看流出去的弧
就從以標號指向未標號的弧都已經飽和了
而反向流回去的
換句話說
就從未標號指向已標號的弧都是零流了
所以不再存在滿足條件的弧
這就屬於第四步中的第二種情形了
標號無法繼續往後進行
終點也沒有標上號
這就太好了
我們說增廣鏈不再存在
這說明當前的可行流已經是最大流了
我們經過計算
最大流就是3加25
我們前面曾經提到過
作爲標號法的一個副產品
我們同時找到了最小節
最小節是什麼呢
就是以當前這種劃分
以標號節點作爲第一集合
未標號節點作爲第二集合所形成的劃分
這樣劃分
對應的階級
階級是這兩條弧
就Vs到V2
V1到V3
你階級必須是第一集合正向
正向第二集合的弧
那麼經過檢驗
這個階級的節量是3加2等於5
也確實是最小節
因爲最小節量等於最大流量
剛纔計算出最大流量是5
最小節量也是5
進一步驗證了最大流最小節定律
好
這就是這樣一個算法
這個標號過程
通過這個標號過程
我們看到要比前期
我們在最大路算法中介紹的標號法等等要麻煩一些
因爲它需要可能不止一次的一個標號過程
當得到增廣鏈還需要重新的從頭進行標號
直到不存在增廣鏈爲止
好
關於這一塊我們這個算法就先介紹到這
同學們下課休息一下
