Last Year Final - Question 08

[Chunwei (Steven) Lai]

I was wondering if my solution for question 8 (flow) is correct:

4 nodes: s, a, b, t (I assume they had a typo and c is t)

From the problem:
e_1 = (s, a) capacity = 4 current flow = 4
e_2 = (s, b) capacity = 5 current flow = 0
e_3 = (a, t) capacity = 3 current flow = 1
e_4 = (b, t) capacity = 3 current flow = 3
e_5 = (a, b) capacity = 4 current flow = 3

Find the residual capacities r(e) and residual path.

The residual capacities:
(s, a) = 0 / (a, s) = 4
(s, b) = 3 / (b, s) = 0
(a, b) = 1 / (b, a) = 3
(a, t) = 2 / (t, a) = 1
(b, t) = 0 / (t, b) = 3

The residual path (this can have multiple answers?):
(s, b) = 2, (b, a) = 2, (a, t) = 2

Steven

[Chunwei (Steven) Lai]

Mistake:

The residual capacities:
(s, b) = 5 / (b, s) = 0 #instead of 3

Also, min cut would divide the nodes into (s, a, b) and (t)

Steven