Network Flow Algorithms: Ford-Fulkerson and Max Flow Quiz Quiz

Explore core concepts of network flow algorithms with these medium-level quiz questions focusing on the Ford-Fulkerson method and max flow problems. Enhance your understanding of flow networks, algorithm steps, and key principles for finding the maximum flow in directed graphs.

1. Identifying Augmenting Paths

   In the Ford-Fulkerson algorithm, what is the primary criterion for selecting an augmenting path in each iteration?

   1. The shortest path from source to sink regardless of edge capacities
   2. The path with the maximum number of edges from source to sink
   3. Any simple path from source to sink where the residual capacity is positive
   4. A path that only uses edges with capacity equal to the current maximum flow

   Explanation: The Ford-Fulkerson method selects any path from the source to sink with available (positive) residual capacity, regardless of the number of edges or total capacity along the path. The second option confuses with the Edmonds-Karp algorithm, which always selects the shortest path. Option three incorrectly prioritizes the number of edges rather than capacity. The last option misunderstands that only positive capacity is needed, not necessarily equal to the current max flow.

2. Residual Networks Explained

   What is the main purpose of maintaining a residual network when solving the max flow problem?

   1. To remove all saturated edges from the graph
   2. To track remaining capacities and allow flow reversal where needed
   3. To assign random weights to edges for balanced flow
   4. To simplify the original graph by merging parallel edges

   Explanation: The residual network shows which edges can still accommodate more flow and also lets the algorithm reverse previously assigned flow if better paths are found. Removing saturated edges does not account for reversals and may miss opportunities to increase overall flow. Merging parallel edges or assigning random weights are irrelevant to the residual network's essential function.

3. Edge Capacity Update Rule

   After pushing flow along an augmenting path in Ford-Fulkerson, how should the capacities be updated in the residual graph?

   1. Only update forward edge capacities, leaving reverse edges unchanged
   2. Multiply forward edge capacities by two and reverse edge capacities by half
   3. Set all edge capacities to zero along the path
   4. Decrease forward edge capacities and increase reverse edge capacities by the amount of flow pushed

   Explanation: Each time flow is pushed through a path, the corresponding forward edges in the residual graph are decreased by that flow, while the reverse edges are increased, allowing for potential backtracking in future iterations. Setting all capacities to zero eliminates subsequent augmentations. Multiplying capacities or only updating forward edges ignores the need for reversible adjustments, undermining algorithm correctness.

4. Termination Condition for Max Flow

   When does the Ford-Fulkerson algorithm terminate, indicating that the maximum possible flow has been found between source and sink?

   1. After completing a fixed number of iterations based on the number of vertices
   2. When no augmenting path with positive residual capacity remains in the residual network
   3. When the total flow equals the sum of all outgoing edge capacities from the sink
   4. After all edges have been traversed exactly once

   Explanation: The algorithm stops once no augmenting path can be found, which means that the maximum flow has been achieved. Equating total flow to outgoing edges from the sink is incorrect; flow is measured at the source. Traversing all edges once or using a fixed number of iterations does not guarantee that the maximum flow has been reached, since paths and capacities can differ.

5. Minimum Cut Connection

   According to the Max-Flow Min-Cut theorem, what does the value of the maximum flow in a network equal?

   1. The sum of all individual edge capacities in the network
   2. The number of paths from the source to the sink
   3. The maximum number of edges in any path from source to sink
   4. The total capacity of the smallest set of edges that, if removed, would disconnect the source from the sink

   Explanation: The Max-Flow Min-Cut theorem states that the value of the maximum flow is equal to the minimum capacity that, if removed, cuts off all connections between the source and sink. The sum of all edge capacities or the number of paths are not related to the actual flow achieved. The number of edges in a single path is also not indicative of the possible flow through the network.