最小割,网络流和强连通分量

jys posted @ Mar 15, 2014 03:44:43 PM in 未分类 , 886 阅读

令G'为残量网络G在缩强连通分量之后的图

一定在最小割方案中的边:<u,v>满流,且在G'中u=S,v=T

可能在最小割方案中的边:<u,v>满流,且在G'中u!=v

对二分图而言

在最大流方案中一定满流的边:<u,v>满流,且在G'中u!=v

在最大流方案中可能满流的边:<u,v>满流,或(<u,v>流量为0,且在G'中u=v)


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter