最大流最小割經典例題_圖割-最大流最小切割的最直白解讀

導讀： 本文主要針對圖像分割中提及的圖割算法作一個最直白的介紹，面向的讀者是所有對這個方面感興趣的同學。從目标上來說，希望所有讀者在閱讀本文後，都能夠自己通過自己熟悉的程式設計語言實作這個算法。

什麼是圖？

本文針對的圖主要是有向圖，具體定義先不給出，先看一個具體例子：

圖1：示例有向圖

上圖就是一個有向圖，不用看官方定義，我們自己就能給出自己的定義：

1.  有向圖包含了頂點與邊；

2.  每一條邊有兩個端點，并且指明了兩個端點之間的指向方向；

3.  每一條邊有對應的值(具體含義與具體的模型化場景有關)。

以上定義雖然不是官方定義，但在本文中，這樣的定義已經足夠使用。為了更好的描述我們總結的定義，是以我給出一個形式化的有向圖定義：

圖2：有向圖形式化定義

上述定義中，V表示為頂點集合，E表示為有向邊集合。當k=0，那麼就表示兩個頂點之間的有向邊無效。

什麼是最大流？

在正式開始介紹最大流之前，必須将前一章節中一個遺留的小問題确定下來，那就是有向邊的數值到底是什麼含義？這裡将其定義為邊的容量，代表了該邊所能通過的最大值。在網絡上有很多類比，比如有些類比把有向圖看作是水管，容量就是能夠通過該水管段最高機關流量。基于此類比，最大流就是從起點到終點所能達到的最高機關流量。為了下文表示上的友善，将容量、最大流都給出一個形式化的定義：

圖3：容量以及最大流定義

(以上兩個公式太醜陋，第一個容量定義公式，可能讓讀者産生是一個固定值得歧義了解，實際想要表達的含義是容量就是有向邊綁定的數值。最大流定義也同樣醜陋，實在不知道該如何表示更加好，是以直接使用了中文描述，對于以上醜陋的表達，我深表歉意。)

最大流的計算方法

為了有效地描述算法，是以必須在具體描述之前再引入幾個定義，(很抱歉，會有這麼多定義産生，但還是懇請讀者耐心一下)：

通路：從圖起點(S)到達圖結束點(T)的路徑，由一系列頂點組成；

通路流量：該通路上所能達到的最大機關流量；

飽和邊：容量等于通路流量的有向邊。

具體算法描述：Step1：初始化最大流Flow=0；

Step2：在圖中找一條通路，如果通路不存在，則結束；

Step3：Flow = Flow+通路流量；

Step4：對通路上所有邊的容量進行更新 Cij = Cij-通路流量；

Step5：跳轉Step2

注意：在上述算法中，當容量為0時，代表該邊已經無效，不能作為通路路經中的邊。

算法的有效性解讀：

這裡使用了解讀，而沒有使用證明，也就表示以下說法是從一種直覺的角度來描述，不是嚴謹的推理證明。算法是有效的，因為當圖中已經沒有通路的時候，已經不可能再增加圖的流量，是以至少已經達到了本次計算過程中的最大流。剩下的另一部份就是如何來說明通路選擇的順序與最終計算的最大流結果無關？如果兩條通路之間是獨立的，那麼先選擇的通路不會對後選擇的通路産生影響。如果兩條通路并非獨立，那麼也是可以簡單證明通路的先後選擇與這兩條通路上的最大流無關。如果兩條通路的可以被證明，那麼将兩條通路看作一條通路，證明N+1情況下同樣成立。

什麼是最小割？

一個割就是一組邊的集合，将給集合邊從圖中邊集合中移除，那麼圖被分割為兩個部分，這兩個部分之間沒有任何邊連接配接。如果說得有點繞口，那麼最簡單來說，一塊肉被從中間隔開，分成兩個部分，中間斷開的連接配接的集合就是割。

最小割就是将圖切割為兩個部分時，代價最小的割的集合，代價就是邊上容量的和(S部分到T部分邊的容量)。還是拿豬肉作類比，最小割就是找到一塊肉連接配接最小的部分，一刀劈開，那個部分的連接配接就是最小割。

如何找到這個最小割？

當一個圖被割分成兩個部分時，不再存在S到T的通路，是以割的代價必定大于等于圖的最大流(這個需要添加額外說明嗎？應該不需要吧，算是非常明顯的結論了吧)。那麼也就是說，割的代碼最小不能小于圖的最大流，也就是割的代價等于圖的最大流。

現在确定了割的代價，但如何去找到這樣一組割？在進行具體算法說明之前，給出額外一個概念：

影響邊：在計算最大流的算法中，會對邊的容量進行修改，而将一條通路中修改後容量為0的邊稱為修改後容量非0邊的影響邊；算法描述：

Step1： 初始化邊影響邊集合；

Step2： 初始化最小割邊集合；

Step3： 記錄邊的原始容量Rij=Cij；

Step3： 尋找一個通路，如果沒有通路，則結束；

Step4： 修正邊的容量Cij = Cij-通路流量；

Step5： 在通路的邊中找一個Cij=0的邊，作為預切割邊；

Step6： 如果預切割邊的容量等于該邊的原始容量(Cij=Rij)，那麼将該邊加入最小割邊集合；否則，找到該邊的所有影響邊，将影響邊從最小割邊集合中移出，将該邊加入最小割邊集合；

Step7： 對通路其他邊記錄影響邊；

算法的有效性解讀：

算法的核心原理就是在尋找最大流的過程中，找出一組邊代價等于最大流，并且能夠将周遊的通路有效分割的邊。

執行個體

按本文描述算法對最初的圖進行最小割求解。

步驟1：尋找第一個通路

圖4：第一條通路标記

紅色字型表示該通路的通路流量。根據算法進行容量修正：

圖5：第一條通路容量修正

修改後的容量是用紅色字型表示。在此通路中，AC邊容量為0，是以将該邊加入最小割邊集合{AC}，同時記錄影響邊資訊，SA的影響邊{AC},CT的影響邊{AC}。

步驟2：尋找第二條通路：

圖6：第二條通路标記

圖7：第二條通路容量修正

此時，最小割邊集合為{AC，DT}

步驟3：尋找第三條通路：

圖8：第三條通路标記

圖9：第三條通路容量修正

此時最小割邊集合為：{AC，DT，DC}

此時，已經不再存在通路，是以目前最小割邊集合就是求解的最小割，其代價為23。

結束語

本文中關于最小割的算法描述沒有參考具體算法，隻是在看最大流算法時自然而然就産生的一個算法，是以此算法沒有被其他文獻描述，本人不禁止讀者将該算法使用在自己的項目以及論文等文檔編寫中，但務必在使用前告知作者。

如果讀者對本文内容還有疑問，可以随時聯系作者。聯系方式如下：

郵箱：[email protected]