Ford-Fulkerson Algorithm & Max Flow Min Cut Theorem

Question

Hi I have trouble in studying Ford-Fulkerson Algorithm with max-flow min-cut Theorem .

According to the Theorem, The maximum flow should be same as total weight of edges being cut.

However, seeing the video https://www.youtube.com/watch?v=Tl90tNtKvxs, it gives me confusion. The lecturer says that the maximum flow is 19 according to Ford-Fulkerson Algorithm but I cannot find any cut with expense of 19. What is wrong?

Answer 1

Nothing is wrong with your interpretation of the max-flow min-cut theorem.

The minimum cut set consists of edges SA and CD, with total capacity 19.

To make a cut and calculate it's cost, you can:

1. Divide all the vertices into 2 sets, S and D, such that the source is in S and the drain is in D.
2. Cut all the edges from a vertex in S to a vertex in D. Note that you don't need to cut the edges that go from D to S.
3. Add up the capacities of the edges you cut.

For the min cut above, S contains vertices s and c, and D contains the rest.