WOA7001 Lecture 9: Network Flow

What is a flow network?

• A network where flow is allowed to exceed capacity.

• A directed graph with capacities assigned to edges.

• An undirected graph with capacity constraints.

• A graph where all edges have the same capacity.

In a flow network, which nodes are EXCEPTIONS to the flow conservation property?

• All intermediate nodes

• Source and sink nodes

• All nodes

• Only sink nodes

What is the purpose of a residual graph in the context of the Ford-Fulkerson algorithm?

• To represent the remaining capacities in the network.

• To calculate the minimum cut directly.

• To check if flow conservation is satisfied.

• To identify cycles in the network.

What is the complexity of the Ford-Fulkerson algorithm if augmenting paths are found using Depth-First Search (DFS)?

•  O(V + E) 

•  O(E²) 

•  O(E x Max Flow) 

•  O(V²) 

In a residual graph, what is an augmenting path?

• A path from sink to source with positive residual capacities.

• An edge with zero capacity.

• A path from source to sink with positive residual capacities.

• A path from source to sink with negative capacity constraints.

What happens when there are no more augmenting paths in a residual graph?

• The flow is not optimal.

• The maximum flow has been achieved.

• The network is disconnected.

• Flow conservation is violated.

What does the Max-Flow Min-Cut Theorem state?

• The maximum flow in a network is always less than the minimum cut.

• The maximum flow in a network equals the capacity of the minimum cut.

• The minimum cut in a network is unrelated to the maximum flow.

• The maximum flow in a network equals the sum of all edge capacities.

In the Max-Flow Min-Cut Theorem, what is a cut in the flow network?

• A path that connects the source to the sink.

• A partition of the graph into two disjoint sets separating the source and sink.

• A set that includes the source and sink.

• A single edge with the maximum capacity.

What happens to the flow in a network when the minimum cut is found?

• The flow can be further augmented.

• The flow becomes equal to the sum of all edge capacities.

• The flow conservation property is violated.

• The flow is equal to the total capacity of the minimum cut.

Which of the following is true about the minimum cut in a flow network?

• The minimum total capacity of edges crossing from the source set to the sink set.

• The maximimum number of capacity crossing the cut.

• It always includes the edge with the smallest capacity.

• It minimizes the flow from the source to the sink.