最大流问题,是网络流理论研究的一个基本问题,求网络中一个可行流f*,使其流量v(f)达到最大, 这种流f称为最大流,这个问题称为(网络)最大流问题。最大流问题是一个特殊的线性规划问题,就是在容量网络中,寻找流量最大的可行流。
最大流问题可以建立如下形式的线性规划数学模型:
式中v(f)称为这个可行流的流量、发点的净输出量或收点的净输出量。∞一般用标号法寻求有向最大流比用求线性规划问题的一般方法要方便得多。
最大的标号算法还用于解决多发点多收点网络的最大问题,设容量网络G有若干个发点x1,x2,...,xm;若干收点y1,y2,...,yn,可以添加两个新点vs,vt,用容量为∞的有向边分别连接两个新点vs与点x1,x2,...,xm,点y1,y2,...,yn与vt,得到新的网路G‘。G’是一个只有一个收点和发点的网络,求解最大流问题即可都得到G的解。