最小割，网络流和强连通分量
jys
posted @ Mar 15, 2014 03:44:43 PM
in 未分类
, 949 阅读
令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）
评论 (0)