最大流中反向边的作用和意义

流量需要满足三个限制条件:

  1. 容量限制 f(u,v)c(u,v)f(u,v)\leq c(u,v)
  2. 流量守恒 (S,v)ϵE=(u,T)ϵE\sum_{(S,v)\epsilon E}=\sum_{(u,T)\epsilon E}
  3. 斜对称 f(x,y)=f(y,x)f(x,y)=-f(y,x)

斜对称的性质就决定了最大流中需要存在反向的流量(反向边),蒟蒻如我,不懂这样的反向流量的意义何在,于是查了一下资料,算是知道了七七八八。

反向流量的意义就在于,当增广的过程中发现当前流量并非最大流量,那么就可以通过反向的流量将原来流量退回一部分,然后得到一个更大的流量。

借用大犇的例子:
最大流中反向边的作用和意义