最小切割问题

首先介绍什么是切割。切割就是将一张图中的顶点分成两部分A和B。

接下来介绍一下什么是容量。容量是A区到B区所有的边权重之和。

最小切割就是求一张图中使得容量最小的切割方式。

最小切割的应用

最小切割在国家的拆分时会用到。著名的苏联解体事件就是通过计算最小切割来实现国家的拆分。在建模的时候将城市作为图论中的顶点，将铁路作为顶点之间的边。最后通过计算最小切割来界定国家界线。

最大流问题

最大流就是从顶点s到顶点t，经过所有的边，网络所能支撑的最大流量。下图中顶点t从三个方向接收流量，它们的流量之和为28，所以最大流是28。