相关概念与定理的分析介绍

视频-6．4．1最大流概念1

视频-6．4．1最大流概念2

视频-6．4．1最大流概念3

(1)弧容量与容量网络。

弧容量:对于有向图D＝(V,A),弧aij(vi,vj)的容量cij表示弧的最大流通能力。

容量网络:在V中指定一点称为发点(记为vs),另一点称收点(记为vt),其余点称中间点,这样的赋权有向图就称为一个容量网络,记为N＝(V,A,C)。图6-34所示为一个容量网络,每段弧上有权,左边表示容量,右边表示流量,左边大于等于右边。

图6-34

(2)弧的流量与可行流。

弧的实际通过量称为该弧的流量。弧集A上的流量集合f＝{xij}称为网络上的流。满足下述三个条件的流称为可行流:

①容量限制条件:对每条弧(vi,vj)∈A,都有0≤xij≤cij;

②中间点平衡条件:对于任意中间点,流出量＝流入量;

③发点流出量＝收点流入量。(www.xing528.com)

(3)前向弧与后向弧。

设μ是从vs到vt的路,方向从vs→vt,则路μ上的弧分为以下两类:

①前向弧:弧的方向与路μ的方向相同,记为μ＋。

②后向弧:弧的方向与路μ的方向相反,记为μ－。

(4)饱和弧与非饱和弧。

若将弧(vi,vj)的流量xij与其容量cij进行比较,则满足xij＝cij的弧称为饱和弧,弧的流量不允许增加;满足xij＜cij的弧称为非饱和弧,弧的流量允许增加。

(5)零弧与非零弧。

满足xij＝0的弧称为零弧。由于xij＝0,因此零弧的流量不能减小;满足xij＞0的弧称为非零弧。弧的流量可以减小,但要满足xij≥0。

(6)可以扩充流量的路(增广链)。

设f＝{xij}是一个可行流,μ是从vs到vt的路,若μ满足以下两个条件,则称其是一条关于可行流f的可以扩充流量的路,通常称为增广链。

①μ上所有的前向弧为非饱和弧,即满足0≤xij＜cij,μ可以扩充流量;

②μ上所有的后向弧为非零弧,即满足0＜xij≤cij,μ可以减少流量。

(7)网络流量与最大流。

在可行流中,网络发点的流出量(或网络收点的流入量)就是网络的流量。一个容量网络中,网络流量中最大的可行流,称为最大流,可记为f∗。

(8)网络最大流定理。

设f＝{xij}是网络N中的一个可行流,并且对于{xij}来说,不存在可以扩充流量的路(增广链),则{xij}为最大流。