Sidetrack: Maxflow and Mincut
Given: flow network G=(V,E) with
- edge weights w(u,v)
- source s∈V, sink t∈V
Cut of flow network G …
- a partition of V into S ∪ T
- s∈ S, t∈T, S and T disjoint
- its weight is the sum of the weights of the edges between S and T:
`ω(S,T) = sum_(u in S) sum_(v in T) w(u,v)`
Minimum cut problem … find cut of a network with minimal weight
|