教案图与网络之二.pptVIP

因为t点得到标号,用反向追踪法可找出从s到t的一条增广链,用红线标出;修改增广链上的流量:其余弧上的流量不变,于是得到网络上的一个新可行流,重复上述的标号过程,转下一步;标号中断,t点得不到标号,网络中没有增广链,该网络的可行流就是最大流,最大流量为下面求该网络的最小割:运筹学讲课教师：汤建影南京航空航天大学经济与管理学院01网络分析中的常用名词02最小生成树问题03最短路问题04最大流问题05最小费用流问题06中国邮递员问题07网络计划技术第四章网络分析第四节最大流问题引言网络流的基本概念求解网络最大流的基本原理寻找网络最大流的标号法确定网络中最大流的方法引言网络中的流量，称为网络流，如公路系统中的车辆流，控制系统中的信息流，金融系统中的现金流等设产地与销地之间具有一个交通网，图中每一条弧代表从到的运输线，产品经这条弧由运到，弧旁的数字表示这条运输线的最大通过能力。现要求制定一个运输方案，使从运到的产品数量最多。1084565331117一、网络流的基本概念流量与容量给定一个有向图D=(V,A)，在V中指定一点，称为发点(记为)，同时指定另外一点，称为收点(记为)，其余的点称为中间点。对于每一个弧，对应有一个或简写为，称为弧的容量。我们把这样的一个有向图D称为一个网络，记作,容量是弧最大允许流通量流量可看作是某时间内通过弧的物质的数量，记为，是网络流问题中的待求解变量一、网络流的基本概念网络流应当满足两个条件每个弧上的流量不能超过该弧的容量即容量限制条件中间点的流量为零：平衡条件定义：满足下述条件的流称为可行流(1)容量限制条件：对每一个弧(2)平衡条件：对于中间点，对于发点对于收点饱和弧与非饱和弧若给一个可行流，定义网络中（流量等于容量）成立的弧为饱和弧，的弧为非饱和弧，的弧为零流弧，的弧为非零流弧正向弧与反向弧设是网络中从始点到终点的一条链，凡与链走向一致的弧称为正向弧，逆向的称为反向弧一、网络流的基本概念增广链：对于一可行流，网络的一条链上的各弧满足01则称该是对于该可行流的增广链增广链上的正向弧都是非饱和弧，反向弧都是非零流弧沿着增广链可以继续增加流量，增量为02一、网络流的基本概念当有增广链时,找出再令显然仍是一个可行流,与原来的可行流比较发现,网络中从s→t的流量增大了一个值(0).因此,只有当网络中找不到增广链时,s→t的流才不可能进一步增大.求解网络最大流的基本原理01数学模型02所谓求网络最大流,就是指在满足容量限制条件和中间点平衡条件下,使v(f)值达到最大.031给出一初始可行流，例如。2寻找增广链，若存在，则通过该增广链调整、增加网络流。4定理：可行流f*为最大流的充分必要条件是当且仅当网络不存在关于f*增广链。3若不存在增广链，则网络流不可再增加。求得最大流。二、求解网络最大流的基本原理三、寻找网络最大流的标号法该算法是由Ford,Fulkerson于1956年提出,故称Ford-Fulkerson标号法.算法的实质是判断网络中是否存在增广链,并将其找出来.Ford-Fulkerson标号法首先给发点s标号,记为,括号中第一个数字是使这个点得到标号的前一个点的代号,第二个数字表示从上一个标号点到这一标号点的流量的最大允许调整值;找出与已标号点相邻的所有未标号点.考虑从标号点i出发的弧(i,j),如有不给j点标号;若有则对j点标号,记为其中i表示j点的标号是从i点延伸过来的,(正向弧)考虑所有指向i的弧(h,i),如有对h点不标号,若有则对h点标号,记为(反向弧)如果某未标号点k有两个以上的相邻的标号点,为减少迭代次数,可按(1),(2)中的规则,分别计算的值,取其中最大的一个标记.标号过程中断,t点得不到标号,说明网络中不存在增广链,网络中给定的流就是最大流.计算结束;01t点得到标号,这时反向追踪,在网络中找到一条从s到t的由标号点和相应的弧连结而成的增广链.02修改流量:设在网络中原有的流量为f.03⒊重复步骤2,可能出现两种结局:抹去网络图中的所有标号,重复第1到第4步,一直到在网络中找不到任何增广链,即出现第3步的结局(1)为止,这时网络中的流量为网络的最大流.Ford-Fulkerson标号法(小节)For