图与网络
网络最大流基本概念
可行流需要满足的条件：
- 容量约束条件： 0 <= fij <= cij
-
流量约束条件：
- 每个中间点：接收的流量之和 = 发出的流量值和
- 发点和收点：发点发出流量之和 = 收点接收流量之和
若
μ
\mu
μ
是网络中联结发点和收点的一条链，链的方向是发点到收点，链上的弧为：
- 前向弧：弧的方向与链的方向一致
- 后向弧：弧的方向与链的方向相反
设f是一个可行流，
μ
\mu
μ
是从发点到收点的一条链，
μ
\mu
μ
是增广链需要满足：
- 弧(Vi,Vj)是前向弧，则 0<= fij < cij, 即前向弧每一条弧是非饱和弧
- 弧(Vi,Vj)是后向弧，则 0< fij <= cij,则后向弧每一条弧是非零流弧
可行性流f*是最大流的充分必要条件是不存在发点到收点的增广链。
割集
：将网络中的点集V分为两个非空的集合
V
1
V_1
V
1
和
V
1
‾
\overline{V_1}
V
1
， 使得发点
V
s
∈
V
1
,
收
点
V
t
∈
V
1
‾
V_s \in V_1,收点V_t \in \overline{V_1}
V
s
∈
V
1
,
收
点
V
t
∈
V
1
。则把弧集(
V
1
,
V
1
‾
V_1,\overline{V_1}
V
1
,
V
1
)称之为是分离发点和收点的割集。
割集(
V
1
.
V
1
‾
V_1.\overline{V_1}
V
1
.
V
1
)中所有的弧的容量之和成为割量，割量最小的割集称之为最小割集。
定理：网络的最大流量等于它的最小割量
割集容量：
算法内容：
流网络的定义：
容量限制：
f
(
u
,
v
)
≤
c
(
u
,
v
)
f(u,v)\leq c(u,v)
f
(
u
,
v
)
≤
c
(
u
,
v
)
对称性：
f
(
u
,
v
)
=
−
f
(
v
,
u
)
f(u,v) = -f(v,u)
f
(
u
,
v
)
=
−
f
(
v
,
u
)
流量限制：对于所有点除了源点和汇点，
∑
v
∈
V
f
(
u
,
v
)
=
0
\sum_{v \in V} f(u,v) = 0
∑
v
∈
V
f
(
u
,
v
)
=
0
==如何理解？==其实就是流入的等于流出的，这里的v指的是所有的点，结合第二条性质，原来从v到u的点（流入）被改成了-f(u,v)。
网络流的值:
∣
f
∣
=
∑
v
∈
V
f
(
s
,
v
)
|f| = \sum_{v \in V}f(s,v)
∣
f
∣
=
∑
v
∈
V
f
(
s
,
v
)
,s是源点
网络流的性质：
-
f(X,X) = 0
证明：
∑x
∈
X
∑
y
∈
X
f
(
x
,
y
)
+
∑
y
∈
X
∑
x
∈
X
f
(
y
,
x
)
=
0
\sum_{x\in X}\sum_{y\in X} f(x,y) + \sum_{y\in X}\sum_{x\in X}f(y,x) = 0
∑
x
∈
X
∑
y
∈
X
f
(
x
,
y
)
+
∑
y
∈
X
∑
x
∈
X
f
(
y
,
x
)
=
0
-
f(X,Y) = -f(Y,X)
证明：
∑x
∈
X
∑
y
∈
X
(
f
(
x
,
y
)
+
f
(
y
,
x
)
)
=
0
\sum_{x\in X}\sum_{y \in X}(f(x,y)+f(y,x))=0
∑
x
∈
X
∑
y
∈
X
(
f
(
x
,
y
)
+
f
(
y
,
x
)
)
=
0
-
f(
X
⋃
Y
,
Z
)
=
f
(
X
,
Z
)
+
f
(
Y
,
Z
)
i
f
X
⋂
Y
=
ϕ
f(X\bigcup Y,Z)=f(X,Z)+f(Y,Z) \quad if X \bigcap Y = \phi
f
(
X
⋃
Y
,
Z
)
=
f
(
X
,
Z
)
+
f
(
Y
,
Z
)
i
f
X
⋂
Y
=
ϕ
f(
X
⋃
Y
,
Z
)
=
∑
s
∈
X
⋃
Y
∑
t
∈
Z
f
(
s
,
t
)
=
(
∑
s
∈
X
+
∑
s
∈
Y
)
∑
t
∈
Z
f
(
s
,
t
)
∵
X
⋂
Y
=
ϕ
=
∑
s
∈
X
∑
t
∈
Z
f
(
s
,
t
)
+
∑
s
∈
Y
∑
t
∈
Z
f
(
s
,
t
)
=
f
(
X
,
Z
)
+
f
(
Y
,
Z
)
f(X \bigcup Y,Z) = \sum_{s\in X \bigcup Y}\sum_{t\in Z} f(s,t) \\ =(\sum_{s\in X}+\sum_{s \in Y})\sum_{t \in Z} f(s,t) \\ \because X\bigcap Y = \phi \\ =\sum_{s \in X}\sum_{t \in Z}f(s,t) + \sum_{s \in Y}\sum_{t \in Z}f(s,t) \\ = f(X,Z)+f(Y,Z)
f
(
X
⋃
Y
,
Z
)
=
s
∈
X
⋃
Y
∑
t
∈
Z
∑
f
(
s
,
t
)
=
(
s
∈
X
∑
+
s
∈
Y
∑
)
t
∈
Z
∑
f
(
s
,
t
)
∵
X
⋂
Y
=
ϕ
=
s
∈
X
∑
t
∈
Z
∑
f
(
s
,
t
)
+
s
∈
Y
∑
t
∈
Z
∑
f
(
s
,
t
)
=
f
(
X
,
Z
)
+
f
(
Y
,
Z
)
-
∣f
∣
=
f
(
V
,
t
)
|f| = f(V,t)
∣
f
∣
=
f
(
V
,
t
)
∣f
∣
=
f
(
s
,
V
)
=
f
(
V
,
V
)
−
f
(
V
−
s
,
V
)
=
−
f
(
V
−
s
,
V
)
=
f
(
V
,
V
−
s
)
=
f
(
V
,
t
)
+
f
(
V
,
V
−
s
−
t
)
∵
f
(
V
,
V
−
s
−
t
)
=
∑
s
∈
V
∑
t
∈
V
−
s
−
t
f
(
s
,
t
)
=
∑
s
∈
V
0
=
0
∴
∣
f
∣
=
f
(
V
,
t
)
|f| = f(s,V) \\ =f(V,V) – f(V-s,V) \\ =-f(V-s,V) \\ =f(V,V-s) \\ =f(V,t) + f(V,V-s-t) \\ \because f(V,V-s-t) = \sum_{s \in V}\sum_{t \in V-s-t} f(s,t) \\ =\sum_{s \in V} 0 \\ =0 \\ \therefore |f| = f(V,t)
∣
f
∣
=
f
(
s
,
V
)
=
f
(
V
,
V
)
−
f
(
V
−
s
,
V
)
=
−
f
(
V
−
s
,
V
)
=
f
(
V
,
V
−
s
)
=
f
(
V
,
t
)
+
f
(
V
,
V
−
s
−
t
)
∵
f
(
V
,
V
−
s
−
t
)
=
s
∈
V
∑
t
∈
V
−
s
−
t
∑
f
(
s
,
t
)
=
s
∈
V
∑
0
=
0
∴
∣
f
∣
=
f
(
V
,
t
)
如果流量图有节点v，从源节点s到达该节点的路径不存在，则有最大流，从节点v流向其他节点的流为0，从其他节点流向v的流也为0.
任
意
u
∈
V
:
p
(
u
,
v
)
=
0
a
n
d
p
(
v
,
u
)
=
0
任意u \in V: p(u,v) =0 \quad and \quad p(v,u) = 0
任
意
u
∈
V
:
p
(
u
,
v
)
=
0
a
n
d
p
(
v
,
u
)
=
0
设s能够到达的节点集合为
V
s
,
显
然
v
∉
V
s
V_s,显然v \notin V_s
V
s
,
显
然
v
∈
/
V
s
,
对
于
任
意
v
′
∈
V
−
V
s
,
s
无
法
到
达
v
′
对于任意v’ \in V-V_s,s无法到达v’
对
于
任
意
v
′
∈
V
−
V
s
,
s
无
法
到
达
v
′
f
(
V
−
V
s
,
V
)
=
0
f
(
V
−
V
s
,
V
s
)
=
0
任
意
x
∈
V
−
V
s
,
y
∈
V
s
:
p
(
x
,
y
)
=
0
f
(
V
−
V
s
,
V
−
V
s
)
=
0
任
意
w
,
z
∈
V
−
V
s
:
p
(
w
,
z
)
=
0
f(V-V_s,V) = 0 \\ f(V-V_s,V_s)=0\\ 任意 x\in V-V_s,y\in V_s: p(x,y) = 0 \\ f(V-V_s,V-V_s) = 0 \\ 任意 w,z \in V-V_s: p(w,z) = 0
f
(
V
−
V
s
,
V
)
=
0
f
(
V
−
V
s
,
V
s
)
=
0
任
意
x
∈
V
−
V
s
,
y
∈
V
s
:
p
(
x
,
y
)
=
0
f
(
V
−
V
s
,
V
−
V
s
)
=
0
任
意
w
,
z
∈
V
−
V
s
:
p
(
w
,
z
)
=
0
残余网络
原图的容量变为严格为正的残余容量
c
f
(
u
,
v
)
=
c
(
u
,
v
)
−
f
(
u
,
v
)
>
0
E
f
≤
2
E
c_f(u,v) = c(u,v) – f(u,v) >0 \\ E_f \leq 2 E
c
f
(
u
,
v
)
=
c
(
u
,
v
)
−
f
(
u
,
v
)
>
0
E
f
≤
2
E
画法：
例子:
增广路径
增广路径是在增广网络
G
f
G_f
G
f
中的从源点到汇点的一条简单路径。
增广路径的容量是增广路径中的流的最小值。最大流能够增大通过提升p中的每一条边。
当流中不存在增广路径时，得到最大流。
这三个定理等价：
- 流的大小等于割量大小
- f时最大流
- f不包含增广路径
Ford&Fuklerson算法
首先初始化流量为0，找增广路径。
时间复杂度
O
(
F
(
n
+
m
)
)
O(F(n+m))
O
(
F
(
n
+
m
)
)
,F是最大流，n是点的数量，m是边的数量。F要是很大，效率会很低。
主要就是画图，DFS原则，没啥好说的
Edmonds & Karp算法
BFS原理部分跳过
BFS(G,s)
for each vertex u in V[G]-{s}
color[u] <- white
d[u] <- +inf
front[u] <- null
color[s] <- gray
d[s] <- 0
front[s] <- null //初始化根节点
Q <- null
enqueue(Q,s) //入队
while Q != null
u <- dequeue(Q)
for each v in Adj[u] //u的邻接点
if color[v]=white
color[v]<-gray
d[v]<-d[u]+1 //父节点深度+1
front[v]<-u //记录父节点
enqueue(Q,v)
color[u] <- black //访问完毕
时间复杂度
O
(
∣
V
∣
+
∣
E
∣
)
O(|V|+|E|)
O
(
∣
V
∣
+
∣
E
∣
)
EK算法就是用BFS去找增广路径。时间复杂度
O
(
∣
V
∣
∣
E
∣
2
)
O(|V||E|^2)
O
(
∣
V
∣
∣
E
∣
2
)
EK算法的证明：你以为我会吗？
标号法寻找网络最大流（运筹学）
选择可用，方便些
。
步骤：
- 找出一个可行流（若没有初始可行流，可设所有弧的流量fij=0）
-
标号以寻增广链
-
发点标号(0,+
∞\infty
∞
) -
选一个点
Vi
V_i
V
i
已标号，并且另一端点
Vj
V_j
V
j
没有标号的弧沿着某条链向收点检查。-
若弧为前向弧，并且fij<cij，则Vj标号(Vj,
θj
\theta_j
θ
j
),
θj
=
c
i
j
−
f
i
j
\theta_j=c_{ij}-f_{ij}
θ
j
=
c
i
j
−
f
i
j
-
若弧为后向弧，并且fji>0，则Vj标号(Vj,
θj
\theta_j
θ
j
),
θj
=
f
j
i
\theta_j = fji
θ
j
=
f
j
i
-
若弧为前向弧，并且fij<cij，则Vj标号(Vj,
-
重复(2),当收点已经得到标号，说明找到一条增广链，依据标号点的第一个标号进行反向追踪得到增广链
μ\mu
μ
;若收点不能得到标号，说明不存在增广链，算法结束。
-
发点标号(0,+
-
调整流量
-
求增广链上所有标号点第二个标号的最小值，得到调整量
θ=
m
i
n
(
θ
j
)
\theta = min (\theta_j)
θ
=
m
i
n
(
θ
j
)
-
调整流量：增广链上前向弧
fi
j
′
=
f
i
j
+
θ
f_{ij}’ = f_{ij} + \theta
f
i
j
′
=
f
i
j
+
θ
;增广链的后向弧
fj
i
′
=
f
j
i
−
θ
f_{ji}’ = f_{ji} – \theta
f
j
i
′
=
f
j
i
−
θ
- 得到新的可行流之后，去掉所有标号，重复步骤二三，直到收点不能标号为止。
-
求增广链上所有标号点第二个标号的最小值，得到调整量
具体参考https://www.bilibili.com/video/BV1ir4y1S7SA?p=2