最大流的標記演算法

A. Ford-Fulkerson演算法正確性證明

圖論中有一類重要的問題就是流量問題。求一個流網路的最大流量。那麼可以用的方法有很多，比較經典的是FF(Ford-Fulkerson)演算法。本文主要描述FF演算法正確性的證明。涉及到的知識點：

其中我們用最大流-最小割定理來證明FF演算法的正確性

一個流網路的定義如下：

流網路 是一個有向圖。具有如下屬性：

流網路中有兩個重要的頂點 ，其中s叫做源點（source），t叫做匯點（sink）。流網路中的流是從源地點到匯點。流網路中的所有流都從源點出發，然後最終都流入匯點。

如圖就是一個流網路的示意圖：

網路G的流是一個如下的一個函數：

流具有如下性質：

一個流的值用 表示

表示從 流出的所有值減去流入 的所有值

我們定義一個流網路的割（cut）為：

其中

就是將一個圖分割為兩個不相交的集合。s在其中一個集合中，t在另外一個集合中，並且兩個集合中的點是不相連的

我們引入一些網路流割的屬性：

為了證明FF的正確性，我們需要引入一個引理來輔助證明過程

設 為流網路中的一個流，橫跨任何切割的凈流量都相同，都為 ，即流的值。即證明

證明有兩種方式，一種是嚴格的數學證明，另外一種是直觀上的感受，如果對於數學證明沒有興趣的話，那麼可以直接去看直觀上的證明。

對於 流量守恆 特性，我們有： ，

根據流的值的定義：

，將上面的式子針對每一個 相加得到

我們可以看到，這個等式前面括弧的一部分就是 ，後面的一部分根據 流量守恆 知道為0

因此

證畢。

根據流的定義，我們知道一個流網路 的流 的值是所有從 流出的流的和，減去所有進入 的流。那麼從 出去的流，最後都會進入到 中。而我們任意的一個切割，都將這個網路分成了兩個不相連的部分， 位於一部分 位於一部分。如果流想要從 到 的話，那麼必須經過這個切割。而流網路是沒有損耗的，因此經過這個切割的流的值，一定等於從 中流出的值和流入值的差，也就是整個網路的流的值。即 證畢。

有了引理1，我們就可以有推論1：網路的流小於或等於網路任意切割 的切割容量，即

證明推論1:

根據引理1，我們知道。網路的流等於任意橫跨切割的流，而再根據 容量限制 我們知道橫跨任意切割的流小於等於切割的容量。傳遞過來，我們就有，網路的流小魚等於任意切割的容量，即

證畢。

有了推論1，我們就可以很明顯的得出。一個網路的最大流的值等於一個最小切割的容量。即最大流-最小切割定理。

設 為流網路 中的一個流，該流網路的源點為 ，匯點為 ，則下面的條件是等價的：

(1) 是 的一個最大流
(2) 殘存網路 不包括任何增廣路徑
(3) ，其中 是流網路 的某個切割

我們可以看到，FF演算法在可以終止的前提下，終止的條件是（2），我們假設在（2）的前提下有（1），也就是 我們就是需要證明

我們使用反證法來證明。如果一個 是最大流，但是 中存在增廣路徑，那麼根據FF演算法就可以增加網路的流的大小，那麼這個流就不是最大流了。與我們最初的假設矛盾，因此 是正確的

中不存在增廣網路，那麼我們就可以將 切割為 定義 ，那麼顯然有 。 我們對於 會有下面兩個推論：

有上面的兩個推論，我們結合跨切割的流的定義有：

根據引理1，我們有

因此 正確

根據推論1，我們知道 ，而 中的等於前提，即 即表明了這是一個最大流。因此 是正確的

經過上面的證明我們可以看到， 是一個獨立的條件，那麼就會有 這樣的證明鏈條，也就有 也就是我們要證明的結論，即FF演算法的正確性--在沒有殘差網路的情況下得到的流一定是最大流。事實上 互為充要條件。

證畢。

B. 薩普的SAP演算法

