Ford-Fulkerson Algorithm & Max Flow Min Cut Theorem

3
votes

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?

2
algorithmgraph-theoryford-fulkerson
Well after the algorithm is done, you make a cut (it does not matter which cut), and you sum up the flow of all edges that pass the cut, and then you come up with 19. – Willem Van Onsem
Ah. I noticed that I mistakenly calculated expense of cut with Capacity.. not flow. Thank you so much – Jiseop Han
Hi Jiseop. Solved how exactly? If you mean by the answer below, you mark a question as solved by checking the checkmark next to the answer. If not, perhaps you could add your own answer. Marking the title of your question with "solved" is not how things are done on Stack Overflow. You can read this for more information on this: What should I do when someone answers my question? In the meantime, I've rolled back your question to remove the "solved" from the title. – TT.
@JiseopHan you absolutely do calculate the expense of the cut with capacity. – Matt Timmermans

2 Answers

2
votes

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.

2
votes

A cut means that you define a cut between the source and the drain. That cut does not have to be a straight line, a curve, or any other shape is sufficient.

For example here I picked as blue cut such that the edges AB, AD and CD are passing the cut. Now if we look at the assigned flow of these edges, and we sum these up, we obtain 4+6+9=19.

An alternative cut is for example the one in green. Here we have edges BT, AD and AC that move "forward", and an edge DC that moves "backwards". So the sum of the flows is then 9+6+9-5=19. So regardless what cut we take, the sum is always 19 (of course we need to do the proper bookkeeping, and subtract flows in the opposite direction).

Of course you can pick any cut you want (for example a cut just after the source, or just before the drain), if the algorithm is done correctly, then the sum of all these cuts is always 19. This is logical, since if the flow of one cut would be more (or less) then 19, then the existence of a cut that "advances" one node that has a flow of 19, means that in that node, flow has disappeared, or appeared.

It however holds that if you would iterate over all possible cuts, then the minimum cut is the one where the sum of the capacities is maximized. So we can, strictly speaking, iterate over all possible cuts, and each time keep track of the sum of the capacities, and at the end, select the one with the smallest flow. A naive approach if simply iterating all cuts, would however result in an O(2n) algorithm, which is, compared to the Ford–Fulkerson algorithm, of course not desirable.

two cuts at the end of the algorithm