网络流——求网络最大流.pptVIP

网络流 第一讲 求网络最大流 一、基本概念 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 1.问题描述 如图所示是联结某产品地v1和销售地v6的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v6。现在要求制定一个运输方案使从v1到v6的产品数量最多。 图1 V1 V2 V4 V6 V5 V3 1 4 4 2 2 7 4 6 9 8 2.网络与网络流 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥0(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v6为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图2所示的网络N，弧上的数表示流量fij。 函数F＝{Fij}（ 且 ）： F12=3, F13=2, F23=2, F24=0, F25=1, F34=2, F35=2, F54=0, F56=3, F46=2 V1 V2 V4 V6 V5 V3 1 2 2 2 2 2 0 0 3 3 图2 图1 V1 V2 V4 V6 V5 V3 1 4 4 2 2 7 4 6 9 8 3.可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： (1)容量约束：0≤fij≤cij，(vi,vj)∈E， (2)守恒条件对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 若给一个可行流F＝(Fij) 饱和弧：网络中Fij =Cij的弧 非饱和弧：网络中Fij ＜ Cij的弧 非零流弧：网络中 Fij＞0 的弧 零流弧：网络中 Fij =0的弧 4.可增广路径 若P是网络中联结源点Vs和汇点Vt的一条路，我们定义路的方向是从Vs到Vt，则路上的弧被分成两类： 一类是弧的方向与路的方向一致，叫做前向弧。前向弧的全体记为P+。另一类弧与路的方向相反，叫做后向弧。后向弧的全体记为P-。 如图，在路P＝{Vl,V3,V2,V4,V6}中 P+＝{(Vl,V3)，(V2,V4)，(V4,V6)} P -＝{(V3,V2)} 图1 V1 V2 V4 V6 V5 V3 1 4 4 2 2 7 4 6 9 8 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： (1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤fijcij  (2)在p上的所有后向弧(vi←vj)都是非零弧，即0fij≤cij则称p为(关于可行流f的)一条可增广路径。 可增广调整： (1)不属于可增广路P的弧(Vi,Vj)上的流量一概不变，即Fij＝Fij (2)可增广路P上的所有弧(Vi,Vj)上的流量按下述规则变化； 在前向弧(Vi,Vj)上，Fij＝Fij+a 在后向弧(Vi,Vj)上， Fij＝Fij-a a称为可增广量，它应该按照下述原则确定：a既要取得尽量大，又要使变化后的Fij仍满足可行流的两个条件——容量限制条件和平衡条件。不难看出，按照这个原则,a即不能超过每条前向弧的Cij-Fij，也不能超过每条后向弧的Fij。因此a应该等于前向弧上的Cij-Fij与后向弧上的Fij的最小值。 V1 V2 V4 V6 V5 V3 1 2 2 2 2 2 0 0 3 3 P