[TOC]

突击学习一下。

Maximum flow problem

最大流问题是在单源单汇的网络流中找到最大的流。

Multi-source multi-sink maximum flow problem equals to maximu flow prblem.

https://en.wikipedia.org/wiki/Maximum_flow_problem

问题输入：一个带有权重的有向图，顶点t是源，目标顶点是t。每个边都一个正的容量。(capacity)

定义流

st-flow(flow)给边赋值，满足下面两个条件：

1、容量约束：0 <= edge’s flow <= edge’s capacity

2、局部平衡：除了顶点s，t，每个边的 流入=流出（inflow=outflow)

最大流问题

定义：一个流的值是顶点t的流入量。

如下图，流flow的值为 15 。

**st-flow(maxflow)问题。 就是找到最大流的值。**Maximum

Max-flow min-cut theorem

最大流等于最小切（割）。

https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

定义

输入：一个带有权重的有向图，顶点t是源，目标顶点是t。每个边都一个正的容量。(capacity)

st-cut(cut)是将顶点分成两个不相交的集合。s在集合A中，b在集合B中。

**容量：**集合A到集合B的所有边的容量之和。

例如下图，黑线所示的一个cut，容量是10+5+15=30.

注意不算B指向A的边

Minimum st-cut(mincut) problem最小割问题： **找到一个割cut，拥有最小的容量capacity。**

下图这个割cut，容量是28.

最小割的应用

下图是冷战时期苏联的供给地图。

红线可以有效截断苏联的供给。

“Free world” goal. Cut supplies (if cold war turns into real war).

总结

输入：A weighted digraph, source vertex s, and target vertex t.

最小割问题：找到一个割的最小容量。

最大流问题：找到最大流的值。