10.6. Residual Graph

Try these first

1. 1.

   What is a residual graph?

   Hint

   Think about what happens to capacities after some flow has been sent.

2. 2.

   What principle governs flow at intermediate nodes?

   Hint

   Consider nodes as junctions where flow enters and exits.

3. 3.

   What does a residual graph in network flow represent?

   • Available edges for flow
   • Time complexity of the flow calculation
   • Remaining capacities and reverse paths

   Hint

   Think about capacity adjustments.

4. 4.

   True or False: The flow into an intermediate node can be greater than the flow out.

   • True
   • False

   Hint

   Refer to the flow conservation principle.

5. 5.

   Consider a directed graph with nodes A, B, C, and D. The following edges exist: A to B (capacity 5), A to C (capacity 10), B to C (capacity 15), and C to D (capacity 10). Define the residual graph after a flow of 8 from A to D. Calculate remaining capacities for each edge.

   Hint

   Make sure to visualize the flow and adjustments.

6. 6.

   Using a real-world scenario of a delivery service with specified routes and capacities, design a model that applies the Ford-Fulkerson algorithm to identify the best path with maximum flow from supply to delivery point. Demonstrate how you would adjust the residual graph after each iteration.

   Hint

   Focus on creating a visual representation of how capacities change.