概述
网络是指一个特殊的有向图 $G=(V,E)$，与一般图不同的是有容量和源汇点
- $E$ 中的每条边 $(u,v)$ 都有一个被称为容量的权值，如果某条边 $(u,v)\not\in E$，可以假定 $c(u,v)=0$
- $V$ 中有两个特殊的点，源点 $s$ 和汇点 $t$
对于网络 $G=(V,E)$，流是一个从边集 $E$ 到整数集或实数集的函数，满足以下性质
- 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 $0\leq f(u,v)\leq c(u,v)$
- 流守恒性：除源汇点外，任意结点 $u$ 的净流量为 $0$。其中，我们定义 $u$ 的净流量为 $f(u)=\sum_{x\in V}f(u,x)-\sum_{x\in V}f(x,u)$
对于网络 $G=(V,E)$ 和其上的流 $f$，我们定义 $f$ 的流量 $|f|$ 为 $s$ 的净流量 $f(s)$，根据流守恒性 $f(s)=-f(t)$
对于网络 $G=(V,E)$，如果 ${S,T}$ 是 $V$ 的划分（即 $S\cup T=V$ 且 $S\cap T=\emptyset$），且满足 $s\in S,t\in T$，那我们就称 ${S,T}$ 是 $G$ 的一个 $s-t$ 割。定义 $s-t$ 割 ${S,T}$ 的容量为 $||S,T||=\sum_{u\in S}\sum_{v\in T}c(u,v)$
常见问题分类
-
最大流问题：对于网络 $G=(V,E)$，给每条边指定流量，得到合适的流 $f$，使得 $f$ 的流量尽可能大，此时称 $f$ 为 $g$ 的最大流
-
最小割问题：对于网络 $G=(V,E)$，找到合适的 $s-t$ 割 ${S,T}$，使得其容量尽可能小，此时称 ${S,T}$ 为 $G$ 的最小割
-
最小费用最大流问题：在网络 $G=(V,E)$，对于每条边给定一个权值 $w(u,v)$，称为费用，含义是单位流量通过 $(u,v)$ 花费的代价，对于 $G$ 所有可能的最大流，我们称总费用最小的一者为最小费用最大流
最大流
最大流问题的学习
概述
令 $G=(V,E)$ 是一个有源汇点的网络，我们希望在 $G$ 上指定合适的流 $f$，以最大化整个网络的流量 $|f|$（即 $\sum_{x \in V} f(s, x) - \sum_{x \in V} f(x, s)$），这一问题被称作最大流问题
Ford–Fulkerson 增广
Ford–Fulkerson 增广是计算最大流的一类算法的总称。该方法运用 贪心 的思想，通过寻找 增广路 来更新并求解最大流。
概述
给定网络 $G$ 和 网络上的流 $f$，做如下定义
对于边 $(u,v)$，我们将其容量与流量之差称为剩余容量 $c_f(u,v)$，即 $c_f(u,v)=c(u,v)-f(u,v)$
我们将 $G$ 中所有的结点和剩余容量大于 $0$ 的边构成的子图称为残量网络 $G_f$，即 $G_f=(V,E_f)$，其中 $E_f={(u,v)\mid c_f(u,v)>0}$