扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 网络与最大流量中等
单选题
2022年5月第44题
中等
单选题
2022年5月第44题
#第二版教材
#必须掌握
某地天然气输送管线网络图如下，每段管线旁的数字表示输气能力（单位：万立方米/小时）。根据该图，从源S到目的地T的最大输气能力为（【9】）万立方米/小时。
问题（1）
浓缩知识点
最大流问题是指在有向连通图中，求解从源点到汇点的最大可行输送流量的问题，这类问题广泛应用于管网运输、数据网络传输等场景。Ford-Fulkerson方法是求解最大流的经典核心方法，其核心逻辑是不断寻找从源点到汇点的增广路径，也就是仍存在剩余输送能力的路径，每次找到路径后，以该路径上各段的最小剩余容量为本次可增加的流量，同时对路径上各段的剩余容量进行调整，扣除本次新增的流量，反复执行这个过程直到找不到新的增广路径，此时累计的总流量即为最大流。需要注意，增广路径的选择顺序会影响算法的迭代次数和运行效率，不同选择顺序可能让迭代次数有明显差异，但最终得出的最大流结果是统一的。
正确答案
C
根据题意，这是一个最大流问题，我们要找出从源点 S 到汇点 T 的最大输气能力（即最大流）。
我们采用增广路径 + 容量调整（Ford-Fulkerson 方法） 来逐步求解。
本题要求从结点1到结点6的最大流量，其实就是把从结点1到结点6所有的路径找出来，然后把每条路径的流量进行累加。B 站芝士架构凯恩有详细的解答和案例。
此题通过分析可以知道，总共抽取流量：3+2+2+1+1=9，最大输出能力为9万立方米/小时。
需要注意的是“增广路径 + 容量调整”方法本质上是 Ford-Fulkerson 算法的核心思想，其本身并不保证每次找到的是“最优路径”，即：每次找到的增广路径不是总是“最短的”或“最大容量的”路径，因此路径的选择顺序不同，可能导致算法运行效率差，甚至需要更多次迭代才能达到最大流。
