What is S-D cut? For the following network flow find the maximal flow from S to D.

 

What is S-D cut? For the following network flow find the maximal flow from S to D.

This answer is restricted. Please login to view the answer of this question.

Login Now

A S-D cut of transparent network is edge whose removal will divide the network into two halves X and x̅ where

  • Source vertext S ∈ X
  • Sink Vertex D ∈ X

It is denoted by (X, Y)

Let’s find maximum flow from S to D using S-D cut method.

X Y cuts(X, Y) Capacity K(X, Y)
{S} {a, b, c, d, e, f, D} {(S, a), (S, c)} 15 + 15 = 30
{S, a} {b, c, d, e, f, D} {(S, c), (a, b), (a, f)} 15 + 7 + 9 = 31
{S, c} {a, b, d, e, f, D} {(S, a), (c, b), (c, d)} 37
{S, a, b} {c, d, e, f, D} {(S, c), (a, f), (b, d), (b, f)} 34
{S, b, c} {a, d, e, f, D} {(S, a), (b, d), (b, e), (b, f)} 40
{S, b, c, d} {a, e, f, D} {(S, a), (b, e), (b, f), (d, D)} 45
{S, a, b, c} {d, e, f, D} {(a, f), (b, f), (b, e), (f, D)} 34
{S, a, b, f} {c, d, e, D} {(S, c), (b, d), (e, d), (f, D)} 45
{S, a, b, e, f} {c, d, D} {(S, c), (b, d), (e, d), (e, D), (f, D)} 44
{S, a, b, c, d, e, f} {D} {c, d, D}{(d, D), (c, b), (f, D)} 35
{S, a, b, c, d} {e, f, D} {(a, f), (b, e), (b, f), (d, D)} 39
{S, b, c, d, e} {a, f, D} {(S, a), (b, f), (d, D), (e, f), (e, D)} 44

Here, the minimum cut  = 30

So, by minimum cut, Maximum flow is 30

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .