首页 > 代码库 > 算法9-1:最大流和最小切割问题

算法9-1:最大流和最小切割问题

最小切割问题


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


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


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


最小切割的应用


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



最大流问题


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