网络流问题.pptVIP

求网络最大流的方法 （1）增量网络与原网络的关系 * 定义1 设G = ( V, E )为有向图, 在V中指定一点称为发点(记为vs ), 和另一点称为收点(记为vt ), 其余点叫做中间点. 对每一条边vivj∈E, 对应一个非负实数Cij, 称为它的容量. 这样的G称为容量网络, 简称网络, 记作G = ( V, E, C ) .G中任一边vivj有流量fij , 称集合f = { fij}为网络G上的一个流. 网络流问题 ３ ５ ３ ５ ４ 定义2 满足下述条件的流 f 称为可行流： ① (容量限制条件) 对每一边vivj, 有0≤ fij ≤Cij ; ② (平衡条件) 对于中间点vk有∑fik =∑fkj , 即中 间点vk的输入量 = 输出量. 如果f 是可行流, 则对收、发点vt、vs有∑fsi =∑fjt =Wf, 即从vs点发出的物质总量= vt点输入的量. Wf称为网络流 f的总流量. 网络流问题 定义3 设f是一个可行流, μ是从vs到vt一条链. 如果满足 ① 当vivj∈μ+ 时, 0≤ f ij ＜Cij, 即 μ+ 中的每一条边都非饱和边; ② 当vivj∈μˉ时, 0＜ f ij ≤C ij, 即 μˉ中的每一条边都非零边. 则称μ为从vs到vt的关于f 的可增广链. 最大流问题 一个可行流 f = { f ij }, 当 f ij = C ij时, 则称流 f 对边vivj是饱和的; 当f ij＜C ij时, 则称流 f 对边是非饱和的. 把f ij = 0的边称为零流边, f ij ＞0的边称为非零流边. 若 μ为网络中从vs到vt的一条链(有向图中的路), 定义链的方向是从vs到vt , 边的方向与链的方向相同称为前向边, 前向边的全体记为 μ+ ; 边的方向与链的方向相反称为后向边, 后向边的全体记为μˉ. 最大流问题 的顺向弧的数表示原网络对应弧上最大可增加的流量。 的逆向弧的数表示原网络对应弧上最大可减少的流量。若在 中能找到从 到 的一条路 ，且每条弧容量为正数，则称 为 的增广链。令: ，称为增广量 对原网络的流 作如下调整： 则 是新的可行流且 ，若 中不存在增广链，则对应的流 已是最大流。 （2）步骤 1、以零流 作初始可行流； 2、作增量网络 ； 3、寻找增广链 ，若无，则结束； 4、令 ； 5、按上一式子调整流量，得新流 ； 6、转2。 例、图表明一个网络及初始可行流，每条边上的有 序数表示 ，求这个网络的最大流。 练习：求网络的最大流。 ３ ５ ３ ５ ４ *