【天津大學】《運籌學》（精品課） P35 - 34. 網絡最大流問題 教學錄像（1）

這一節課開始,我們來學習網絡分析的網絡最大流問題。 我們在前幾次課中,關於網絡分析內容, 我們一共講了最小支撐數問題和最短路問題。 那麼咱們今天將要學習的最大流問題, 跟前面這兩塊網絡分析內容相比, 它在學習內容上,難度上都要比它們要更多更難。 那什麼是網絡最大流問題呢? 爲此我們也是先給出了一個引力。 請同學們一塊來看一下這個例子。 引力,下圖是一個V1到V6的交通網絡圖。 注意,全數表示的是相應運輸線路的最大通過能力。 比如說每一條線路上我都標了一個全數。 這個全數表示的是相應的條線路, 單位時間內最大能夠運送多少貨物。 要求現在制定一個方案, 使得從V1到V6的產品數量運輸的最多。 這樣一個問題, 就是我們看這個網絡圖有一個起點, 有一個終點, 然後經過若干個中間節點, 現在有一批貨物需要從起點運往終點, 通過這樣一個運輸交通網來實現這個運輸。 那麼由於實際路況條件和客觀條件的影響, 我們每一條線路都有一定的能力, 或者說運輸能力, 或者說運輸容量。 就是說單位時間內所通過的貨物量都是有一個限制的。 現在的問題, 在各條線路上怎麼樣來安排具體的貨物的流量, 可以使得這個網絡圖從起點運往終點的總的流量最大。 那怎麼來安排這個流量呢? 我在這個圖形呢, 請朋友們看一下, 繼續的又標上了相應的一個, 用黃色來標示的這樣一個數字。 那麼這個黃色數字呢, 我可以表示具體的每一條線路上的流量。 要注意這個概念區別, 剛纔已知的那個白色數字表示的這些數字呢, 是容量。 而我在每一條標上後來又標的, 用黃色數字表示的這些權數呢, 表示的是流量。 那我在用這個黃色的這些數字來表示這些流量的時候, 我在往上填這些數字的時候, 不是說隨便地任意亂填的。 它們是要滿足一定的條件的。 同學們可能已經觀察出, 在這個黃色數字跟白色數字相比的時候發現, 它們具有哪些條件呢? 請朋友們思考一下這個問題, 觀察一下看看能不能看出來。 好,有的同學可能想到了, 首先非常明顯的一條就是, 每一條線路上安排的這些流量呢, 都沒有超過容量, 流量小於或者等於容量, 這是一條。 這一條呢也是非常直觀的, 很容易看到的這樣一點。 除此以外呢, 除此以外是不是還有別的一些條件呢? 還有一條可能有的同學不一定能夠直接的能夠看出來, 那就是對於這些網絡的中間節點來說, 每一個節點流入相應節點的貨物的流量, 應該等於流出去的流量。 這樣的話, 這樣這個流量就達到了一種平衡。 就是說中間節點, 我們可以把它理解爲這個交通網絡的, 比如說收費站或者是十字路口, 過路節點吧。 那麼這些節點呢, 當貨物通過它們的時候, 不應該有所增加或者有所減少, 那麼流進多少就應該流出多少。 我們可以具體的來看一看, 以V2節點爲例。 V2節點有一條湖流入它, 有三條湖流出。 那麼按照剛纔的說法, 我們來檢驗一下, V2節點的流入的流量, 全部的流量之和應該就是這條湖上的流量5。 那麼流出的流量呢, 因爲有三條湖, 那我們要把三條湖的流量加起來, 看看是不是也是5, 2加2加上這個1也是5。 所以V2節點流入等於流出, 這樣是平衡的。 我再來看其他的節點, 以V4節點再來看一看。 那麼有三條湖, V2到V4, V3到V4, 還有V5到V4, 這三條湖同時流入到V4這個節點, 然後只有一條湖流出。 那麼這三條湖上的流量之和, 流入到V4節點的流量之和, 2加1加上3是6。 流出去的流量之和, 只有這一條邊, 也就是這個6, 也是平衡的。 類似的同學們可以檢驗一下, V3和V5也是滿足這種平衡的。 所以我們現在簡單總結一下, 我在每一條湖上標上流量的時候, 它至少滿足了兩個條件。 第一,流量不超過容量, 或者說小於容量。 第二條, 每一箇中間節點來說, 流入的流量之和等於流出的流量之和, 或者說是平衡的這樣一種條件。 那麼這樣一個流, 我們過後有一個嚴格的定義, 叫做一個可行流。 那下面再請同學們來回答一下這個問題, 那就是, 我這樣來在每一條湖上, 安排這樣一個運輸量以後, 實際上從起點到終點, 經過這個網絡, 一共運輸了多少貨物呢? 怎麼來看? 很簡單, 可以從起點看, 起點流出的流量之和, 5加上這個3是8。 所以通過這個網絡, 目前這樣來安排流量的話, 這個網絡的流量就是8。 或者我們也可以從終點來看, 流入到終點的流量之和也是8, 這兩個數當然要相等了。 只要中間節點是平衡, 這兩個數字必然是相等的。 比如說, 我這樣來安排流量的話, 這個通過網絡的總流量是8, 那這個8是不是達到最大了呢? 最大流量是多少呢? 能達到多大呢? 這就是我們這一節的標題, 網絡最大流量的問題。 好, 那這只是一個引力, 後面呢, 我會具體地來繼續來討論它的糾結問題。 那麼基於這個引力呢, 接下來我們來看一下問題的描述。 它的一般提法, 假設有一個網絡, D等於VAC, 那麼V和A呢, 我們都非常熟悉了, 就是一個網絡圖, 它的兩個構成要素分別是節點集合和圖的集合。 關於第三個要素C啊, 我們特別地要注意一下, C等於Cij構成的集合。 這個Cij, 這個全數啊, 跟以前網絡分析中所給的這些全數的內容都不一樣, 跟它們含義都不一樣。 以前, 比如說我們在最短路問題中, 那麼這個全數呢, 可能表示的是每一條路的長度, 或者是修設道路的費用。 在最小支撐數問題中呢, 那麼每一條邊上的全數呢, 也往往表示費用或者長度等等。 而在這個網絡最大流問題中, 這個弧上的這個Cij, 具體地表示的是弧的Vi到Vj上的容量。 容量這個詞啊, 屬於這個網絡最大流問題特有的一個概念。 現在地上要通過一個流, F等於Fij, 注意了, 這個流是一個比較抽象的概念, 什麼叫一個流呢? 我們看到, 這樣來定義, 用集合的符號來定義, 也就是說, 每一條邊上具體地安排一個Fij這樣的特定的流量, 所有的邊或者弧上都安排這樣一個流量, 它構成的一個集合呢, 就叫做一個流, 記錄F, F應該是英文單詞flow的首字母, 它表示流量。 每一個Fij呢, 具體地表示弧上的流量。 問題是, 如何來安排各條弧上的Fij這個流量, 可以使網絡地上的總流量V最大? 這個怎麼叫網絡的總流量呢? 或者說目前我這個安排這個流的流量呢? 剛纔我們在引例中已經提到了, 這個引例中這個網絡圖, 比如說, 所謂網絡的流量, 目前我這樣來安排這個流, 流量就是1加3, 是8, 6加28, 這個當前這個網絡流量是8, 那怎麼樣來安排可以使總流量最大? 這就是網絡最大的問題。 我們特別要注意一下, 在最大流問題的描述過程中, 有一個概念, 那就是全數它是表示容量, 這個在以前我們在其他的網絡分析內容中呢, 都沒有遇到過這樣的情形。 好, 這是問題的描述。 通過這個問題描述我們看到, 這也是一個比較典型的最優化問題, 它就是帶有約束條件的最優化問題。 所以啊, 接下來我們就來想, 能不能把這個問題用一個規劃模型, 給它描述出來。 好, 下面我們就具體的來討論這個問題。 最大流問題實際上可以用數學模型, 具體來說就是線性規劃模型來把它特定的表示出來。 那我們就回想起來, 要描述一個線性規劃模型, 至少有三個要素, 第一個要素就是決策變量, 第二要素是目標函數, 第三個要素是約束條件。 那麼這個問題我們來回顧一下, 看看問題的決策變量應該是什麼。 決策變量我們說設置的技巧呢, 就是看問題它最終要求什麼, 我們一般就把它設成決策變量。 這個問題要求什麼呢? 我們回過去看一看。 如何安排Fij? 就是說每一條湖上具體的怎麼來安排這個流量? 這不就是最終要求的嗎? 所以我們就可以把它來設成決策變量。 好, 決策變量就是每一條湖上的具體的流量安排。 第二個要素是目標函數, 總流量最大, 我們可以寫成maxw等於wf, 這種w表示總流量, 它顯然是一個流f的函數。 具體的來說, 我們在測算的時候, 可以由整個網絡的起點出發到所有邊上的流量之河, 或者是流入到終點的湖上的流量之河。 這是目標函數。 第三個要素, 約束條件。 約束條件就是說, 在求這個流的時候, 每一個湖上的流量到底應該滿足什麼樣的約束呢? 實際上我們在剛纔引例中也已經提到這兩條了。 就是說在具體的, 我在這個網絡圖上安排這些黃色數字的時候, 它們要滿足什麼條件來的? 具體的來一般化描述一下, 應該有兩類約束。 第一類呢, 我叫容量約束。 就是說每一條湖上的流量, 當然要大於等於零了。 再一個關鍵是小於等於cij, 就是說流量不要超過容量。 第二條, 我特別的要注意一下, 所謂的平衡約束。 請同學們看看這個式子是什麼含義。 sigma fij, 這也是求河邊的, 減去sigma fji, 等於當i是s的時候是vf, 到i是t的時候是-vf, 到i不等於vf, s和t的時候是0。 請同學們自己思考一下, 這個式子爲什麼能描述平衡約束? 好,我們來解釋一下。 那麼這個求河湖號, 我們先來看看是什麼含義。 我們注意了, 臨時的我們要把i先固定住了, i等於s表示的是起點, i等於t表示是終點, f等於s和t的時候就是中間節點了。 對於某一個i節點, 那麼這個求河湖號 fijj求河邊量, 那麼是不是表示的是從vi節點引出的, 出發的所有湖上的流量之河? 沒錯, 它應該是從vi節點出發的流量之河, 減去fji求河是流入到vi節點的流量之河。 那麼先看最後一條, 當i不等於s和t的時候, 也就是說對於中間節點流出減流入, 顯然應該等於0, 這個我們前面多次說過, 沒錯, 這就是平衡約束。 那麼對於起點來看, 流出減流入, 起點沒有流入湖, 只有流出的湖, 所以流出減流入, 那就是vf, 就是流量, 就是這個目標函數, 就是這個流的總流量。 那對於終點來說呢, 流出減流入, 流出沒有, 只有流入, 那流出減流入顯然就是負的流量了, 所以這兩個特殊的節點是這樣的意思。 這樣的話, 我們就得到了網絡最大流問題的一個線性規劃模型。 我們通過這個線性規劃模型, 也能夠進一步地加深對最大流問題的理解。 下面順便給出一個定義, 那就是滿足所有這些約束條件的一個流, 叫做一個可行流。 滿足所有約束條件的一個流, 叫做一個可行流。 實際上, 一個可行流的概念, 那就是這個線性規劃的一個可行解。 好, 下面我們結合一個具體的例題啊, 來看看怎麼來寫出一個最大流問題的線性規劃模型來。 例19, 還是剛纔的問題, 那麼我把這個流量都給刪了, 只有容量了。 要求寫出用途所示的這個最大流問題的數學模型, 就是線性規劃模型。 那我們看一看這個問題, 決策變量應該有多少個呢? 第一個要素就是決策變量嘛, 對於這個具體的特定的問題, 應該有多少個決策變量呢? 決策變量描述的是, 每一條湖上要安排多少的流量。 所以, 那麼我們看看這個網絡圖, 有多少條湖, 就有多少個流量。 1,2,3,4,5,6,7,8,9,10, 10個, 有10個決策變量。 我們把這些決策變量分別叫做 f12, f13, f23, 等等, 表示相應的vi到vj, 各個標, 各個湖上的流量。 這是決策變量。 目標函數, 目標函數我們看, 就是總流量最大。 那麼這個問題, 總流量可以怎麼來把它表示出來呢? 我們說了, 可以從起點出發的流量之和, 這樣來表示。 起點v1, 出發了有兩條點, v1到v2, 還有一個是v1到v3。 那麼這兩條邊上的流量之和, 也就是f12加上f13, 所以, 把它作爲目標函數max, f12加f13, 這就是總流量。 我們接下來再來看約束條件。 那麼約束條件呢, 我們就着各個接點來分別來討論。 先來看中間接點, v2接點。 v2接點的話, 有一條流入的和, 有三條流出的和。 好, 那麼爲了保證v2接點的平衡, 或者說, v2接點的所有流量之和, 應該等於流出v2接點的流量之和。 那麼我們可以具體的來寫出來, 那就是f12等於f24加上25加上23。 嗯, f12等於這個, 這就是剛纔的式子。 一次來推, v3接點, 那麼我們也可以寫出它的約束條件了。 兩條流入之和, 就是f223加上f13, 應該等於f34加上f35。 好, 還有, v4接點, v5接點, 類似的, 都可以寫出它的平衡約束欄。 除此以外呢, 再就是兩個特殊的接點, 就是起點和終點, 怎麼來把它表述呢? 實際上, 我們在剛纔上一篇, 關於這個最大流量問題的普通的模型中, 是這麼寫的, 對於起點, 流出點流入等於流量, 對於終點, 流出點流入等於負的流量。 這兩個條件可以合併成一個, 那就是起點的流出流量之和, 等於終點的流入的流量之和, 所以我們就把它寫成一個約束條件。 起點流出的流量不是f12加f13嗎? 那麼終點的流入的流量, 那就是f46加上f56, 所以這兩個寫成一個約束條件就行了。 好,這是關於平衡約束, 我們有這麼多約束, 基本上來說, 平衡約束它是受網絡的節點數目的影響, 節點數目越多, 平衡約束條件的個數就越多。 除此以外呢, 還有容量約束, 容量約束我們就不再具體的每一個都寫出來了, 我們籠統的寫一些, fij小於0, cij大於0。 實際上來說, 有多少條邊, 那麼這地方呢, 也相應的應該有多少個這樣的容量約束的條件。 就不再具體寫了。 好,關於這個先前規劃模型, 請同學們看一看前面的這五條平衡約束, 實際上最後一條, 有首尾節點的這個平衡約束, 是不是可以由前面的四條推導而得。 請同學們自己想一想, 看看是不是能夠由前面的四條平衡約束推導出來。 實際上是沒問題的, 我們只需要把前四條約束條件, 等式的左右兩邊分別的進行相加, 然後再進行化減, 可以很容易的證明一下, 就可以直接推導得出最後這個約束條件。 這麼來說的話, 實際上這個平衡約束的最後一條, 就是首尾這個約束, 也是多餘的了。 也就是說, 我們在將來寫一個網絡最大流問題的線性分化模型的時候, 對簡化期間的話, 我們只需要來把中間節點, 它的平衡約束給寫出來, 那就行了。 至於爲什麼我們還在那個剛纔上一篇的模型的一般式中, 把這個起點重點都把它列出來, 那也是爲了便於同學們理解這個問題。 那麼真正的在寫的時候, 實際上通過這個例題也看到, 可以把它這個關於起點和重點的這個平衡約束, 就不做考慮了。 因爲只要中間節點平衡, 那麼起點和重點肯定是平衡的。 這是這個線性分化模型。 當然了, 那麼基於這個線性分化模型, 我們就可以用單針心法來求出這個網絡問題, 網絡最大流問題的具體的最大流。 顯然, 對於網絡最大的問題, 我們並不希望藉助於通過建立線性分化模型的方式, 來具體的進行求解。 這是因爲, 第一, 建立這樣一個線性分化模型實際上還是挺囉嗦的。 我們這個網絡圖這麼簡單, 只有這麼六個節點, 十條邊, 就要寫出這麼一個大的模型來, 其中最後一條我還剪輯了。 所以, 對於一個更大型的複雜的網絡來說, 首先建立其它的線性分化模型來, 就是一個不小的工作量。 第二呢, 單針心法實施起來, 是不是也不是特別的簡單, 那麼也是有一個計算的工作量問題。 所以, 我們在這一節, 關於網絡最大流問題, 它的求解方法, 我們顯然是想探討一種具有圖論特色的求解方法。 那就是, 我們在上幾次課中, 曾經也類似的提到過的方法, 那就是標號的方法, 看看能不能直接在網絡圖上進行標號, 可以求出最大流來。 回答是肯定的。 但是呢, 網絡最大流問題的標號求解方法, 不是那麼簡單, 不像我們在講對轉路問題等這些求解方法, 上來就可以直接的來介紹這個方法過程。 而最大流問題的這個標號法呢, 它的求解, 我們首先要做一些概念和定理的準備。 當對這些基本概念和定理熟悉以後, 掌握以後, 我們在這個基礎上才能再進一步的來介紹標號法。 好, 下面我們就先來看一些基本的概念和定理。 第一組概念呢, 這個非常簡單。 就是說, 在網絡最大流問題中, 湖可以有這麼多叫法, 按照流量的大小, 可以分爲這麼幾種叫法。 一個是飽和湖。 飽和湖很形象這個詞兒, 那就是流量達到最大了, 等於容量了, 達到飽和了。 這樣一種湖呢, 叫飽和湖。 像下面的網絡圖有沒有飽和湖呢? 有, V5到V4這條圖, 流量等於容量。 那麼如果流量沒有達到容量, 這個上限是小於容量的話, 那麼叫做非飽和湖。 這是從飽不飽和這個角度來分。 還可以進一步地從流量適度等於零這個角度, 來給出另外一個定義, 就是零流湖和非零流湖。 零流湖就是流量等於零, 流零實際上就是。 非零流呢, 就是非流零, 流量不等於零。 像這個網絡圖, 所有的湖都是非零流湖。 這個例子中還沒有零流湖的例子。 好, 這個概念非常簡單。 接下來我們進入這一節課的第一個非常難理解的一個概念, 就是增廣鏈的概念, 也是非常重要的一個概念。 爲什麼說它非常重要呢? 因爲我們後邊要介紹的這個標號法來求解這個最大流量體系, 它的一個重要的依據就是要基於增廣鏈進行調整。 這個增廣鏈是非常非常重要的一個概念, 也不是特別容易理解。 所以我們接下來先來看一看什麼叫增廣鏈。 F爲可行流, U是Vs-Vt的鏈, 令U加等於正向湖構成的集合, U減是反向湖構成的集合。 若U加中湖結非薄, 並且U減中湖結非零, 則稱U是關於F的一條增廣鏈。 我們看到這個定義比較拗口, 有點彆扭, 怎麼這麼多條件呢? 我們不着急, 從開始慢慢地來理解一下這個概念。 首先第一句話, F爲一個可行流, 也就是說, 這個增廣鏈定義首先要基於一個可行流才能談得上增廣鏈。 增廣鏈一定是關於某個可行流的增廣鏈。 如果沒有可行流的話, 增廣鏈就談不上了。 我們接下來就以這個網絡圖爲例吧。 像這個網絡圖, 每一條湖上前面的數字是容量, 後面的數字是流量。 有個標上一個可行流的, 可以驗證它確實是一個可行流。 好了,第二句話, U是Vs-Vt的鏈。 這個關於鏈的概念呢, 我們在這一章的第一節中, 這個圖的基本概念中曾經介紹過。 什麼叫鏈呢? 我們來簡單地回顧一下吧。 這個鏈的概念, 當時是在無相圖中介紹的。 在有相圖裏面叫路。 所謂無相圖中的鏈, 指的就是無相圖中一些點邊交錯的序列, 一個地點一條邊, 一個地點又一條邊。 這樣形成的一個序列, 首尾相接的點邊交錯序列, 就構成了一條鏈。 當時確實是無相圖的概念。 而網絡最大流的問題, 它要求的必須是有相網絡圖。 那麼就好像出現一個矛盾了。 那怎樣在這個有相網絡圖裏面, 還有鏈的概念呢? 在這塊確實是我們用了一下, 無相圖關於鏈的一個定義, 借用了一下。 在有相圖裏面怎麼叫鏈呢? 有相圖的鏈實際上就是說, 如果我們先不考慮有相圖各條有相邊的箭頭, 不考慮它的方向, 只要能夠把起點跟終點連接起來, 那就叫做起點到終點的一條鏈。 它不一定是路,路必須是順着箭頭可達, 而有相圖的鏈只要給連接起來就行了。 比如我們具體的舉個例子, 看這樣一條鏈, 從位1到位2, 到位4, 到位5, 到位6。 要注意了, 這條鏈, 第一條鏈, 第一條弧, 第二條弧, 第四條弧, 都是順着這個大方向走的。 第三條弧呢, 位5到位4, 是一個反向的。 你說, 這樣來連接起來呢, 把首、尾給連接起來, 就是一條鏈, 但它顯然不是一條路, 因爲, 它到了位4到位5這條弧的時候, 它是逆行了, 不可達了, 但它就是一條鏈。 好, 這就叫有相圖的一個鏈。 那麼我們也看到了, 在這條鏈繼續往後看, 有可能有正向弧, 有可能有反向弧。 我們把正向弧的集合, 就說在這條鏈上的正向弧的集合, 計作右加。 反向弧的集合呢, 計作右減。 那麼像這條鏈裏面, 正向弧就是有三條了, 第一條, 第二條, 第四條。 而反向弧呢, 只有這一條位5到位4, 第三條就是了。 我們繼續往後看, 若右加中這些弧結非保, 也就是說, 在這條鏈上, 正向弧都是非保和的。 右減中這個弧呢, 結非零, 也就是說, 反向弧呢, 都是非零的。 那麼這個鏈, U呢, 就稱爲關於當前的可信度F的一條增廣鏈。 我們具體來看一下, 這條鏈是不是增廣鏈呢? 我們判斷一下, 扣一下這個定義。 正向弧, 第一條是正向弧, 非保和。 第二條也是正向弧, 非保和。 第三條弧, 注意它是反向弧, 我們看的不是保不保和, 而是非零。 它的流量是3, 確實是非零的。 最後一條弧, 也是非保和, 是正向弧。 它確實滿足在增廣鏈定義中給出的要求, 以正向弧結非保和, 反向弧結非零。 所以我們就說, 這個鏈確實是關於當前的可信度F的一條增廣鏈。 那麼增廣鏈定義, 現在我們就基於這個例題也掌握得差不多了。 但是對於它爲什麼這麼定義, 定義這麼一個概念有什麼作用, 可能還是不是特別瞭解。 接下來呢, 我想去結合這條增廣鏈, 再來具體的給出一個解釋。 什麼叫一個增廣鏈呢? 實際上作爲一個增廣鏈指的就是, 我們只要在網絡圖中存在一個增廣鏈, 就可以肯定的是, 當前這個可行流不是最大流量。 後面我們也會給出這樣一個定義。 具體的來說, 我們也就可以沿着這個增廣鏈, 對現有的流進行增廣, 進行擴充, 使得當前這個可行流, 它的流量再進一步擴大。 所以爲什麼叫增廣鏈呢? 可以再進一步增廣, 具體怎麼增廣呢? 我們只需要在這條鏈上的所有正向湖中, 加上一個流量, 反向湖中減去一個流量, 同樣一個流量, 加和減都是同樣一個數。 那麼可以肯定的是, 得到新的流要比原來的流量更大一些。 具體的來說, 我們拿這條鏈, 比如說我這個第一條湖是個正向湖, 那我可以在原來的基礎上加上一個流量, 加幾呢? 比如說我們加3, 得到了8。 所以當這個流改成8以後, 那麼V2這個節點的平衡受到了影響, 它的流入已經多了3了, 比原來多了3了。 所以爲了保證這個V2節點的新的平衡, 那麼我們只需要在這個V2到V4這條湖上, 把它這個流量2也擴充3, 改成5, 那麼我們看V2節點是不是已經平衡了? 沒問題, 也是平衡的了。 這個2改成5以後呢, 又進一步地影響了V4這個節點的平衡性。 那麼V4這個節點流入實際上比原來已經多了3了。 那麼怎麼辦呢? 我們在這條增廣鏈上, 跑到下一條湖, 把這個3這個流量減去剛纔那個調整量3, 變成0, 那麼我們會看到V4節點得到新的平衡。 這條湖流入多了3, 下面這條湖流入又少了3, 總的來說流入又是保持不變。 在這個基礎上, V5這個節點的流量平衡又受到了影響。 我們看V5這個節點流出少了3, 那怎麼辦呢? 最後這條湖, 我們把這個2流出在原來基礎上再多加上3, 改成5, 這樣的話V5節點又是平衡的了, 流出少了3又多了3, 還是平衡的。 請同學們觀察一下, 經過這樣一種調整, 我又得到了一個新的可行流, 這個可行流呢, 它的流量顯然要比原來多了, 多了幾呢? 多了就是剛纔給的這個調整量3, 我們可以看起點, 流出的流量8加上3是11, 也就是說調整完以後, 這個可行流它的流量達到了11, 比原來是5加上3是8, 多了3。 我們再來簡單回顧一下, 剛纔這個可行流是怎麼樣沿着這條正廣鏈進行調整的呢? 就是我們只需要在這條正廣鏈上調, 其他的湖都不用管, 具體的來說, 正向湖上加上一個同樣一個數, 正向湖加一個數, 反向湖呢, 要減去一個數, 正向湖加一個數, 這樣我們看到有加有減, 得到了新的可行流, 還是平衡的, 還是可行的, 正向湖要加流量, 所以我們說, 要求正向湖中接非寶河嘛, 只有非寶河才能加流量嘛, 剛纔反向湖是減流量, 所以我們就要求反向湖接非靈, 非靈才能在原來基礎上再進一步減, 這就是爲什麼正廣鏈這麼來要求, 正向湖非寶河,反向湖非靈, 這是因爲將來我們在調整的時候, 正向湖要加上一個流量, 反向湖要減去一個流量, 好,這是這個例子, 我們再來看一個例子, 又回到原來的網絡圖, 有調整之前的這個網絡圖, 請同學們觀察一下, 或者判斷一下, 看看V1到V2到V4到V6, 這是不是一條正廣鏈呢? 這個顯然也是一條正廣鏈, 我們看到這不僅是一條鏈, 還是一條路, 也就是說, 這條鏈裏面沒有反向湖, 都是正向湖, 所以正向湖就跟着大方向一致的, 我們看都是正向湖, 正向湖那我們也可以啊, 一條鏈正廣鏈裏面可以不存在反向湖, 那也是可以的, 那麼只要要是都是正向湖, 那我們就判斷一下, 看看所有這些正向湖是不是都非飽和呢? 都是非飽和的, 所以這也是一個正廣鏈, 那麼基於這個正廣鏈, 我們也可以對現有的可行流進行調整, 或者進行增廣, 使得流量進一步的擴大, 那麼具體來說, 我們可以在這條正廣鏈上, 都是正向湖嘛, 那就所有的正向湖都加上一個同一個調整量, 也是可以加3, 這也是一種調整辦法, 當然了, 這個還有剛纔那個, 這兩個正廣鏈, 是兩個不同的正廣鏈, 但是呢, 只要任何一個正廣鏈調整完以後, 另外一個正廣鏈, 那就未必還是正廣鏈了, 就剛纔那個正廣鏈, 如果調整完以後, 如果這樣調整完以後, 顯然, 這條鏈, 就下面這條湖這條鏈, 下面這一頁這個鏈, 就不是正廣鏈了, 所以正廣鏈這東西, 它是一個動態調整, 動態變化的, 新調整完以後, 可能原來是正廣鏈的, 也可能就不是了, 這又是一個正廣鏈的例子, 還是這個網絡圖, 我們看這個世界正廣鏈呢, 位1到位2, 到位5, 到位4, 最後到位6, 這個顯然也是一條路, 也是一條路, 沒有反向湖, 那麼看看, 有一條湖是飽和的, 不滿足正廣鏈的定義, 正廣鏈要求正向湖都是非飽和的, 這條湖就飽和了, 所以這個就不是一個正廣鏈, 從這個例子我們也看到, 同樣的一條湖, 就位5到位4, 在剛纔那個例子中呢, 它就是一個反向湖, 而在這個例子, 它是一個正向湖, 所以正向湖, 反向湖, 它在相對正廣鏈來說, 它也是一個相對的概念, 不是一個絕對的概念, 好, 這就是正廣鏈這個定義, 不太好理解, 非常重要, 但是, 我們將來標二法它的基本思想, 也就是在網絡圖中尋找是否存在正廣鏈, 我們會看到, 只要網絡圖中存在正廣鏈, 那麼沒辦法, 我們只能沿着正廣鏈進行調整, 說明當前這個流不是最大流, 那麼調整完以後, 再來檢驗還有沒有正廣鏈, 調整直到最後沒有正廣鏈爲止, 說明當前這個流已經達到最大了, 這是將來我們在標號法中, 將要採用的一個基本思想, 到時候我們還會具體地再來講述這一塊, 這是第二個概念, 接下來我們再來看, 這一節課中也是非常重要的第三組概念, 那就是節急和節量的概念, 這個概念也是不是特別容易理解, 但是也是非常重要, 因爲節, 節怎麼突然要講到一個節呢, 節急節量, 它跟我們前面講到的流流量有沒有關係呢, 這個實際上是有很大的關係的, 我們想象一下,流是想通過這個網絡穿過去, 正向流過去, 而節呢, 就想把它截住, 截斷, 所以它兩個是一對矛盾, 將來我們還會具體地討論流量和節量之間的定量關係, 到時候會發現, 節量跟流量是一個矛盾的關係, 好, 先來看什麼叫節急的概念, 把v, v就是網絡圖的節點急了, 把v分成兩部分, v1和v2, 當然要求這兩部分, v1交v2等於空集, 互相交, 然後呢, v1並v2等於整個點急, 就是說, 這個我們把它叫做對於節點急的一個劃分, 分成兩塊, 這兩塊是分離的, 然後呢, 它的並急呢, 就是整個的節點急和, 這個在集合論裏面叫做一個劃分, 對急和的一個劃分, 前面部分說的是把節點急作爲一個劃分, 在劃分中, 要求vs屬於v1, 就是說起點呢, 要屬於第一個集合, 而vt呢, 屬於v2, 就是說終點呢, 屬於第二個集合, 那我們來看一下什麼叫節急, 則圖急v1到v2, 就稱爲d, d是網絡圖了, d的一個節急, 再進入它, 節急上的容量之和, 稱爲節量, 即爲cv1v2, 那在這要特別解釋一下, 這個符號表示什麼含義呢, 我在這具體地解了一下, 實際上它們表示的就是, 所有這樣的和構成的集合, vi, vj和構成的集合, 其中vi屬於v1集合, 而vj屬於v2集合, 也就是說, 這個符號v1到v2, 表示的是, 所有從v1集合中, 任何一個節點, 正向指向v2集合中, 任何一個節點的和構成的集合, 它是這樣一個意思, 所以所謂網絡圖d的一個節急呢, 我們指的就是, 在網絡中, 首先把它做一個劃分, 把所有的節點分成兩塊, 然後呢, 在這劃分中要求, 起點屬於第一集合, 終點屬於第二塊, 那麼所謂一個節急呢, 就是從第一塊中的任何一個節點, 指向第二塊的任何一個節點, 所有的可能的和, 在做形成的集合吧, 就叫做這個節急, 那麼節急上這些和, 每一條和上不都有一個容量嗎, 容量之和就成爲節量, 這是節急和節量的概念, 好, 下面我們具體的結合這樣一個例題, 來看一下節急和節量, 對於這樣一個網絡圖, 若我令V1等於Vs和V1這兩個節點構成集合, 也就是說, 第一個集合, 有這兩個節點構成這樣的集合, 那麼第二個集合呢, 就剩下的V2, V3, V4, 這三個節點構成的集合, 做這樣一個劃分, 在這個劃分條件下, 請同學們來求一求, 當前的節急是什麼, 節量又是什麼, 按照剛纔的定義, 節急應該是從第一集合指向第二集合的所有和的集合, 有兩條和, 一個是Vs到V2, 一個是V1到Vt, 要注意了, 反向的不算, 反向的, V2到V1和V3到V1, 這個不算, 那麼節量呢, 就是這兩條和上的容量之和, 4加3, 每一條和前面的數字表示容量, 應該是7, 好, 這是這個立體, 我們先休息一會兒。