返回
当前 - 选择题 - 网络与最大流量网络与最大流量
中等
高频
某石油管理公司拥有下图所示的输油管道网。其中有6个站点，标记为①～⑥。站点①是唯一的供油站。各站点之间的箭线表示输油管道和流向。箭线边上标注的数字表示该管道的最大流量（单位：百吨／小时）。据此可算出，从站点①到达站点⑥的最大流量为（16）百吨/小时，而且当管道（⑤→④）关闭维修时管道网仍可按该最大流量值向站点⑥供油。
浓缩知识点
知识点网络最大流指的是从网络源点到汇点的最大可行传输量，计算时常用增广路径法：通过反复寻找从源点到汇点的增广路径（路径上每条边剩余传输容量大于0），累加各条增广路径的最小剩余容量，直至无法找到新的增广路径，所得总和即为网络最大流。判断边的关键性时，若某条边的实际传输流量为0，也就是残量等于初始最大容量，未被纳入任何构成最大流的路径中，那么关闭这条边不会影响网络的最大流；若边的传输流量已达上限，则属于关键边，关闭会导致最大流下降。与之相关的核心定理为最大流最小割定理，即网络的最大流值等于能将源点与汇点分隔开的最小割集的容量，这一定理为最大流的计算与网络流量分析提供了重要理论支撑。
正确答案
C
问题 1：
我们要从图中找出从源点①到汇点⑥的所有可能路径，并利用增广路径的方法反复寻找路径直到无法增广，最后所有路径的最小残余流量之和即为最大流量。在给出的残量图中，我们直接读取3条有效路径的传输量，最终得出最大流为16。