I was wondering what the relationship between the Ford-Fulkerson Method and the

Question

I was wondering what the relationship between the Ford-Fulkerson Method and the idea of min cuts is. I understand that the max-flow min-cut theorem relates the the idea of min-cuts and the lack of an augmenting path to the max flow, and that the ford-fulkerson method relies on the idea of augmenting paths to find the max flow. What I'm wondering is why did we need to introduce the idea of min-cuts at all? It seems that all we need to know to calculate the max flow is the idea of residual networks, augmenting paths, and the Ford-Fulkerson Method. Was the portion about max cuts added for completeness, or does the Ford-Fulkerson Method rely of the idea of min cuts somehow?

Explanation / Answer

Relationship between FordFulkerson method and minimum-cut theorem:

In order to show that no better flow exists that found by Ford-Fulkerson

   Let us show that the Ford-Fulkerson flow uses the full capacity of every edge in some s-t cut
   where,
        s-t cut - It is defined by a partition of the vertices into two sets S and T where s is in S and t is in T
       Edges in the cut are all edges that cross the partition

   Let,
        f' - final flow produced by the Ford-Fulkerson algorithm
   S - define S as the set of all vertices reachable from s in the final residual graph Gf'
   T as the set of all vertices not in S.

Consider some edge uv in the original that crosses the cut. Because u is reachable from s in Gf' and v is not, uv cannot appear as an edge in Gf. This means that cuv - f'uv = 0 and that uv is saturated. Since this is true for any such edge, the final flow f saturates all edges that cross the cut.

This fact is enough to show that f' is a maximum flow. Consider any other flow f, and recall that fuv = -fvu by definition; so for any set A, u in A, v in A fuv = 0, because every edge appears once as fuv and once as fvu.

Now compute
u in S, v in G fuv
= u in S, v in S fuv + u in S, v in T fuv
= u in S, v in T fuv.

The above computation shows that the total net outflow from all nodes in S equals the total flow across the S-T cut. But we also know that the total net outflow from any node in V-{s,t} is zero, so

u in S, v in G fuv
= v in G fsv + u in S-s, v in G fuv
= v in G fsv.

So the size of the flow equals the flow across the cut. But this is limited by the capacity of the cut, which is the sum of the capacities of the S-T edges:

v in G fsv
= u in S, v in T fuv
u in S, v in T cuv
= u in S, v in T f'uv
= v in G fsv.

Let us observe a few things discussed here:

a)The first is that the size of any s-t flow is bounded by the capacity of any s-t cut, and in particular that the size of the max flow is less than or equal to the capacity of the min cut.

b)The second is that the size of any s-t flow is less than or equal to the size of the Ford-Fulkerson flow, which shows that the Ford-Fulkerson flow is maximum.

We can identify something about max flows and min cuts. Because the Ford-Fulkerson flow saturates some cut, its size equals the capacity of some cut so the size of the maximum flow is at least as big as the size of the minimum cut. Since we already showed it's no bigger, they must be equal.

This gives the Max-flow min-cut theorem

Max-flow min-cut theorem:

In any graph G with capacities, the maximum size of any s-t flow equals the minimum capacity of any s-t cut.
A consequence of the max-flow min-cut theorem and the analysis above is that finding a maximum flow also finds a minimum cut, by constructing S and T as above. Using this we can solve the zombie-diversion problem.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.