§91网络与网络流的基本概念 定义9.1.1一个网络N=(V,A)是指一个连通无环弧且满足下列条件的有向图 (1)有一个顶点子集X,其每个顶点的入度都为0 (2)有一个与Ⅹ不相交的顶点子集Y,其每个顶点的出度都为0 (3)每条弧都有一个非负的权,称为弧的容量。 注:上述网络N可写作N=(V,X,Y,A,C),X称为网络的发点集或源点集,Y称为网络的 收点集或汇点集,C称为网络的容量函数。 例 14|3 定义9.2网络N=(V,X,Y,A,C中的一个(可行)流是指定义在A上的一个整值函数/, 使得: (1)对va∈A,0≤f(a)≤c(a),(容量约束) (2)对vv∈V-(X∪Y),∫(v)=f(v),(流量守恒) 其中∫(ν)表示点ν处入弧上的流量之和,∫(v)表示点v处出弧上的流量之和 注:(1)可行流总是存在的,比如∫≡0。 (2)现实问题中有许多关于网络和流的实例。 比如:产销物资输送网络;输油管线网络;通信数据传输网络等。 定义9.3设∫是网络N=(VX,Y,A,C)中的一个可行流,则必有∫+(X)=f()。 ∫(X)(或∫(Y)称为流∫的流量,记为alf。 网络最大流问题:给定网络N=(V,X,Y,A,C,求N中流量最大的可行流(称为最大流) 注:如果一个网络中的源点集和汇点集都只含一个顶点,则称该网络为单源单汇网络。任 一网络N=(VX,Y,A,C)都可导出一个单源单汇网络。方法如下: (1)给N添加两个新顶点s和t; (2)对x∈x,从s向x连一条弧,其容量为∞(或∑c(s) (3)对vy∈y,从y向t连一条弧,其容量为∞(或∑c(u1)。 新添的顶点s和t分别称为人工源和人工汇,所得的新网络为NW',s,t,A,C)。§9.1 网络与网络流的基本概念 定义 9.1.1 一个网络 N=(V,A)是指一个连通无环弧且满足下列条件的有向图： (1) 有一个顶点子集 X，其每个顶点的入度都为 0； (2) 有一个与 X 不相交的顶点子集 Y，其每个顶点的出度都为 0； (3) 每条弧都有一个非负的权，称为弧的容量。 注： 上述网络 N 可写作 N=(V, X, Y, A, C)，X 称为网络的发点集或源点集，Y 称为网络的 收点集或汇点集，C 称为网络的容量函数。 例： 定义 9.1.2 网络 N=(V, X, Y, A, C)中的一个(可行)流是指定义在 A 上的一个整值函数 f， 使得： (1) 对∀∈ ≤ ≤ a A f a ca ,0 () () ，(容量约束); (2) 对 vV X Y f v f v ( ), ( ) ( ) − + ∀∈ − = ∪ ，(流量守恒)。 其中 f ( ) v − 表示点 v 处入弧上的流量之和， f ( ) v + 表示点 v 处出弧上的流量之和。 注：(1) 可行流总是存在的，比如 f ≡ 0。 (2) 现实问题中有许多关于网络和流的实例。 比如：产销物资输送网络；输油管线网络；通信数据传输网络等。 定义 9.1.3 设 f 是网络 N=(V, X, Y, A, C)中的一个可行流，则必有 f ( ) () X fY + − = 。 f ( ) X + (或 f ( ) Y − )称为流 f 的流量，记为Val f 。 网络最大流问题：给定网络 N=(V, X, Y, A, C)，求 N 中流量最大的可行流(称为最大流)。 注：如果一个网络中的源点集和汇点集都只含一个顶点，则称该网络为单源单汇网络。任 一网络 N=(V,X, Y, A, C)都可导出一个单源单汇网络。方法如下： (1) 给 N 添加两个新顶点 s 和 t； (2) 对∀ ∈x X ，从 s 向 x 连一条弧，其容量为∞ (或 ( ) (, ) vN s csv + ∈ ∑ ); (3) 对∀ ∈y Y ，从 y 向 t 连一条弧，其容量为∞ (或 ( ) (,) uN t cut − ∈ ∑ )。 新添的顶点 s 和 t 分别称为人工源和人工汇，所得的新网络为 N V stA C ′( ,,, , ) ′ ′′ 。 y1 x2 x1 v2 y3 v1 x3 y2 v3 v4 4 4 4 2 2 2 2 2 2 2 2 2 2 2 2 1 1 3 v1 y v3 v2 v4 x2 x1 3 6 5 2 1 4 3 5 2 2 3