流网络的切割

1.了解网络流算法原谅必须要弄懂 最大流最小切割定理 2.把图的点分成两个部分，S,T 设f为一个流，

体内容看书。 3.对于给定一个流f，横跨任何切割的净流量都相同， 都等与|f|,就是流的值，这个很重要，有证明的。 这个可以推出，一个流网络中的最大流的值不能超 过网络的最小切割的容量。容量为集合点的输入流总和。 5,由4 可以知道,也是一个定理：最大流的值其实等于 最小切割的容量。 （2）在残存网络里没有任何一条zhen广路径。（3）f=c(s,t). 好了写个那么多定理， 来讲讲自己是怎么想的， 一条增广路径 这时候 在残存图里，从S出发s源点出 发不会找到一条到汇点t的路径，我们可以把图里的 点V 分成两个部分，S集合里是 从s出发能到达的所 有的点，V-S可以表示为另外一个集合T，和流切 割有关了吧。设点u在S内，v在T内，在残存图里 this time 会想 u->v 是否有边呢，那当然不会啦 ，因为有边的话 v 就该属于S啦。幸运的是会有边v->u, 未完，先睡觉。