■通过上述实例分析,包含了流量因素的问题,是一类特殊 的图; 口引例给出的交通网,其实具体的物理模型是多种多样的: 网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、 天然气站之间的输气管道等; 边的容量则可以表示为允许通过的物资数量、汽车数量、速率或最大 信号流量等。 口这一类特殊的图,称为网络流图; 网络流图中需要解决的基本问题 口最大流问题 口最大流最小割问题 口最小费用最大流问题
21 ◼ 通过上述实例分析，包含了流量因素的问题，是一类特殊 的图； 引例给出的交通网，其实具体的物理模型是多种多样的： ◼ 网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、 天然气站之间的输气管道等； ◼ 边的容量则可以表示为允许通过的物资数量、汽车数量、速率或最大 信号流量等。 这一类特殊的图，称为网络流图； ◼ 网络流图中需要解决的基本问题 最大流问题 最大流最小割问题 最小费用最大流问题
流网络G=(V,E)是一个有向图,其中每条边(u,)∈E均有 个非负容量c(u,v)>=0; 如果(uv)不属于E,则假定c(uv)=0; ■流网络中有两个特别的顶点:源点S和汇点t; 个流网络的实例(红 色数字表示边的最大容 量,蓝色数字表示边上 的实际流量) 3 )25t 4 22
22 ◼ 流网络G=(V,E)是一个有向图，其中每条边(u,v)∈E均有 一个非负容量c(u,v)>=0； ◼ 如果(u,v)不属于E，则假定c(u,v)=0； ◼ 流网络中有两个特别的顶点：源点s和汇点t； 1 2 3 4 5 4 3 2 6 2 5 4 1 1 3 4 3 s t 一个流网络的实例（红 色数字表示边的最大容 量，蓝色数字表示边上 的实际流量）
■定义:带权的有向图G=(VE),满足以下条件,则 称为网络流图 low network) 口(1)仅有一个入度为0的顶点s,称s为源点( source)或 出发点; 口(2)仅有一个出度为0的顶点t,称t为汇点(sink)或结 束点; 口(3)每条边(u,v)的权值都为非负数,称为该边的容量, 记作c(u,); 口满足上述的条件的图称为网络流图,也可以记作记为 G=(V,E,c)
23 ◼ 定义：带权的有向图G=(V,E)，满足以下条件，则 称为网络流图(flow network)： （1）仅有一个入度为0的顶点s，称s为源点(source)或 出发点； （2）仅有一个出度为0的顶点t，称t为汇点(sink) 或结 束点； （3）每条边(u,v)的权值都为非负数，称为该边的容量， 记作c(u,v)； 满足上述的条件的图称为网络流图，也可以记作记为 G=(V,E,c)
例:一个网络流图: a(容量 3 源点 汇点 13 t 2 c 2 中间点
24 例：一个网络流图： s t a b c d 4 4 3 3 2 2 2 4 1 3 2 源点 容量 汇点 中间点 中间点
对一个流网络G=(V,E,),每条边(u,)上给定一个实数 f(uy,满足:0≤f(uy)≤c(u,y),则f(u,V)称为边(u,v)上的 流量。其中满足f(u,v)=c(u,v)的边称为饱和边。 ■如果有一组流量满足条件: 口源点S:流出量=整个网络的流量 口汇点t:流入量=整个网络的流量 口中间点:总流入量=总流出量 那么整个网络中的流量称为一个可行流。 这个是真实的实体网络中的情况,如果针对通信网络来说,不一定满 足这样的条件:比如对于汇点来说,流入量可能大于整个网络的流量 (当然多的那些是重复的,但是它们还是占用了网络资源) 25
25 ◼ 对一个流网络G=(V,E,c)，每条边(u,v)上给定一个实数 f(u,v)，满足：0≤f(u,v) ≤ c(u,v)，则f(u,v)称为边(u,v)上的 流量。其中满足f(u,v)=c(u,v)的边称为饱和边。 ◼ 如果有一组流量满足条件： 源点s：流出量= 整个网络的流量 汇点t：流入量= 整个网络的流量 中间点：总流入量= 总流出量 那么整个网络中的流量称为一个可行流。 这个是真实的实体网络中的情况，如果针对通信网络来说，不一定满 足这样的条件：比如对于汇点来说，流入量可能大于整个网络的流量 （当然多的那些是重复的，但是它们还是占用了网络资源）