最大流算法及其应用.ppt

最大流算法及其应用 提要 网络流相关的一些概念 最大流和最小割问题 最大流算法的应用 总结 一网络流相关的一些概念 流网络 (Flow Network) 流网络是一个有向图G=(V,E)其中每条边(u,v)E均有一非负容量c(u,v)0如果(u,v)E则假定c(u,v)=0流网络中有两个特别的顶点源点s和汇点t 图1 一个流网络的例子 流 (Flow) G的流是一个实值函数ff(u,v)表示顶点u