网络流

定义

给定一个有向图$G=(V, E)$，其中每条边$(u, v)$都有一个非负的容量值，记做$c(u, v)\geq 0$，同时图中存在两个特殊点源点$S$, 汇点$T$。其中从源点$S$到汇点$T$的最大可行流量，这个问题也被称为最大流问题

性质

• 容量限制：对于任意的$ < u, v > \in V,f(u,v)\leq c(u,v)$
• 反对称性：对于任意的$ < u,v > \in V,f(u,v)=-f(v,u)$
• 流量守恒：对于任意的$u$，若$u$不为$S$且不为$T$，那么$\sum f(u,v)=0$，即$u$到相邻节点的流量和为$0$，因为流入$u$的流量和$u$流出的流量相等，节点$u$本身不会产生和消耗流量。

解决思路

寻找增广路，不断更新残余网络，直到找不到任何增广路

最大流最小割定理

前言

对于一个网络流$G=(V,E)$，其割的定义是一种点的划分方式，将所有点划分为$S$和$T=V-S$两部分，其中源点$s\in S$，汇点$t \in T$。对于一个割$(S,T)$，定义净流$f(S,T)$表示穿过割$S,T$的流量和。

$f(S,t)=\sum f(u,v) | u\in S, v \in T$

其中任意一个割的净流$f(S,T)$总是和网络流的流量$f$相等

解释

根据网络流的定义，只有源点$s$会产生流量，汇点$t$会接收流量。因此对于任意非$s$和$t$的点$u$，净流量一定是$0$，也就是$\sum f(u,v)=0$。而源点$s$的流量最终都会经过割$(S,T)$的边到达汇点$t$，所以网络流的流$f$等于割的净流$f(S,T)$

定义

在所有可能的割中，存在一个容量最小的割，我们称其为最小割

对于任意网络流图而言，其最大流一定小于等于最小割

定理

对于一个网络流图$G=(V,E)$，其中有源点$s$和汇点$t$，我们可以推出一个最大流最小割定理

• 流$f$是图$G$的最大流
• 残留网络$Gf$不存在增广路
• 对于$G$的某一个割$(S,T)$，此时$f=C(S,T)$

证明

$1 \Rightarrow 2$

利用反证法，假设$f$是$G$的最大流，但是残留网络中存在增广路$p$，流量为$fp$，那么我们又$f'=f+fp>f$。和$1$矛盾

$2 \Rightarrow 3$

假设参与网络$Gf$不存在增广路，所以在参与网络$Gf$中不存在路径从$s$到达$t$。我们定义$S$集合为：当前残留网络汇中$s$能够到达的点。同时定义$T = V - S$

此时$(S,T)$构成一个割$S,T$。且对于任意的$u \in S, v \in T$有$f(u,v)=c(u,v)$。若$f(u,v)<c(u,v)$则由$Gf(u,v)>0$，$s$可以到达$v$，与$v$属于$T$矛盾

$3 \Rightarrow 1$

由于$f$的上界是最小割，当$f$到达割的容量的时候，显然达到了最大值，因此$f$是最大流

拓展

二分图多重匹配

$S$连向$A$，流量为$A$中点可以连接的数量，$A$连向$B$表示可以匹配，$B$连向$T$，流量为可以连接的数量

最小路径覆盖

定义

给定一个有向无环图，用最少的路径数量去保证所有点都被覆盖住

对于每条路径，起点入度都为$0$，终点的出度都为$0$，中间节点的出入读都为$0$

每个点最多有一个前驱，同时最多有一个后继节点

做法

将每个点$u$拆成$u,u'$，其中$S$连向每个$u$，每个$u'$连向$T$，对于每条边$(u,v)$，建立边$u\rightarrow v'$，跑网络流，最终答案为点数$-$最大流

最大权闭合子图

定义

给定一有向图，从中选择一些点组成点集$V$。对于每个$V$中的节点，其后续节点仍然需要在$V$中。最权值最大的子图

做法

首先建立源点$s$和汇点$t$，将源点$s$和所有权值为正的点相连，流量为权值，将所有权值为负的点和汇点$t$相连，流量为权值的绝对值，权值为$0$的点不做选择，同时将原来的边的流量设置为无穷大，答案为所有正权值和$-$最小割

引理

• 最小割一定是简单割
  • 简单割指得是：割$(S,T)$中每一条割边都与$s$或者$t$关联，这样的割叫做简单割。
• 简单割一定和一个闭合子图对应
  • 闭合子图$V$和源点$s$构成$S$集，其余点和汇点$t$构成$T$集

证明

• 闭合子图是简单割

• 若闭合子图对应的割$(S,T)$不是简单割，则存在一条边$(u,v)$，$u\in S$，$v \in T$，且$c(u,v)=\infty$。说明u的后续节点$v$不在$S$中，产生矛盾

• 简单割是闭合子图

• 对于$V$中任意一个点$u$，$u\in S$。$u$的任意一条出边$c(u,v)=\infty$，不会在简单割的割边集中，因此$v$不属于$T$，$v\in S$。所以$V$的所有点均在$S$中，因此$S-s$是闭合子图

• 最小割就是最大权的闭合子图

• 割的容量$C(S,T)=T$中所有正权点的点权之和等于$+S$中所有负权点的权值绝对值之和

• 闭合子图的权值$W=S$中所有正权点的权值之和$-S$中所有负权点的权值绝对值之和

• $C(S,T)+W=T$中所有正权点的权值之和$+S$中所有正权点的权值之和$=$所有正权点的权值之和

• 所以$W=$所有正权点的权值之和$-C(S,T)$