10.5. Ford-Fulkerson Algorithm

Try these first

1. 1.

   Define a flow network.

   Hint

   Think about the flow and paths in a directed graph.

2. 2.

   What does the residual graph represent?

   Hint

   Consider it as the remaining capacity after flow is processed.

3. 3.

   What defines a flow network?

   • A graph where all edges are bidirectional.
   • A directed graph with source and sink nodes.
   • A graph with no edges.

   Hint

   Think about the direction of the flow.

4. 4.

   True or False: Flow conservation means that inflow equals outflow at every node.

   • True
   • False

   Hint

   Consider an intermediate node’s behavior.

5. 5.

   Given a directed graph with capacities: S-A (10), A-B (5), B-T (10), S-C (15), C-B (5), C-T (10), calculate the maximum flow using the Ford-Fulkerson algorithm. Detail each augmenting path.

   Hint

   Identify all possible augmenting paths step-wise.

6. 6.

   A flow network has nodes: S, A, B, and T with C(S,A)=8, C(S,B)=10, C(A,T)=5, C(B,T)=5. Determine the maximum flow and explain why certain paths are chosen.

   Hint

   Think about the paths that maximize capacity usage.