Max Flow Min Cut

501 views Asked by At

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

1

There are 1 answers

0
Amin Abouee On

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