82网络最大流 运输网络问题是很大一类网络问题,通 过介绍有些运输网络问题,可以使我们 建立起一些处理网络问题的基本概念和 方法。 这里涉及的运输网络问题只是考虑简单 情况
8.2 网络最大流 运输网络问题是很大一类网络问题，通 过介绍有些运输网络问题，可以使我们 建立起一些处理网络问题的基本概念和 方法。 这里涉及的运输网络问题只是考虑简单 情况
、运输网络 1运输网络的定义 定义87:一个带权有向图G=(,E)若满足如下条件 (1)G是连通无自环的; (2)每条弧(j)的权c为非负整数,称为弧的容量, c全体所构成的集合记为C; (3)存在2个不同的顶点和t 则称该有向图为运输网络,简称网络,记为N(V,E,O) 称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:在网络N(V,E,C)的弧集E上定义了一个非 负整值函数},称为网络N上的流称为弧(i) 上的流量。若无弧(则定义为0。设流瞒满足下 列条件 (1)容量限制条件:对每一条弧(),有 (2)平衡条件:除和t外的每个中间点k有 ∑=∑fk 即流出和等于流入和。 对于s和t有22=2/21=V 则称f为网络N的一个可行流,V为流f值,或称f 流量 若N中无可行流∫,使vr>V则称为最大流
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
108 64 1010 66 4.4 t 4 74 103 定义89:若c,则称弧(动是饱和的;若 f则称弧()是未饱和的。若G则称弧 (i)是f0的;若島>0,则称弧()是/正的 现在的关键是如何求最大流的值
定义 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:设N(V,E,O是有一个发点s和一个收点t 的网络若V划分为P和,使S∈P,t∈P,则从P中 的点到P中的点的所有弧集称为分离s和t的割, 记为(P,P)。 如图8.6中虚线所示,P={s,a,c},P={b,t 若从网络N中删去任一个割,则从s到t之间不存 在有向路。 要说明的是,对同一s,割不唯一
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,割不唯一