企源知识库

某地区的公路网如图所示，图中V₁，……，V₆为地点，边为公路，边上所赋的权数为该段公路的流量（单位为千辆/小时），请求出V₁ 到V₆ 的最大流量。

解：第一次迭代：选择路为V₁ →V₃ →V₆ 。弧（V₃ ，V₆）的顺流流量为5，决定了p_f=5，改进的网络流量图如图所示：

第二次迭代：选择路为V₁ →V₂ →V₅ →V₆ 。弧（V₁ ，V₂）的顺流流量为6，决定了p_f=6，改进的网络流量图如图所示：

第三次迭代：选择路为V₁→V₄ →V₆ 。弧（V₁ ，V₄）的顺流流量为6，决定了p_f=6，改进的网络流量图如图所示：

第四次迭代：选择路为V₁→V₃→V₄ →V₂→V₅→V₆ 。弧（V₂ ，V₅）的顺流流量为2，决定了p_f=2，改进的网络流量图如图所示：

第五次迭代：选择路为V₁→V₃→V₄→V₅→V₆ 。弧（V₁ ，V₃）的顺流流量为3，决定了p_f=3，改进的网络流量图如图所示：

在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流容量都大于零，运算停止。我们已得到此网络的从 V₁到V₆的最大流量，最大流量为22，也就是公路的最大流量为每小时通过22千辆车。（此题也可以使用标号法进行求解）