运筹学 Operations Research §6.6最大流问题 在生产生活中有许多网络,如电网、供水网、原油管道 运输网、交通运输网、通讯网、国际互联网等.以供水网络 为例,设仅有一个出水口和一个进水口.网络每段管道都有 个容量(单位时间内通过管道的最大水量).水由出水口 流出经过水管网络后流入进水口,这就形成一个水的实际的 稳定的有向的流动,称之为流 显然,流具有如下性质: (1)每段管道中通过的流量不超过该管道的容量; (2)网络的每个内部顶点处的流入量等于与流出量; 3)出水口的总流出量等于进水口的流入量.因受自身 网络结构的限制,通过水管网络的流必有一个最大界限,称 之为最大流 2021/2/202021/2/20 1 运 筹 学 Operations Research 在生产生活中有许多网络，如电网、供水网、原油管道 运输网、交通运输网、通讯网、国际互联网等．以供水网络 为例，设仅有一个出水口和一个进水口．网络每段管道都有 一个容量（单位时间内通过管道的最大水量）．水由出水口 流出经过水管网络后流入进水口，这就形成一个水的实际的 稳定的有向的流动，称之为流． 显然，流具有如下性质： （1）每段管道中通过的流量不超过该管道的容量； （2）网络的每个内部顶点处的流入量等于与流出量； （3）出水口的总流出量等于进水口的流入量．因受自身 网络结构的限制，通过水管网络的流必有一个最大界限，称 之为最大流． §6.6 最大流问题