图论（七）——网络流的最大流问题引入

网络流

一个网络 G= (V , E) 是一张有向图，图中的每一条边 (x , y) ∈ E，其权值w的意义为 最多可以将w个物品从节点x运输到节点y，所以这个权值又称为边的 容量，记为c(x , y)；

此外，在图中没有标出的边，即 (x , y) ∉ E，则c(x , y) = 0

然后还有两个指定的特殊的节点 S ∈ V，T ∈ V（S != T）分别称为源点和汇点（源点：入度为0的点；汇点：出度为0的点）

网络流就像水流一样，“水”要从源点经过中间节点和其中的边流向汇点，每一条边最多所能够流过的“水”就是边的容量（ c(x , y) ），而在实际过程中流过一条边（x , y）的“水”称为这条边的流函数，将其记为 f(x , y)

很明显，对于一条边而言，其流量必然不大于容量，即c(x , y)>=f(x , y)，这个性质又称为容量限制

“对于边（x , y），有3个“水”从x流向y，又有4个“水”从y流向x”，

其实就等价于，”有1个“水”从y流向x“，即f(y , x)=1，

又等价于”有-1个“水”从x流向y“，即f(x , y)=-1

那么因此就可以规定对于相反的两条边（x , y）和（y , x），它们的流量不能同时为正（当然可以同时为0），且f(x , y)= -f(y , x)，这个性质又称为斜对称性

对于这个图而言，所有的”水“从源点出发，最终必然都汇聚到汇点，即从源点流出的“水” 等于 流回汇点的“水”，当然这个值也就等于整个图的流量，这个性质称为流量守恒

综上，可以总结出流函数f(x , y)的三个性质：

容量限制（c(x , y)>=f(x , y)），

斜对称性（f(x , y)= -f(y , x)），

流量守恒（流入总量等于流出总量）

那么如何使得整个网络的流量最大的问题，就称为最大流问题

解决最大流问题的方法：

1. 图论（六）——网络流的最大流问题之Edmonds-Karp算法
2. 图论（七）——网络流的最大流问题之Dinic算法