最短增廣路演算法(Shortest Augmenting Path Algorithm)，是網路流中求最大流的經典演算法之一，即每次尋找包含弧的個數最少的增廣路進行增廣，可以證明，此演算法最多隻需要進行mn/2次增廣。並且引入距離標號的概念，可以在O(n)的時間里找到一條最短增廣路。最終的時間復雜度為O(n^2m)，但在實踐中，時間復雜度遠遠小於理論值（特別是加了優化之後），因此還是很實用的。 對於每個頂點i賦予一個非負整數值d(i)來描述i到t的「距離」遠近，稱它為距離標號，並且滿足以下兩個條件： 1. d(t)=0 2. 對於殘留網路Gf中的一條弧(i,j)，d(i)≤d(j)+1。
允許弧和允許路：
如果殘留網路Gf中的一條弧(i,j)滿足d(i)=d(j)+1，我們稱(i,j)是允許弧，由允許弧組成的一條s-t路徑是允許路。顯然，允許路是殘留網路Gf中的一條最短增廣路。當找不到允許路的時候，我們需要修改某些點的d(i)。 可以注意到一個事實：如果說在某次迭代中從i出發的弧(i,j)不是允許弧，則在頂點i的標號修改之前(i,j)都不可能是允許弧。（因為d(i)不變，d(j)不減且d(i)<d(j)+1）這樣，在查找允許弧的時候只需要從上一次找到的允許弧開始找。所以我們增加「當前弧」這個數據結構，記錄當前頂點找到的允許弧，只有在修改這個頂點標號時才會更改這個頂點的當前弧。
最後附上我寫的部分程序，用的非遞歸結構
Fillchar(last, Sizeof(last), $ff); Fillchar(first, Sizeof(first), $ff);
Procere add(x, y, z, k: Longint);
Begin
Inc(num);
e[num].x := x;
e[num].y := y;
e[num].z := z;
e[num].next := k;
If first[x]=-1 Then first[x] := num;
If last[x]=-1 Then last[x] := num Else Begin
e[last[x]].next := num;
last[x] := num;
End;
End;
這個加邊，用數組模擬鏈表的鄰接表
now := First;
i := 1;
c := maxlongint;
vh[0] := n;
While dis[1]<n Do Begin（dis存距離標號）
fc[i] := c;（fc用於遞歸c的值）
ff := False;（表示是否找到允許弧）
k := now[i];（now存當前弧）
While k<>-1 Do Begin
j := e[k].y;
If (e[k].z>0) And (dis[j]+1=dis[i]) Then Begin
ff := True;
now[i] := k;
If e[k].z<c Then c := e[k].z;
pre[j] := k;
i := j;
If i=n Then Begin（找到增廣路）
Inc(ans, c);
While i<>1 Do Begin
dec(e[pre[i]].z, c);
Inc(e[pre[i] xor 1].z, c);
i := e[pre[i]].x;
End;
c := Maxlongint;
End;
Break;
End;
k := e[k].next;
End;
If ff Then Continue;
min := n-1;（重新標號）
k := First[i];
While (k<>-1) Do Begin
j := e[k].y;
If (e[k].z>0) And (dis[j]<min) then Begin
tj := k;
min := dis[j];
End;
k := e[k].next;
End;
now[i] := tj;
dec(vh[dis[i]]);（gap）
If vh[dis[i]]=0 Then Break;
dis[i] := min+1;
Inc(vh[dis[i]]);
If i<>1 Then Begin
i := e[pre[i]].x;
c := fc[i];
End;
End;

C. 網路最大流演算法通常應用在什麼方面

首先是網路流中的一些定義：
V表示整個圖中的所有結點的集合.
E表示整個圖中所有邊的集合.
G = (V,E) ,表示整個圖.
s表示網路的源點,t表示網路的匯點.
對於每條邊(u,v),有一個容量c(u,v) (c(u,v)>=0)，如果c(u,v)=0，則表示(u,v)不存在在網路中。相反，如果原網路中不存在邊(u,v)，則令c(u,v)=0.
對於每條邊(u,v),有一個流量f(u,v).

一個簡單的例子.網路可以被想像成一些輸水的管道.括弧內右邊的數字表示管道的容量c,左邊的數字表示這條管道的當前流量f.

網路流的三個性質：
1、容量限制: f[u,v]<=c[u,v]
2、反對稱性：f[u,v] = - f[v,u]
3、流量平衡: 對於不是源點也不是匯點的任意結點,流入該結點的流量和等於流出該結點的流量和。
只要滿足這三個性質,就是一個合法的網路流.
最大流問題，就是求在滿足網路流性質的情況下，源點 s 到匯點 t 的最大流量。

求一個網路流的最大流有很多演算法 這里首先介紹 增廣路演算法（EK）
學習演算法之前首先看了解這個演算法中涉及到的幾個圖中的定義：

**殘量網路
為了更方便演算法的實現，一般根據原網路定義一個殘量網路。其中r(u,v)為殘量網路的容量。
r(u,v) = c(u,v) – f(u,v)
通俗地講：就是對於某一條邊（也稱弧），還能再有多少流量經過。
Gf 殘量網路,Ef 表示殘量網路的邊集.

這是上面圖的一個殘量網路。殘量網路（如果網路中一條邊的容量為0,則認為這條邊不在殘量網路中。
r(s,v1)=0,所以就不畫出來了。另外舉個例子：r(v1,s) = c(v1,s) – f(v1,s) = 0 – (-f(s,v1)) = f(s,v1) = 4.
其中像(v1,s)這樣的邊稱為後向弧,它表示從v1到s還可以增加4單位的流量。
但是從v1到s不是和原網路中的弧的方向相反嗎？顯然「從v1到s還可以增加4單位流量」這條信息毫無意義。那麼，有必要建立這些後向弧嗎？
顯然，第1個圖中的畫出來的不是一個最大流。
但是，如果我們把s -> v2 -> v1 -> t這條路徑經過的弧的流量都增加2,就得到了該網路的最大流。
注意到這條路徑經過了一條後向弧:(v2,v1)。
如果不設立後向弧，演算法就不能發現這條路徑。
**從本質上說，後向弧為演算法糾正自己所犯的錯誤提供了可能性，它允許演算法取消先前的錯誤的行為（讓2單位的流從v1流到v2)

注意,後向弧只是概念上的,在程序中後向弧與前向弧並無區別.

**增廣路
增廣路定義：在殘量網路中的一條從s通往t的路徑，其中任意一條弧(u,v)，都有r[u,v]>0。

如圖綠色的即為一條增廣路。

看了這么多概念相信大家對增廣路演算法已經有大概的思路了吧。