增广容量网络与最大流量（信息系统项目管理师考试）

容量网络与最大流量知识点解析

1.概念

容量网络设G(V,E)是一个有向网络图在V中指定了一个顶点s称为源点(即出发点入度为0记为Vs) 以及另一个顶点t,称为汇点(即结束点 出度为0记为Vt)对于每一条弧(u,v)∈E对应有一个权值c(u,v)>0称为弧的容量。通常把这样的有向网络图G称为容量网络。

正向边与反向边从s到t的一条简单路径若弧(u,v)与该路径方向一致 则(u,v)为正向弧若弧(u,v)与该路径方向相反则(u,v)为反向弧。

可行流每条弧(u,v)上给定一个实数f(u,v)  满足 有0≤f(u,v)≤c(u,v) 则 f(u,v)称为弧(u,v)上的流量。如果有一组流量满足下列条件

源点s流出量=整个网络的流量

汇点t 流入量=整个网络的流量

中间点 总流入量=总流出量。

那么整个网络中的流量成为一个可行流。

最大流在所有的可行流中流量最大的可行流。最大流可能不止一个。

割设G的原始点集为V选出点集S使得源点s∈ST=V-S汇点t∈T则S到T的弧为S到T割记做(S,T)。割的净流f(S,T)

—1—

表示穿过割(S,T)的流量之和 割的容量c(S,T)为所有从S到T的弧容量之和。

最小割所有割集中容量最小的割集。

最大流最小割定理 G中所有流中的最大值等于所有割中的最小容量。

增广路径如果G中任何一条从源点S到汇点T的路径的所有弧均满足正向弧f(u,v)<c(u,v)反向弧f(u,v)>0则称这条路径为一条增广路径。

残留网络在增广路径的过程中每次进行增广操作之后得到的新图称为旧图的残留网络。

度 图中某个顶点所具有的边的数目。在有向图中度分为入度和初度。

入度终止于该顶点的边的数目 顶点被箭头指向。

出度起始于该顶点的边的数目 箭头从顶点指出。

2.最大流量算法

了解了一些基本概念后对网络最大流量有了一个基本的认识 可能有些概念解释不是特别清楚但这并不影响考试答题。在考试过程中 我们是要如何尽快找到正确的答案。下面简单列举一些网络最大流量的算法并就考试需要掌握的算法解读一道书上的例题。

最大流量常见的算法有基于增广路径的一般增广路算法F ord-Fulkerson、最短增广路算法Edmonds-Karp、连续最短

—2—

增广路算法Dinic及基于预流推进一般预流推进算法、先进先出预流推进算法、最高标号预流推进算法。这里重点了解基于增广路径的一般增广路算法F ord-Fulkerson。

一般增广路算法思路是若网络中存在增广路径 则找出一条增广路径沿着找出的增广路径进行更新流量 不断重复该过程直到没有可增广路径为止。 当没有增广路径时 网络达到最大流。

例 下图标出了某地区的运输网络各节点之间的运输能力单位万吨/小时如表格所示。请问节点1-6的最大运输能力为多少万吨/小时

—3—

1.根据表格数据将两点之间运输数据及方向 箭头表示标注到图中如下图

2.选择路线①③⑤⑥该路线运输能力受①③影响 因此该路线的最大运输能力为10万吨此时最大流量=10断开①③。③⑤、⑤⑥运输能力分别剩余4万吨 14-10、 11万吨21-10更新后如下图

3.选择路线①②⑤⑥该路线运输能力受①②影响 因此该路线的最大运输能力为6万吨此时最大流量=10+6断开①②。②⑤、⑤⑥运输能力分别剩余1万吨7-6、 5万吨 11-6更新后如下图

—4—

4.选择路线①④⑥该路线运输能力受④⑥影响 因此该路线的最大运输能力为5万吨此时最大流量=10+6+5断开④⑥。①④运输能力剩余5万吨 10-5 如下图

5.选择路线①④③⑤⑥该路线运输能力受④③影响 因此该路线的最大运输能力为1万吨 此时最大流量=10+6+5+1断开④③。①④、③⑤、⑤⑥运输能力分别剩余4万吨5-1 、 3万吨4-1 、 4万吨5-1 更新后如下图

6.到这一步只剩下路线①④②⑤⑥该路线运输能力受②⑤

—5—

影响 因此该路线的最大运输能力为1万吨 此时最大流量=10+6+5+1+1 断开②⑤。①④、④②、⑤⑥运输能力分别剩余3万吨4-1 、 3万吨4-1 、 3万吨4-1 更新后如下图

7.此时 网络中①到⑥之间已经没有通路 因此该网络的最大流量为23吨。

—6—