最大流最小割定理 是最優化理論 的定理。根據該定理,在一個網絡流 中,從源點 到匯點 的最大的流量,等於它的最小割中每一條邊的容量之和。「割」指的是一種邊 的集合,如果移除這個集合的全部邊,就會斷開源點和匯點的連接。
最大流最小割定理 是線性規劃 中的對偶問題 的一種特殊情況,並且可以用來推導門格爾定理 和König–Egerváry定理 。[ 1]
定義
最大流和最小割定理是圖論的一部分,因此為了準確定義,我們需要先定義圖、流、割,然後再定義這個定理。
圖
設
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
為一個有向圖,其中有一個起源點
s
{\displaystyle s}
和一個超匯點
t
{\displaystyle t}
,代表
s
{\displaystyle s}
是所有流的源頭,
t
{\displaystyle t}
是所有流的終點。這個圖的每一條邊都有一個容量 c : E → R + ,記做
c
u
v
{\displaystyle c_{uv}}
或者
c
(
u
,
v
)
{\displaystyle c(u,v)}
,代表著能通過邊
(
u
,
v
)
{\displaystyle (u,v)}
的最大流量。
最大流
定義: 流量 代表一種映射
f
:
E
→
R
+
{\displaystyle f:E\rightarrow \mathbb {R} ^{+}}
,記做
f
u
v
{\displaystyle f_{uv}}
或者
f
(
u
,
v
)
{\displaystyle f(u,v)}
,代表通過邊
(
u
,
v
)
{\displaystyle (u,v)}
的流量。每一條邊所通過的流有以下兩個限定條件:
流量限制 :
f
u
v
≤
c
u
v
∀
(
u
,
v
)
∈
E
.
{\displaystyle f_{uv}\leq c_{uv}\quad \forall \,(u,v)\in E.}
也就是說,一條邊上的流量不可以超過它的容量。
流量守恆 :
∑
{
u
:
(
u
,
v
)
∈
E
}
f
u
v
=
∑
{
w
:
(
v
,
w
)
∈
E
}
f
v
w
∀
v
∈
V
∖
{
s
,
t
}
.
{\displaystyle \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}\quad \forall \,v\in V\setminus \{s,t\}.}
也就是說,除了源點和匯點以外,進入一個節點的流量等於流出這個節點的流量,節點內不能保存流。
規定在一個圖中,流的值是
|
f
|
=
∑
v
:
(
s
,
v
)
∈
E
f
s
v
=
∑
v
:
(
v
,
t
)
∈
E
f
v
t
.
{\displaystyle |f|=\sum \nolimits _{v:(s,v)\in E}f_{sv}=\sum \nolimits _{v:(v,t)\in E}f_{vt}.}
也就是說,一個圖的流是自其源點流出的流量之和,也是向其匯點流入的流量之和。或者說,由源點向匯點移動多少內容,這個圖的流就是多少。
最大流問題 : 計算
|
f
|
{\displaystyle |f|}
的最大值,即從
s
{\displaystyle s}
到
t
{\displaystyle t}
的最大流量。
最小割
定義: s-t割
C
=
(
S
,
T
)
{\displaystyle C=(S,T)}
將圖
G
{\displaystyle G}
完全劃分 為兩部分,使得
s
∈
S
,
t
∈
T
,
{\displaystyle s\in S,t\in T,}
也就是一側有源,一側有匯。
C
{\displaystyle C}
的割集
X
C
{\displaystyle X_{C}}
是
{
(
u
,
v
)
∈
E
:
u
∈
S
,
v
∈
T
}
.
{\displaystyle \{(u,v)\in E\ :\ u\in S,v\in T\}.}
也就是說,一條邊若且唯若騎在這個劃分方法上,一個節點位於劃分出來的源側,另一個位於匯側,那麼它包含在
X
C
{\displaystyle X_{C}}
里。因此如果
C
{\displaystyle C}
的割集是空集,或者我們把一個割集裡的邊全都從圖中拿走,則
|
f
|
=
0
{\displaystyle |f|=0}
。通俗地說,割集就是一個圖的斷面,而割則是劃分斷面的方法。
規定在一個圖中,s-t割的容量 是
c
(
S
,
T
)
=
∑
(
u
,
v
)
∈
X
C
c
u
v
=
∑
(
i
,
j
)
∈
E
c
i
j
d
i
j
,
{\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in X_{C}}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},}
其中當
i
∈
S
,
j
∈
T
{\displaystyle i\in S,j\in T}
時,
d
i
j
{\displaystyle d_{ij}}
為
1
{\displaystyle 1}
, 否則為
0
{\displaystyle 0}
。
通俗地說,割的容量就是斷面中所有邊的總容量。
最小 s-t 割問題: 計算
c
(
S
,
T
)
{\displaystyle c(S,T)}
的最小值。即找到一種割法,使割的容量最小。也就是說,找到通過能力最弱的斷面。
主定理
可以證明一切流都不能超過任何s-t割,所以經過圖的最大流就是圖的最小割。我們直觀上就可以知道,通過能力最弱的斷面就是整個網絡的最大流量。這個理論把最大流問題 和最小割問題聯繫了起來。
線性規劃公式
最大流最小割問題可以被看做為一對線性規劃對偶問題。[ 2]
Max-flow (Primal)
Min-cut (Dual)
variables
f
u
v
{\displaystyle f_{uv}}
∀
(
u
,
v
)
∈
E
{\displaystyle \forall (u,v)\in E}
[a variable per edge]
d
u
v
{\displaystyle d_{uv}}
∀
(
u
,
v
)
∈
E
{\displaystyle \forall (u,v)\in E}
[a variable per edge]
z
v
{\displaystyle z_{v}}
∀
v
∈
V
∖
{
s
,
t
}
{\displaystyle \forall v\in V\setminus \{s,t\}}
[a variable per non-terminal node]
objective
maximize
∑
v
:
(
s
,
v
)
∈
E
f
s
v
{\displaystyle \sum \nolimits _{v:(s,v)\in E}f_{sv}}
[max total flow from source]
minimize
∑
(
u
,
v
)
∈
E
c
u
v
d
u
v
{\displaystyle \sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}}
[min total capacity of edges in cut]
constraints
subject to
f
u
v
≤
c
u
v
∀
(
u
,
v
)
∈
E
∑
u
f
u
v
−
∑
w
f
v
w
=
0
v
∈
V
∖
{
s
,
t
}
{\displaystyle {\begin{aligned}f_{uv}&\leq c_{uv}&&\forall (u,v)\in E\\\sum _{u}f_{uv}-\sum _{w}f_{vw}&=0&&v\in V\setminus \{s,t\}\end{aligned}}}
[a constraint per edge and a constraint per non-terminal node]
subject to
d
u
v
−
z
u
+
z
v
≥
0
∀
(
u
,
v
)
∈
E
,
u
≠
s
,
v
≠
t
d
s
v
+
z
v
≥
1
∀
(
s
,
v
)
∈
E
,
v
≠
t
d
u
t
−
z
u
≥
0
∀
(
u
,
t
)
∈
E
,
u
≠
s
d
s
t
≥
1
if
(
s
,
t
)
∈
E
{\displaystyle {\begin{aligned}d_{uv}-z_{u}+z_{v}&\geq 0&&\forall (u,v)\in E,u\neq s,v\neq t\\d_{sv}+z_{v}&\geq 1&&\forall (s,v)\in E,v\neq t\\d_{ut}-z_{u}&\geq 0&&\forall (u,t)\in E,u\neq s\\d_{st}&\geq 1&&{\text{if }}(s,t)\in E\end{aligned}}}
[a constraint per edge]
sign constraints
f
u
v
≥
0
∀
(
u
,
v
)
∈
E
{\displaystyle {\begin{aligned}f_{uv}&\geq 0&&\forall (u,v)\in E\\\end{aligned}}}
d
u
v
≥
0
∀
(
u
,
v
)
∈
E
z
v
∈
R
∀
v
∈
V
∖
{
s
,
t
}
{\displaystyle {\begin{aligned}d_{uv}&\geq 0&&\forall (u,v)\in E\\z_{v}&\in \mathbb {R} &&\forall v\in V\setminus \{s,t\}\end{aligned}}}
最大流的線性規劃公式是容易理解的,對於最小割的線性規劃公式的理解如下:
d
u
v
=
{
1
,
u
∈
S
,
v
∈
T
0
,
Otherwise
{\displaystyle d_{uv}={\begin{cases}1,&u\in S,v\in T\\0,&{\text{Otherwise}}\end{cases}}}
z
u
=
{
1
,
u
∈
S
0
,
Otherwise
{\displaystyle z_{u}={\begin{cases}1,&u\in S\\0,&{\text{Otherwise}}\end{cases}}}
最小化目標是使在割中的邊最小。
下列限制保證了這些變量可以確保一個合法的割。
限制
d
u
v
−
z
u
+
z
v
≥
0
{\displaystyle d_{uv}-z_{u}+z_{v}\geq 0}
(即
d
u
v
≥
z
u
−
z
v
{\displaystyle d_{uv}\geq z_{u}-z_{v}}
) 確保了對兩個非源點或匯點 u,v , 如果u 在 S 中 且 v 在 T 中, 那麼邊 (u ,v )一定會被記在割中 (
d
u
v
≥
1
{\displaystyle d_{uv}\geq 1}
)。
限制
d
s
v
+
z
v
≥
1
{\displaystyle d_{sv}+z_{v}\geq 1}
(即
d
s
v
≥
1
−
z
v
{\displaystyle d_{sv}\geq 1-z_{v}}
) 確保了如果 v 在 T 中, 那麼邊 (s,v) 一定會被記在割中。
限制
d
u
t
−
z
u
≥
0
{\displaystyle d_{ut}-z_{u}\geq 0}
(即
d
u
t
≥
z
u
{\displaystyle d_{ut}\geq z_{u}}
) 確保了 u 在 S 中, 那麼邊 (u,t) 一定會被記在割中。
需要注意的是,這是一個最小化問題,我們不需要確保一條邊不在割里,我們只要保證每條應當在割里的邊被計算了。
注意到在給定的 s-t 割
C
=
(
S
,
T
)
{\displaystyle C=(S,T)}
中,如果
i
∈
S
{\displaystyle i\in S}
那麼
z
i
=
1
{\displaystyle z_{i}=1}
並且 0 反之。 所以
z
s
{\displaystyle z_{s}}
應該等於 1 並且
z
t
{\displaystyle z_{t}}
應該等於0。由線性規劃 中的強對偶定理 推得最大流最小割問題 中的等式,也就是說如果原問題有一個最優解 x *,則對應問題也有一個最優解 y * ,並且兩個解相等。
舉例
一個流量等於s-t 割的容量的流網絡
上圖是一個網絡,上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點, 從而形成了一個割集包含圖中虛線的 s-t 割,並且其容量為 7,與流量相同。故由大流最小割定理知,前述的流與 s-t 割皆達到流量及容量的極值。
應用
廣義最大流最小割定理
額外規定映射
c
:
V
→
R
+
{\displaystyle c\colon V\rightarrow R^{+}}
為點的容量,記做 c(v),使得一個流 f 不只要滿足邊的流量限制與流量守恆,還要滿足點的流量限制,即
∀
v
∈
V
∖
{
s
,
t
}
:
∑
{
u
∈
V
∣
(
u
,
v
)
∈
E
}
f
u
v
≤
c
(
v
)
.
{\displaystyle \forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u\in V\mid (u,v)\in E\}}f_{uv}\leq c(v).}
換句話說,流過 v 點的總流量不能超過 v 的容量 c(v)。一個 s-t 割 的定義為一個包含一些點和邊的集合,滿足與任一條由 s 到 t 的路徑皆不互斥。並且 s-t 割的容量 定義成所有點和邊的容量總和。
在此定義之下,廣義最大流最小割定理 的敘仍為流量的最大值等於所有 s-t 割的容量最小值。
門格爾定理
不共邊路徑問題為給定無向圖
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
及兩頂點 s、t,求從 s 到 t 彼此沒有共同邊的路徑數量的最大值。
門格爾定理的敘述為從 s 到 t 彼此沒有共同邊的路徑數量的最大值等於在所有 G 的 s-t 割(以原本的定義)中,頂點分別在不同集合的邊數的最小值。
計畫選擇問題
計畫選擇問題的網絡型態
計畫選擇問題敘述如下:當下有 n 個計畫
p
1
,
…
,
p
n
{\displaystyle p_{1},\dots ,p_{n}}
可以被實施、m 種設備
q
1
,
…
,
q
m
{\displaystyle q_{1},\dots ,q_{m}}
可以被購買,要執行計畫必須擁有該計畫要求的設備,執行計畫
p
i
{\displaystyle p_{i}}
可獲得
r
(
p
i
)
{\displaystyle r(p_{i})}
的收益,但購買設備
q
j
{\displaystyle q_{j}}
要支付
c
(
q
j
)
{\displaystyle c(q_{j})}
的費用。如何選擇執行計畫並購買所需設備以獲得淨利的最大值?
設 P 為不 被執行的計畫的集合,Q 為所購買的設備,則問題變成求最大值
max
P
,
Q
∑
i
=
1
n
r
(
p
i
)
−
∑
p
i
∈
P
r
(
p
i
)
−
∑
q
j
∈
Q
c
(
q
j
)
{\displaystyle \max _{P,Q}\sum _{i=1}^{n}r(p_{i})-\sum _{p_{i}\in P}r(p_{i})-\sum _{q_{j}\in Q}c(q_{j})}
注意到
∑
i
r
(
p
i
)
{\textstyle \sum _{i}r(p_{i})}
與 P、Q 的選擇無關,故只需求後兩項和的最小值,即
min
P
,
Q
∑
p
i
∈
P
r
(
p
i
)
+
∑
q
j
∈
Q
c
(
q
j
)
{\displaystyle \min _{P,Q}\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j})}
現在考慮一個網絡,起源點 s 連接到 n 個點
p
1
,
…
,
p
n
{\displaystyle p_{1},\dots ,p_{n}}
,邊的容量分別為
r
(
p
i
)
{\displaystyle r(p_{i})}
,超匯點 t 連接到 m 個點
q
1
,
…
,
q
m
{\displaystyle q_{1},\dots ,q_{m}}
,邊的容量分別為
c
(
q
j
)
{\displaystyle c(q_{j})}
,若執行任務
p
i
{\displaystyle p_{i}}
需購買設備
q
j
{\displaystyle q_{j}}
,則在
p
i
{\displaystyle p_{i}}
、
q
j
{\displaystyle q_{j}}
之間連上一條容量為無限大的邊,若不需購買設備,則不連上邊。則
∑
p
i
∈
P
r
(
p
i
)
+
∑
q
j
∈
Q
c
(
q
j
)
{\textstyle \sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j})}
對應到一個 s-t 割的容量,其中的兩個集合是要執行的計畫與要購買的設備和它的餘集,也就是
{
s
}
∪
(
P
′
∖
P
)
∪
Q
、
{
t
}
∪
P
∪
(
Q
′
∖
Q
)
{\displaystyle \{s\}\cup (P'\setminus P)\cup Q{\text{、 }}\{t\}\cup P\cup (Q'\setminus Q)}
在此,
P
′
=
{
p
1
,
…
,
p
n
}
{\displaystyle P'=\{p_{1},\dots ,p_{n}\}}
,
Q
′
=
{
q
1
,
…
,
q
m
}
{\displaystyle Q'=\{q_{1},\dots ,q_{m}\}}
。於是,原問題轉成求該圖的最大流問題 ,並且可以藉由各種算法求得其極值。
以下給出一個計畫選擇問題的例子,右圖是該問題對應到的網絡。
計畫收入 r (pi )
設備價格 c (qj )
備註
1
100
200
執行計畫 p 1 須購買設備 q 1 、q 2 。
2
200
100
執行計畫 p 2 須購買設備 q 2 。
3
150
50
執行計畫 p 3 須購買設備 q 3 。
該網絡的最小 s-t 割是選擇計畫 p 2 、p 3 與設備 q 2 、q 3 ,容量為 250。三個計劃的總收益是 450,因此最大淨利為 450 − 250 = 200。
以上解法可以理解為將計畫所給予的收益流過所需設備,如果無法流滿設備至 t 的邊,代表執行計畫不合成本,最小割將選擇穿過 s 到計畫的邊而非穿過設備到 t 的邊。
影像分割問題
Each black node denotes a pixel.
設原圖有 n 像素,想要把該圖分割為前景和背景,並且將 i 像素歸類為前景有效益 fi ,歸類為背景有效益 bi ,但是若 i、j 像素相鄰且被歸類為不同塊,則會減少 pij 的效益。求將該圖分割為前後景的最有效益方法。
令 P 為前景的集合,Q 為背景的集合,於是問題轉化成求最大值
max
P
,
Q
∑
i
∈
P
f
i
+
∑
i
∈
Q
b
i
−
∑
i
∈
P
,
j
∈
Q
∨
j
∈
P
,
i
∈
Q
p
i
j
{\displaystyle \max _{P,Q}\sum _{i\in P}f_{i}+\sum _{i\in Q}b_{i}-\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}}
因為 fi 、 bi 的總合是與 P、Q的選取無關,因此等價於求以下最小值
min
P
,
Q
∑
i
∈
Q
f
i
+
∑
i
∈
P
b
i
+
∑
i
∈
P
,
j
∈
Q
∨
j
∈
P
,
i
∈
Q
p
i
j
{\displaystyle \min _{P,Q}\sum _{i\in Q}f_{i}+\sum _{i\in P}b_{i}+\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}}
以上的最小值問題可以被描述為一個網絡的最小割問題,其中該網絡如右圖,以橘點為起源點;紫點為超匯點。各個像素被描述為網絡的頂點,起源點至第 i 個像素連上一條容量為 fi 的有向邊 ;第 i 個像素至超匯點連上一條容量為 bi 的有向邊 。相鄰的像素 i、j 之間連上來回兩條容量為 pij 的有向邊 。則一個 s-t 割代表一種將部分像素歸類為前景 P、其餘歸類為背景 Q 的安排。
歷史
最大流最小割問題 最早在1956年被P. Elias, A. Feinstein,和 C.E. Shannon 證明[ 3] , 並且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年證明了該定理[ 3] 。
證明
同之前的設定,G = (V , E ) 是一個網絡(有向圖) ,s 點和 t 點分別為 G 的起源點和超匯點。
將所有流考慮成一個歐式空間 的有界 閉 子集,滿足流量限制與流量守恆,而流量是一個連續函數,因此有極大值 |f| 。
設 f 達到最大流,令 (Gf ) 是 f 的殘留網絡,定義
A:在 (Gf ) 中可以從 s 出發到達的點
Ac :A 以外的點,即 V − A
換句話說,v∈A 若且唯若 s 可以流出更多流量到 v。
我們宣稱
|
f
|
=
c
(
A
,
A
c
)
{\displaystyle |f|=c(A,A^{c})}
,其中該 s-t 割的容量 定義為
c
(
S
,
T
)
=
∑
(
u
,
v
)
∈
(
S
×
T
)
∩
E
c
u
v
{\displaystyle c(S,T)=\sum \nolimits _{(u,v)\in (S\times T)\cap E}c_{uv}}
.
由於
|
f
|
{\displaystyle |f|}
的大小等於所有流出集合 A 的流量總和減所有流入集合 A 的流量總和,故
|
f
|
≤
c
(
A
,
A
c
)
{\displaystyle |f|\leq c(A,A^{c})}
,並且等號成立若且唯若
所有從 A 流向 Ac 的邊流量均已達飽和。
所有從 Ac 流向 A 的邊流量均為 0。
我們用反證法分別證明以上兩點:
假設存在從 A 流向 Ac 的邊
(
x
,
y
)
∈
A
×
A
c
{\displaystyle (x,y)\in A\times A^{c}}
並未達到飽和,即
f
(
x
,
y
)
<
c
x
y
{\displaystyle f(x,y)<c_{xy}}
。因此,可以從 x 流更多 的流量到 y,(x,y) 是 Gf 的一條邊。由 x∈A 知 Gf 圖中有一條中的路徑從 s 到 x,其中只經過 A 中的點, 所以 y∈A,產生矛盾。是故所有從 A 流向 Ac 的邊流量均已達飽和。
假設存在從 Ac 流向 A 的邊
(
y
,
x
)
∈
A
c
×
A
{\displaystyle (y,x)\in A^{c}\times A}
其流量不為 0,即
f
(
x
,
y
)
>
0
{\displaystyle f(x,y)>0}
。因此,可以從 y 流更少 的流量到 x,(x,y) 是 Gf 的一條邊。由 x∈A 知 Gf 圖中有一條中的路徑從 s 到 x,其中只經過 A 中的點, 所以 y∈A,產生矛盾。是故所有從 Ac 流向 A 的邊流量均為 0。
於是,聲稱得證。
由於流量恆不超過容量,|f| 是容量的下界,所以
c
(
A
,
A
c
)
{\displaystyle c(A,A^{c})}
是容量的最小值,由聲稱知,最大流最小割定理得證。
參見
參考文獻
^ Dantzig, G.B.; Fulkerson, D.R. On the max-flow min-cut theorem of networks (PDF) . RAND corporation. 9 September 1964: 13 [10 January 2018] . (原始內容存檔 (PDF) 於2018-05-05).
^ Trevisan, Luca. Lecture 15 from CS261: Optimization (PDF) . (原始內容存檔 (PDF) 於2019-11-01).
^ 3.0 3.1 P. Elias, A. Feinstein, and C. E. Shannon, A note on the maximum flow through a network, IRE. Transactions on Information Theory, 2, 4 (1956), 117–119