网络流基本概念

对于交通网、管道网，都有物质流动的问题，在交通网中，有人、车辆的流动；在管道网中有流体（水、油等）的流动等等。这种网络中的物质流动称为网络流。

下面介绍与网络流有关的一些基本概念。

（1）流量：表示某时间内通过弧（j i v v ）的物质数量，记为ij f ，他是网络流问题中待求解的变量。网络中的总流量用v(f)表示。

（2）容量：弧的最大允许流通量，一般用ij c 表示。

（3）可行流：在实际的网络中，网络流应满足下面两个条件：

1) 容量限制条件：对于没一个弧{j i v v }∈A ，A 为弧集来说，ij c f ≤≤ij 0。即通过每条弧

的流量不能超过该弧的容量。

2) 平衡条件：对于始点s v ，流入始点的流量等于网络中的总流量，即

()f v f f A v v js A v v sj s j j s =-∑∑∈∈)()(

对于终点t v ，流出终点的流量等于网络中的总流量，即

()f v f f A v v jt A v v tj t j j t -=-∑∑∈∈)()(

对于仍以中间的顶点()t s i i ,≠，流进某中间顶点的流量等于流出盖顶点的流量。即 0)()(=-∑∑∈∈A v v ji A v v ij i j j i f f

在网络分析中，满足上面两个条件的流动，称为可行流。

（4）零弧与非零弧：满足 的弧称为零弧。由于 ，所以弧的流量不能减小；满足 的弧称为非零弧。弧的流量可以被减小，但要满足 0。

（5）饱和弧和非饱和弧：网络中流量等于容量（即ij f =ij c ）的弧称为饱和弧。流量小于容量（即ij f

（6）正向弧和反向弧：设μ是网络中从始点s v 到终点t v 的一条链。凡与链走向一致的弧称为正向弧+μ，逆向的称为反向弧-

μ。

（7）增广链：从始点s v 到终点t v 的一条链上的各弧，若对于某一可行流ij f 来说，满足下面两个条件，则称该链式对于可行流ij f 的增广链。

1) 对于正向弧，满足条件ij f

2) 对于反向链，满足条件ij f >ij c 。

这就是说，在增广链上的正向弧都是非饱和弧。反向弧都是非零流弧。很显然，沿着这条增0ij x ≥ij ij x b =0ij x >ij x ≥

广链可以继续增加流量，起增量 ????????-=-+μμβji ij ij f f c ,min