网络流初步◆最大流算法◆最小费用最大流◆最大流最小割定理最大流算法网络流之一问题:问从S到T的最大水流量是多少?1S43256t73484246实例:有一自来水管道输送系统,起点是S,目标是T,途中经过的管道都有一个最大的容量。1S43256t7348424646222446最大水流量是10一、网络流的定义有唯一的一个源点S(入度为0:出发点)有唯一的一个汇点T(出度为0:结束点)图中每条弧(u,v)都有一非负容量c(u,v)有向图G=(V,E)中:满足上述条件的图G称为网络流图。记为:G=(V,E,C)1、可行流◆每条弧(u,v)上给定一个实数f(u,v),满足:有0<=f(u,v)<=c(u,v),则f(u,v)称为弧(u,v)上的流量。◆如果有一组流量满足条件:源点s:流出量=整个网络的流量汇点t:流入量=整个网络的流量中间点:总流入量=总流出量那么整个网络中的流量成为一个可行流。区分:容量和流量124356423454121243542333112435642345411243542353334一个可行流:5一个可行流:7图1图22、最大流在所有的可行流中,流量最大的一个流的流量如:图2中可行流7也是最大流。最大流可能不只一个。二、最大流算法步骤: (1)如果存在增广路径,就找出一条增广路径(2)然后沿该条增广路径进行更新流量(增加流量)◆Ford-Fulkerson(福特-福克森)算法:
最大流算法 来自淘豆网m.daumloan.com转载请标明出处.
