05数学(算法)与经济管理

03-网络与最大流量

2021-08-08 178 2

简介 图论应用中的网络与最大流量类型题


题目:

下图标出了某地区的运输路径管道,各节点之间的运输能力如下图所示。那么,从节点①到节点⑥的最大运输能力(流量)可以达到多少万吨/小时?

upfile


解析:

    做这个题之前,我们首先要明白一个问题,如果有三节粗细不同的管道连接起来,那么整个管道的最大流量受限制的是在哪个管道上?


    如图所示:


    upfile

    ABC三个管道,拼接在一起,那么水的流量最大时,那根管道限制了最大水流量? 毫无疑问是C对吧,如果C管道能流5立方/h的水,那么整个ABC管道的最大流量就是5立方/h。


    当然水流的快慢还跟压力有关,这里我们就不去考虑压力了。


    对于本题,我们可以依次分析每一个路径上的最大流量,然后将最大流量“抽取”出来,依次累加,就可以得到1到6的最大流量了。


    步骤1:

    我们就先挑选最大的,依次“抽取”这个最大流量,我们抽取路径1356上的“最大”流量10.


    upfile

抽取后

upfile


再次抽取一个最大的,抽取1256上的最大流量6。

upfile


抽取后


upfile


再抽取146上的最大流量5

upfile

抽取后

upfile

再次抽取14356路径上的最大流量1

upfile


抽取后


upfile


再次抽取14256上最大流量1,

upfile


抽取后的图示

upfile


此时,虽然部分节点之间还有流量,但是无法从1到6连通了,也就是剩下了残余的流量,无法使用。

最终结果,1到6的最大运算能力为

    10 + 6 + 5 + 1 + 1 = 23















点赞 2

文章评论

欢迎您:

纸上得来终觉浅,绝知此事要躬行!

112 文章 36783 浏览 3 评论

联系我

  •   QQ:    361352119
  •  Email:  lisimmy@sina.com
  • 微信: