首页 > 其他 > 详细

最小割最大流定理

时间:2019-05-11 19:13:45      阅读:152      评论:0      收藏:0      [点我收藏+]

先来理解几个概念

在原先能够流通的网络中移除的边集,使得网络无法流通

最小割

所有的割中边权和最小的割即为最小割

可以想象一下,Kido为了自给自足给自己建了超多供水管道(kido能进行光合作用),形成了一个网络,然后容量越大的管道防护设施越好,但是总有人想渴死Kido就想炸掉管道,但是贫乏的恐怖分子既想渴死kido又想节约成本,那么最节约成本的破坏管道的方案即为最小割

技术分享图片

技术分享图片

 

技术分享图片

 最大流最小割定理

在任何的网络中,最大流的值等于最小割的容量

 

最小割最大流定理

原文:https://www.cnblogs.com/graytido/p/10849560.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!