05数学(算法)与经济管理
03-网络与最大流量
2021-08-08 545 2
简介 图论应用中的网络与最大流量类型题
题目:
下图标出了某地区的运输路径管道,各节点之间的运输能力如下图所示。那么,从节点①到节点⑥的最大运输能力(流量)可以达到多少万吨/小时?
解析:
做这个题之前,我们首先要明白一个问题,如果有三节粗细不同的管道连接起来,那么整个管道的最大流量受限制的是在哪个管道上?
如图所示:
ABC三个管道,拼接在一起,那么水的流量最大时,那根管道限制了最大水流量? 毫无疑问是C对吧,如果C管道能流5立方/h的水,那么整个ABC管道的最大流量就是5立方/h。
当然水流的快慢还跟压力有关,这里我们就不去考虑压力了。
对于本题,我们可以依次分析每一个路径上的最大流量,然后将最大流量“抽取”出来,依次累加,就可以得到1到6的最大流量了。
步骤1:
我们就先挑选最大的,依次“抽取”这个最大流量,我们抽取路径1356上的“最大”流量10.
抽取后
再次抽取一个最大的,抽取1256上的最大流量6。
抽取后
再抽取146上的最大流量5
抽取后
再次抽取14356路径上的最大流量1
抽取后
再次抽取14256上最大流量1,
抽取后的图示
此时,虽然部分节点之间还有流量,但是无法从1到6连通了,也就是剩下了残余的流量,无法使用。
最终结果,1到6的最大运算能力为
10 + 6 + 5 + 1 + 1 = 23