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

Question

Suresh Chand · Accepted Answer

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

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

Leave your Answer:

Hits Counter

Question

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

Leave your Answer: