二、网络最大流问题 最大流问题就是在一定条件下,使网络系统中 的某种流的流量达到最大的问题 例如:公路系统中的车辆流;水利系统中的水流;电 力系统中的电流;服务系统中的顾客流,信息系统中 的信息流等等
二、网络最大流问题 最大流问题就是在一定条件下,使网络系统中 的某种流的流量达到最大的问题. 例如: 公路系统中的车辆流;水利系统中的水流;电 力系统中的电流;服务系统中的顾客流,信息系统中 的信息流等等
如图为某物资的运输网络问从v到v的最大运输流 量是多少?弧线边的数字表示路线的容量,即 该弧的能够容纳的最大流量
如图为某物资的运输网络,问从vs到vt的最大运输流 量是多少? 弧线边的数字表示路线的容量,即 该弧的能够容纳的最大流量. 1 vs 2 3 4 vt 9 5 3 4 3 5 2 7 6
1基本概念 对一个网络D=(V,4) (1)网络流指在一定条件下流过一个网络的某种流 在各弧上的流量的集合 一定条件指 ()有一个起点v和终点v; Gi流过网络的流量有一定的方向; (i每一弧都有一个容量表示容许通过该 弧的最大流量 (2弧(%)的容量记为r; (3弧(vp)的流量记为x;:流X{x引(vv∈A}
1.基本概念: (1)网络流:指在一定条件下流过一个网络的某种流 在各弧上的流量的集合. 对一个网络D=(V,A) 一定条件指: (i)有一个起点vs和终点vt ; (ii)流过网络的流量有一定的方向; (iii)每一弧都有一个容量,表示容许通过该 弧的最大流量. (2)弧(vi , vj )的容量记为rij ; (3)弧(vi , vj )的流量记为xij ;流X={xij| (vi , vj ) A}