什么是網(wǎng)絡流？首先大家要知道網(wǎng)絡流在圖論中是尤為重要的。在這里，給大家介紹網(wǎng)絡流中的一些基本知識。

一、網(wǎng)絡流的概念和定義整理

在圖論中，網(wǎng)絡流（英語：Network flow）是指在一個每條邊都有容量（Capacity）的有向圖分配流，使一條邊的流量不會超過它的容量。

1. 流網(wǎng)絡

流網(wǎng)絡是一種特殊的有向圖。

一個網(wǎng)絡可以表示成一個點集和邊集的集合，即：G=(V,E)。

V表示點，流網(wǎng)絡有兩個特殊點，分別是源點和匯點。

E表示邊，流網(wǎng)絡中每條邊都有一個權(quán)重c，被稱之為容量（Capacity）。

（1）源點 & 匯點

可以把流網(wǎng)絡類比成一個由一條條河流組成的網(wǎng)絡。

源點（Source）有無窮的的流量可以向外流出，匯點（Sink）有無窮的容量容納流量。

（2）凈流

通過流網(wǎng)絡的一條邊的流量（凈流）記為f(u,v)。

可行流

可行流常用 f 表示，在流網(wǎng)絡中滿足以下條件的網(wǎng)絡流稱為可行流。

（1）容量限制（Capacity Constraints）:

（2）流守恒（Flow Conservation）:除了源點和匯點，所有點流出流量之和=流入流量之和

反之，如果只滿足容量限制不滿足流守恒則稱之為偽流。

可行流的流量

每秒從源點流出的凈流量或者每秒從匯點流入的凈流量就是該可行流的流量：

式子也可以用匯點來表示。式子后半部分表示減去流回源點的流量。

最大流

最大流即為最大可行流，最大流的流量是所有可行流中最大的。

2. 殘留網(wǎng)絡 Residual Network

一個顯示了流及容量的流網(wǎng)絡及對應的殘留網(wǎng)絡

殘留網(wǎng)絡是由流網(wǎng)絡G和可行流 f 決定的一個流網(wǎng)絡，記為，它顯示可用的容量的多少。

殘留網(wǎng)絡的點等于流網(wǎng)絡G的點：

殘留網(wǎng)絡的邊等于原本的邊和反向邊之和

每條邊的容量可以表示為：

分別表示剩余可用流量和反向流量（可以退回的流量）。

殘留網(wǎng)絡也是一個流網(wǎng)絡，因此也有可行流的概念

定理：原網(wǎng)絡的可行流 f 加上 殘留網(wǎng)絡的一個可行流 f′ 也是原網(wǎng)絡G的一個可行流 ：|f+f′|=|f|+|f′|

3. 增廣路徑 Augmenting Path

增廣路是一條路徑 (u1,u2,?,uk)，而 u1=s 、uk=t及 cf(ui,ui+1)>0，這表示沿這條路徑傳送更多流是可能的。

定理：一個可行流當且僅當剩余網(wǎng)絡 Gf 沒有增廣路時處于最大流。

4. 割 Cut

割將一個流網(wǎng)絡G分為兩個圖S和T，記為[S,T]，滿足：S∪T=G

且：S∩T=?

源點滿足 s∈S，匯點滿足 t∈T

（1）割的容量

所有從S指向T的有向邊的容量之和為割的容量：

從T指向S的邊則不被計算。

（2）割的流量

類似割的容量，割的流量被定義為：

可以注意到，容量和流量的定義不對稱，容量只考慮正向邊，流量考慮雙向邊。

（3）最小割

容量最小的割即為最小割

（4）割的性質(zhì)

對于任意割，割的容量大于等于割的流量?[S,T] f(S,T)≤c(S,T)

一個割只有一個容量，但可能有很多個流量（可行流），割的容量大于所有這個割的流量。

觀察一下容量和流量的表達式，這條性質(zhì)是很容易理解的。

