首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》结论

关灯直达底部

当Ford-Fulkerson算法终止时,顶点集V被分成了两个不相交的子集,S和T(T=V-S)。注意s∈S,t∈T。S是V中不能组成增广路径的顶点集合。我们得到的这两个集合是非常重要的,因为在S和T之间的前向边组成了流网络的“最小割”。也就是说,这些边成了这个流网络的“瓶颈”,因为(a)流网络被分成了两个顶点集合,S和T,这两个顶点集合的流是最小的;(b)在S和T之间的流已经达到容量限制了。