[prev] 38 [next]

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