對于任意一個可行流，和任意一個割，可行流的流量等于割的流量|f|=f(S,T)

這個可以形象的理解，從源點流出的凈流量一定全部流向了匯點，而割將源點和匯點分為了兩部分，所以這些凈流量一定流經(jīng)了割。

對于任意可行流，任意割，可行的流的流量一定小于割的容量

第一條性質(zhì)再結(jié)合第二條性質(zhì)，可以得到：|f|=f(S,T)≤c(S,T)

也就是：|f|≤c(S,T)

由于 f 是任意的流，割是任意的割，因此最大流的流量一定小于等于最小割的容量。后面會證明，如果是這種情況的話，這里其實是取等號的。

最大流最小割定理：網(wǎng)絡流的基石，核心概念

首先列出三個命題：

對于一個流網(wǎng)絡G

（1）f 是最大流

（2）Gf中不存在增廣路

（3）?[S,T],|f|=c(S,T)?[S,T],|f|=c(S,T)

最大流最小割定理證明了這三個命題是等價的。

1?2

首先證明1式可以推得2式，使用反證法

假定 f 是G的最大流，且殘留網(wǎng)絡 Gf 存在增廣路，那么 Gf 中必定存在一個流量大于0的可行流 f′。

由定理 |f+f′|=|f|+|f′| ，可得 |f+f′|>f，這與 f 是最大流相矛盾，因此 Gf 中不存在增廣路，證畢。

2?3

嘗試構(gòu)造一個割，在殘留網(wǎng)絡 Gf 中從源點s沿著正權(quán)路徑遍歷，能到達的所有點組成 S ，其他點組成 T 。這樣就構(gòu)造了一個合法的割。注意，這里的構(gòu)造出的割是針對原圖的割，而不是殘留網(wǎng)絡。

在 S 中任取一點 x ，在 T 中任取一點 y ，可以證明 f(x,y)=c(x,y)，且 f(y,x)=0：

（1）假定 f(x,y)<c(x,y)，那么在殘留網(wǎng)絡中就存在一條c(x,y)?f(x,y)>0的邊，按照構(gòu)造割時候的方法，y 點應該在 S 中，這與假設矛盾，所以 f(x,y)=c(x,y)。

（2）假定 f(y,x)≠0，由于殘留網(wǎng)絡會建反向邊，所以在殘留網(wǎng)絡中，必定存在 f′(x,y)>0，同樣按照構(gòu)造割的方法，y 點應該在 S 中，這與假設矛盾，所以 f(y,x)=0。

前面提到，對于任意一個可行流，和任意一個割，可行流的流量等于割的流量：|f|=f(S,T)

所以：

又因為在構(gòu)造的割中，f(x,y)=c(x,y),f(y,x)=0，所以：

3?1

這里要證明的是3式中的 f 就是最大流。

不妨記最大流為F

首先|F|≥|f|，又因為 |f|=c(S,T)≥|F|，所以 |F|=|f|，證畢。

這個式子還可以繼續(xù)推導，記最小割為

又因為最小割的容量大于等于最大流的流量

所以最小割的容量等于最大流的流量

和起來就是：

1?2?3?1

所以這三個命題是等價的，這就是最大流最小割定理。

二、網(wǎng)絡流的常見問題

網(wǎng)絡流問題中常見的有以下三種：最大流，最小割，費用流。

（1）最大流

我們有一張圖，要求從源點流向匯點的最大流量（可以有很多條路到達匯點），就是我們的最大流問題。

（2）最小費用最大流

最小費用最大流問題是這樣的：每條邊都有一個費用，代表單位流量流過這條邊的開銷。我們要在求出最大流的同時，要求花費的費用最小。

（3）最小割

割其實就是刪邊的意思，當然最小割就是割掉  條邊來讓  跟  不互通。我們要求  條邊加起來的流量總和最小。這就是最小割問題。