2. 计算机
  3. 下图标出了某地区的运输网。 各结点之间的运输能力如下表： 从结点①到结点⑥的最大运输能力(流量)可以达到( )万吨／小时。

下图标出了某地区的运输网。 各结点之间的运输能力如下表： 从结点①到结点⑥的最大运输能力(流量)可以达到( )万吨／小时。

admin2018-10-14  56
问题 下图标出了某地区的运输网。

各结点之间的运输能力如下表：

    从结点①到结点⑥的最大运输能力(流量)可以达到(    )万吨／小时。
选项 A、26
B、23
C、22
D、21
答案B
解析 这题考的是最大流量问题。
首先把运输能力数据标在图上(注意：结点之间的双向运输能力都是相同的，所以省略了箭头，这是最简单的流量问题)。

接下来寻找从结点①到结点⑥的运输能力最大的那条路径(注意：每条路径上的最大流量应是其各段流量的最小值)，路径①③⑤⑥运输能力最大，为10万吨。
将总运输能力暂时记为10万吨，然后将路径①③⑤⑥上各段线路上的流量扣除10万吨，剩余流量为0的线段则将其删除(比如①一③)。此时的运输网变成了下图。

继续寻找从①到⑥的运输能力最大的那条路径，此时路径①②⑤⑥的运输能力最大，为6万吨。
将总运输能力暂时记为10+6=16万吨，然后将路径①②⑤⑥上各段线路上的流量扣除6万吨，剩余流量为0的线段则将其删除。此时的运输网变成了下图。

重复以上步骤，直至①和⑥之间再无通路。
此时，总运输能力暂时记为10+6+5+1+1=23万吨，过程如下：
(1)路径①③⑤⑥的最大流量为10万吨：
(2)路径①②⑤⑥的剩余最大流量为6万吨；
(3)路径①④⑥的剩余最大流量为5万吨；
(4)路径①④③⑤⑥的剩余最大流量为1万吨；
(5)路径①④②⑤⑥的剩余最大流量为1万吨。
有同学问，如果不是每次都先找最大流量路径，是否也能得出23万吨。
理论上可以证明，不管每次先找流量最大的，还是流量最小的，或是流量居中的路径，都能得出正确答案，最大流量值23万吨是唯一确定的。
转载请注明原文地址:https://www.kaotiyun.com/show/wvFZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

信息系统项目管理师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)