网络流杂谈

学习了快三个月网络流了,总算有点个人的感觉了,希望这篇 blog 可以给各位新学网络流的人一些启示吧 QWQ

目录

• 网络流杂谈
  • 基础概念
    • 什么是网络(Network)
    • 什么是流(Flow)
    • 常见的网络流问题类别
  • 基础网络流问题的求解

网络流杂谈

基础概念

什么是网络(Network)

简单的说, 就是给定一个有向图 \(G = (V, E)\), 如果 \(V, E\) 满足以下这些特殊的性质, \(G\) 就被称为一个网络

在 \(V\) 当中有两个特殊点, 一个叫源点(Source), 一个叫汇点(Sink). 源点没有入边, 汇点没有出边. 源点用字母 \(s\) 表示, 汇点用字母 \(t\) 表示

而对于每一条边 \((u, v) \in E\), 都有一个容量(Capacity) \(c\), 记作 \(c(u, v)\). 特别的, 如果对于一条边 \((u, v) \notin E\), 我们可以认为 \(c(u, v) = 0\)

另外, 在网络流中, 边有一个特殊的名字叫做 弧(Arc)

什么是流(Flow)

OIwiki 的说法有点太官方了, 听的云里雾里的所以我们这里换一个网络流原本的说法. 考虑你要从源点出发向汇点发送信息, 衡量信息的大小我们用一个量来形容, 用 \(f\) 表示, 称之为流量. 每条边相当于一个管道, 可以通过的最大的流量就是这条边的容量 \(c(u, v)\)

现在你每条边分配一个流量, 为了方便记录, 我们又如描述一条边的容量般描述一条边 \((u, v)\) 的流量为 \(f(u, v)\), 如果 \((u, v) \notin E\), 同样可以认为\(f(u, v) = c(u, v) = 0\). 这个 \(f\) 就是流, 它是一个函数, 我们也可以叫它流函数, 从源点 \(s\) 到汇点 \(t\) 的流函数记作 \(s - t\) 流. 最后运输到汇点的所有流量之和就是这个流的流量(Flow)

一个蕴含了流的网络就是流网络(Flow Network)

这里, 我们有两条性质

1. 容量限制: 根据我们的定义显然有每条边的流量小于或等于每条边的容量, 且不能倒流, 即流量非负.

   严谨的说,

   \[\forall (u, v) \in E, f(u, v) \le c(u, v) \]

2. 流量守恒: 除源点汇点之外, 每个节点的总流出量等于总流入量, 也就是说在这个流网络中, 不会存在一个除源点汇点之外的节点私吞流量或创造流量, 而源点可以产生无尽的流量, 汇点可以接收无尽的流量.

   严谨的说,

   \[\forall u \in V, \sum_{v \in V} f(u, v) = \sum_{v \in V} f(v, u) \]

基于此, 我们可以计算一个流的流量 \(f = \sum_{u \in V} f(u, t)\), 同时由于流量守恒, 源点流出的流量也应当等于汇点接收的流量, 所以我们得到一个更加大众化的结论(我也不知道这为什么大众) \(f = \sum_{u \in v} f(s, u)\)

常见的网络流问题类别

以上我们介绍了网络和流, 而网络流就是在网络上解决流问题, 一般常见以下名字像网络流的网络流问题

1. 最大流(Maximum Flow): 求解一个网络中的最大流量
2. 费用流(Cost Flow): 每一条边另有运输流量的代价 \(cost(u, v)\), 最终流的代价 \(C\) 为 \(\sum_{(u, v) \in E} f(u, v) \cdot cost(u, v)\), 现在要求在保证某种条件的情况下最值化 \(C\)
3. 可行流(Feasible Flow): 求解是否存在一个流满足某种给定的条件

基础网络流问题的求解