算法创新与实践论文

4 最大流问题的应用

4.1 实例1 求网络图1 的最大流

（1）用割集矩阵算法求解。写出网络图的流量为单位流的可行流条件。写出方程组的增广矩阵，此矩阵就是割集流量关系矩阵。对矩阵进行运算，得网络割矩阵。网络割矩阵中的常数项全部为1，共16 个，即得到16 个割集。网络割矩阵第一行对应的割集的割容量为3+5=8；第二行对应的割集的割容量为5+2=7；以此类推，可得它们的割容量8、7、11、13、9、7、16、9、10、15、11、6、14、13、5、10。min{8，7，11，13，9，7，16，9，10，15，11，6，14，13，5，10}=5，即网络的最小割容量为5，故该网络的最大流为5。

（2）用表格法求解。给出可行流零流。用表格法寻找一条增流链P1。从终点??6反向追踪其先行顶点，??4从反??4向追踪其先行顶??2，从??2 反向追踪其先行顶点是初始点??1，找到一条增流链??1=??1??2??4??6，此时流量调整值?1=3，可行流的流量??1=3，。对增流链??1 增流；找到一条增流链??2=??1??3??5??6，流量调整值?2，此时可行流的流量??2=?1+?2=5。再对增此为止。此时可行流的流量即为最大流f=5。

（3）用“构造式”算法求解。构造初始“构造图”，图中仅包含节点而不包含边。在以源点??1 为起点的边中找到容量最大的边 ??1,??3 ，使其成为满载边，再以节点??3 为发点找到容量最大的边 ??3,??5 ，使其也成为满载边，但??3,5

（4）用改进算法求解。假设网络初始可行流为零流，找中间点较少的同向路(??1,??2,??4,??6)，，在此路上弧 ??1,??2 容量最小，在此路各弧上均增加弧 ??1,??2 的流量：3，弧 ??1,??2 满值，在上面划“×”。表示此路以后不走。继续找中间点较少的同向路(??1,??3,??5,??6)，，弧 ??3,??5 ， ??5,??6 容量最小，在此路上各弧均增加流量：2，弧 ??3,??5 和 ??5,??6 上划“×”。到此，同向路全部被切断，故得最

8

算法创新与实践论文

大流为f=f ??1,??2 +?? ??1,??3 =5。

4.2 实例2 求网络图2 的最大流

（1）用图单纯性算法求解。标号，找到增广路P1：(??1,??2,??4,??6)，将该路上所有弧的流量都增加??6=2。去掉所有顶点上的标号，重新标号，找到增广路P2：(??1,??3,??5,??6)，将该路上所有弧的流量都增加??6=1。再重新标号，找到改进链??3：(??1,??3,??2,??4,??6)，将该路上所有正向弧的流量都增加??6=1，所有反向弧的流量都减少??6=1。去掉所有顶点上的标号，重新标号，此时标号过程达不到终点，图中不再存在改进链，当前流f=3+3=6 就是最大流。

（2）用数值算法求解。分别写出图2 的费用矩阵B 和容量矩阵C，利用文献的作者根据算法??6 用Visual Basic5.0 设计的名为《规划系统》的应用软件的名叫《最小费用最大流问题》的功能模块，输入费用矩阵B、容量矩阵C 及相关信息n=6，s=1 和t=6 就能快捷地求出图2 的最小费用最大流为6。

9

算法创新与实践论文

5 结论

本文主要讨论了最大流问题六种的算法，通过两个例子对六种算法的具体应用发现：割集矩阵算法通过求出网络图的割集流量矩阵从而得到网络割矩阵，省去了2F 标号法中频繁的画图标号步骤，利用矩阵运算来求得最大流。但由于涉及到矩阵的行、列运算，若网络中节点与弧数目很多的情况下可能会给计算带来困难；利用表格法求解最大流问题可以很快找到主要的增流链，避免了重复计算，既节省计算时间，又不易漏掉增流链，直观性强，计算方便；“构造式”最大流算法是图的深度优先搜索策略应用于传统的前向推进最大流算法而得到的一个改良算法，由于“构造式”算法过程简便，步骤相对较少，不失为一种求解最大流问题的好方法；“断路法”的各步操作可以在一个图中进行，比2F 标号法简明的多，该方法道理简单，步骤易于掌握，是一种求解最大流问题的好方法；图单纯算法，其实质与2F 算法相同，但利用饱和流的概念，为规定寻找增广路的先后顺序提供了理论依据，从而避免了2F 算法的缺陷；数值算法需要借助于计算机，使用起来方便快捷，但是由于需要特殊的软件才能实现，这样也就使该算法在一定程度上难以普遍适用。

10

算法创新与实践论文

参考文献

[1]谢政，李建平.网络算法与复杂度理论[M].长沙：国防科技大学出版社，1995.

[2]许俊明.图论及其应用[M].合肥：中国科学技术大学出版社，1998. [3]党耀国，刘思峰，方志耕.网络最大流的割集矩阵算法[J].系统工程理 论与实践，2003（9）：125-128.

[4] 宁宣熙. 网络最大流的图单纯形解法[J]. 南京航空航天大学学报， 1996，28（5）：626-628.

[5]侯景亮，迟红娟.计算网络最大流的表格法[J].烟台师范学院学报（自 然科学版），2005，21（2）：109-110.

[6]郏宣耀，张帆.求解最大流问题的“构造式”算法[J].深圳职业技术学院 学报，2005（1）：18-20.

11