Virtual Labs

Ford - Fulkerson Algorithm

What is the primary role of the 'Residual Graph' in Ford-Fulkerson?

a: To store the final flow values Explanation

Explanation

b: To identify augmenting paths by showing remaining capacities Explanation

Explanation

c: To visualize the physical layout of the nodes Explanation

Explanation

d: To calculate the shortest path between any two nodes Explanation

Explanation

In the residual graph, what does a backward edge (v, u) represent?

a: A mistake in the input graph Explanation

Explanation

b: The ability to 'undo' or reduce flow previously sent from u to v Explanation

Explanation

c: An edge with negative capacity Explanation

Explanation

d: A path that only the sink can use Explanation

Explanation

How is the 'bottleneck' capacity of an augmenting path calculated?

a: Max capacity in the path Explanation

Explanation

b: Average capacity of the path Explanation

Explanation

c: Minimum residual capacity of any edge in the path Explanation

Explanation

d: The capacity of the source node Explanation

Explanation

The Max-Flow Min-Cut Theorem states that:

a: Max flow is always less than min cut Explanation

Explanation

b: Max flow value equals the capacity of the minimum cut Explanation

Explanation

c: Min cut is the sum of all source edges Explanation

Explanation

d: Max flow is equal to the number of edges Explanation

Explanation

Why is BFS preferred over DFS in the Edmonds-Karp version of Ford-Fulkerson?

a: BFS is easier to code Explanation

Explanation

b: BFS ensures the shortest augmenting path is found, guaranteeing polynomial time Explanation

Explanation

c: DFS cannot find the sink Explanation

Explanation

d: BFS uses less memory Explanation

Explanation

When does the Ford-Fulkerson algorithm terminate?

a: After 100 iterations Explanation

Explanation

b: When all edges have maximum flow Explanation

Explanation

c: When no more augmenting paths exist in the residual graph Explanation

Explanation

d: When the source node is deleted Explanation

Explanation

What happens to the residual capacity of a forward edge after flow is pushed through it?

a: The residual capacity increases Explanation

Explanation

b: The residual capacity decreases (less room for additional flow) Explanation

Explanation

c: The capacity of the original graph increases Explanation

Explanation

d: The edge is removed from the graph Explanation

Explanation

A 'Cut' in a flow network is a partition of nodes into two sets, S and T, such that:

a: All edges are in S Explanation

Explanation

b: The source is in S and the sink is in T Explanation

Explanation

c: All nodes are in T Explanation

Explanation

d: S and T are identical Explanation

Explanation

If the Max Flow is 50, and you find a cut with capacity 50, what can you conclude?

a: There is a smaller cut somewhere Explanation

Explanation

b: This is a minimum cut Explanation

Explanation

c: The algorithm has a bug Explanation

Explanation

d: The flow can be increased further Explanation

Explanation

What does pushing 5 units through a backward edge (v, u) in the residual graph mean in terms of the original network?

a: 5 new units of flow are added from v to u in the original network Explanation

Explanation

b: 5 units of previously assigned flow on edge (u, v) are cancelled or rerouted Explanation

Explanation

c: The capacity of edge (v, u) increases by 5 Explanation

Explanation

d: The source stops producing flow Explanation

Explanation