网络流基础概念

## 1、网络流的基础概念

1、对于一个网络，它被定义为有向图 $G=(V,E)$ 。
其中 $V$ 为点集，$E$ 为边集。

2、图中分为三类点：源点、汇点、普通点。

源点：假使这个点是一个无限水的水龙头，可以无限流出水来。

汇点：假使这个点是一个无限存水的水库，可以无限储存水。

普通点：假使这个点是一个管道，可以将水流入别处，同时无法存水。

## 2、关于流函数

1、一个流函数 $f(u,v)$ 表示从 $u$ 到 $v$ 这个管道中在最远情况下能流多少水。

流函数的两个重要性质

1：容量限制 $0\le f(u,v)\le c(u,v)$ 其中 $c(u,v)$ 为这条边的最大流量。

2：流量守恒 简单理解就是因为一个点无法存水，所以流入的等于流出的。严谨的定义为 $\forall _{x\ne S,x\ne T} \sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$

2、我们定义 $|f|$ 表示每秒从源点流入汇点的水有多少。则 $|f|=\sum_{(S,v)\in E}f(s,v)-\sum_{(v,S)\in E}f(v,S)$ 。而这被称为源点流量值。

最大流就是求最大可行流量值。

## 3、残留网络

1、对于每个可行流$f_x$它的残留网络为 $G_x$ 。
其中 $V_x = V$ ，$E_x=2\times E$，为什么呢？
因为残留网络包含所有的反向边。

它的流量限制定义为
若 $(u,v)\in E$ 则$c_x(u,v)={c(u,v)-f(u,v)}$ 。

否则$c_x(u,v)={f(v,u)}$ 。

2、一条边的流量值定义为 $|f|=\frac{c_x(u,v)}{c(u,v)}$

## 4、增广路径

这个是指在残留网络中有一条能从源点走向汇点并不经过流量值 $< 0 $ 的边的路径。

## 5、割

割指的是将点集分为两个集合 $S,T$ ，其中$S\lor T=V$，$S\land T=\empty$ 。

割的容量：割的容量用 $C(S,T)$ 表示，那么 $C(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)$ 。

最小割：所有割的容量最小值。

割的流量：割的流量用 $F(S,T)$ 表示，那么 $F(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in T}\sum_{v\in S}f(u,v)$ 。

两条非常重要的性质： 
1： $\forall [S,T]\quad F(S,T)\le C(S,T)$ 。形式化的讲就是对于所有的割，割的流量小于等于割的容量。
2： $\forall [S,T]\quad F(S,T)=|f|$。

## 6、最大流最小割定理：

1、流 $f$ 是最大流。

2、流 $f$ 的残留网络中不存在增广路。

3、存在某个割 $[S,T]$ ，$|f|=C(S,T)$ 。

以上三点只要满足一条，其余两条也满足。