第十一章 网络
§11.1 流
*作为商品从产地运送到市场必经之途的运输网络,把它看作是具有
某些附加结构的有向图时,可以进行极为有效的分析。
网络:一个网络 N 是指一个具有两个特定顶点子集 X 和 Y 的有向图
D(称为 N 的基础有向图),以及一个在 D 的弧集 A 上定义的非负整数
数值函数 c;假定顶点集 X 和 Y 是不相交的和非空的。
称 X 中的顶点是 N 的发点,Y 中的顶点是 N 的收点,既不是发点又
不是收点的顶点称为中间点;所有中间点的集合记为 I。
称函数 c 是 N 的容量函数,它在弧 a 上的值称为 a 的容量。一条弧
的容量可以看作沿着这条弧输送商品所能允许的最大流量,而发点对
应于产地,收点对应于市场。
一个网络的例子:(见图 11.1)
若则用
表示。
若 f 是定义在 N 的弧集 A 上的实值函数,并且,则用 f(K)表示
。
若 K 是形为
的弧集,则把
写成
,而把
写成
。
流:网络 N 中的流是指定义在 A 上的一个整数值函数 f,使得
评论0