1

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image?

enter image description here

TheRapture87
  • 1,403
  • 3
  • 21
  • 31
  • What have you tried? and what exactly are you doing? I think this should be asked on a different exchange. It doesn't look like you are coding, just a puzzle... – Evan Carslake May 04 '16 at 18:50
  • @EvanCarslake Max-flow min-cut is an algorithm. I'm trying to get a visual understanding rather than just learning by looking at code. I want to know exactly what is going on. The algorithm is something like - http://www.cse.yorku.ca/~aaw/Wang/MaxFlowMinCutAlg.html – TheRapture87 May 04 '16 at 19:06
  • Possible duplicate of [How can I find the minimum cut on a graph using a maximum flow algorithm?](http://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on-a-graph-using-a-maximum-flow-algorithm) – Evan Carslake May 04 '16 at 20:24

1 Answers1

1

Let me assume:

  1. the vertex in the top of the S is A (S -> A = 6)
  2. the vertex in the right side of S is C (S -> C = 6)
  3. the vertex in the right side of A is B (A -> B = 3)
  4. the vertex in the right side of C is F (C -> F = 3)
  5. the vertex in the bottom of the graph is D (S -> D = 2 )

So the final min-cut edges are:

A -> B = 3

C -> F = 3

S -> D = 2

C -> D = 2

The source vertices also are: S, A, C

Amin Abouee
  • 41
  • 2
  • 5