Home [感性认识] 网络流中反向边的正确性
Post
Cancel

[感性认识] 网络流中反向边的正确性

众所周知,求最大流要是没有反向边,基本都是错的

那为什么反向边能修正错误的增广

查了一些资料,好像没有什么严格证明的样子,可能图论还是太复杂了点

不过还是找到了PKU camp的PPT,感觉说的还不错,大概意思就是反向边可用于二路合并

back edge

(你刚才说我画的丑是吧)

考虑某种情况,如图有一条增广路通过\(a \to b\)的路径,\(flow = n\)

那么至少说明,

边\(e1,e4\)有\(cap-flow=n\),

如果此时已经跑不动了,那就只能增广到这里得到最大流\(n\)

假如添加了反向边的机制,发现能\(b \to a\)反向流动\(flow=n-k\)的流量

至少说明,

边\(e2,e3\)有\(cap-flow=n-k\)

此时的情况和图的上半部分对应

添加了反向边后的情况其实等价于下半部分,把\(n-(n-k)\)的流退回去后

我们可以得到最大流\(maxflow=2n+k\)

关键是,这是在不影响其他边的前提下获得的增广(\(e1,e2,e3,e4\)均不受影响)

因此我们可以感性地认为反向边的策略是正确的

This post is licensed under CC BY 4.0 by the author.