最大流问题

图论、网络理论应用中的一个优化问题。设一个连通的有向图G=(V,E)只有一个始点 （流的发点） 和一个终点 （流的收点），通过每条边(Vi、Vj)εE的流量为fij≥0，规定流量的上限为Cij>0。如果网络流f={fij}，满足0≤fij≤Cij，对于中间点有＝, 对于发点有＝F, 对于收点有＝F，则称f为一可行流，F为流进或流出整个网络的总流量。那么求一个可行流f*使流量F最大的问题就是最大流问题。求最大流的方法有，标号法也称Ford Fulkerson算法。最大流问题常用于解决公路交通运输网络、信息流通网络，以及各种具有流量分配的社会、经济、工程问题。