网络最大流8.2下运输网络问题是很大一类网络问题，通过介绍有些运输网络问题，可以使我们建立起一些处理网络问题的基本概念和方法。这里涉及的运输网络问题只是考虑简单情况
8.2 网络最大流 运输网络问题是很大一类网络问题，通 过介绍有些运输网络问题，可以使我们 建立起一些处理网络问题的基本概念和 方法。 这里涉及的运输网络问题只是考虑简单 情况
一、运输网络1.运输网络的定义定义8.7：一个带权有向图G-V,E）若满足如下条件：(1)G是连通无自环的：2）每条弧（ii的权cii为非负整数，称为弧的容量，cii全体所构成的集合记为C；(3）存在2个不同的顶点s和t。则称该有向图为运输网络，简称网络，记为NVE.C)。称s为发点，t为收点，除s和以外其它顶点称为中间点。C称为容量函数
一、运输网络 1.运输网络的定义 定义 8.7：一个带权有向图G=(V,E)若满足如下条件： (1)G是连通无自环的； (2)每条弧(i,j)的权cij为非负整数，称为弧的容量， cij全体所构成的集合记为C； (3)存在2个不同的顶点s和t。 则称该有向图为运输网络, 简称网络，记为N(V,E,C)。 称s为发点, t为收点, 除s和t以外其它顶点称为中间点。 C称为容量函数
2.运输网络N中的流定义8.8：在网络NV.E.C的弧集E上定义了一个非负整值函数，称f为网络N上的流，f称为弧ii）上的流量。若无弧(i.i),则定义为0。设流满足下列条件：(1)容量限制条件：对每一条弧(i),有fi≤cij°(2)平衡条件：除s和外的每个中间点k.有即流出和等于流入和。E-EIZfs-Zf-Z-Zfa=V对于s和t有iejevieviel则称为网络N的一个可行流，V为流的值，或称的流量。若N中无可行流，使V>V，则称f为最大流
2.运输网络N中的流 定义 8.8：在网络N(V,E,C)的弧集E上定义了一个非 负整值函数f={fij}, 称f为网络N上的流, fij称为弧(i,j) 上的流量。若无弧(i,j), 则fij定义为0。设流f满足下 列条件: (1)容量限制条件：对每一条弧(i,j), 有fij≤cij。 (2)平衡条件：除s和t外的每个中间点k, 有 即流出和等于流入和。 对于s和t有 则称f为网络N的一个可行流, Vf为流f的值, 或称f的 流量。 若N中无可行流f', 使Vf'>Vf , 则称f为最大流。 = j V jk i V ki f f f i V ti j V jt j V js i V f si − f = f − f =V
10.104.44,410.3O0定义8.9：若f-Ci，贝则称弧（ii是饱和的：若fi<ci，则称弧(i,)是未饱和的。若f-0,则称弧(i,i是f-0的；若f>0,则称弧(i,j)是f-正的现在的关键是如何求最大流的值
定义 8.9：若fij=cij, 则称弧(i,j)是饱和的; 若 fij<cij, 则称弧(i,j)是未饱和的。若fij=0, 则称弧 (i,j)是f-0的; 若fij>0, 则称弧(i,j)是f-正的. 现在的关键是如何求最大流的值
3.运输网络N中的割定义8.10:设NVE.C是有一个发点s和一个收点t的网络。若V划分为P和p、使 sEPtE P则从P中的点到P中的点的所有弧集称为分离S和的割记为(P,P)。如图8.6中虚线所示,P=/s,a,c,P={b,t)。若从网络N中删去任一个割，则从S到t之间不存在有向路。要说明的是,对同一s,t,割不唯一
3.运输网络 N 中的割 定义 8.10:设 N(V,E,C)是有一个发点 s 和一个收点 t 的网络。若 V 划分为 P 和P , 使 sP,t P ,则从 P 中 的点到P 中的点的所有弧集称为分离 s 和 t 的割, 记为(P, P )。 如图 8.6 中虚线所示, P={s,a,c}, P ={b,t}。 若从网络 N 中删去任一个割, 则从 s 到 t 之间不存 在有向路。 要说明的是,对同一 s,t,割不唯一