周承贵

（桂林理工大学南宁分校，广西 南宁 530001）

谈谈有向图的一个应用
—— 求网络最大流问题

周承贵

（桂林理工大学南宁分校，广西 南宁 530001）

网络最大流是一类应用很广泛的问题，有十分重要的现实意义，本文给出一种求网络最大流的有效快捷的算法，此算法使计算网络最大流变得简便且具有很强的实用性。

源汇；增广链；最大流

1 引言

图论中讨论的网络最大流是一类应用十分广泛的问题。比如现实生活中的交通系统中有人流、车流、货物流等；金融系统中有现金流；通信系统中有信息流；供水（油）系统中有水（油）流等，解决这类系统优化问题有十分重要的现实意义。

2 基本概念

［定义1］在有向图（网络图）中，只有流出量而没有流入量的顶点称为源；只有流入量而没有流出量的顶点称为汇；既有流入量也有流出量的顶点称为中间点；图中每一条弧一般都标注有两个权数（Cij，fij），其中前一个权Cij表示这条弧能容纳的最大流量，称为弧的容量，后一个权数fij表示该条弧现有的流量，称为弧的现有流量。若现有流量等于弧的容量，则称该弧为饱和弧，否则称不饱和弧。特别地，若弧的现有流量为0，则称该弧为零流弧，否则称非零流弧。

［定义2］若在一个网络图中每一条弧满足0≤fij≤Cij且中间点的流入量和流出量相等，同时源的流出量和汇的流入量也相等，则称网络图存在可行流。

所谓最大流问题就是在网络图中寻找流量最大的可行流。

3 网络最大流的求法

3.1 增广链的定义

［定义3］设f是一个可行流，若A是从VS到Vt的一条增广链，则A应该满足以下条件：①与前进方向一致的弧（称前向弧，记作A＋）为非饱和弧；……