Home › Quizzes › Network Optimization: Flows, Cuts, and Matching

Network Optimization: Flows, Cuts, and Matching

This quiz covers the fundamental concepts of network optimization, including flows, cuts, and matching. Test your understanding of these topics and their applications in various domains.

14 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

In a network flow problem, what does the residual capacity of an edge represent?

  1. The maximum amount of flow that can be sent along the edge
  2. The minimum amount of flow that must be sent along the edge
  3. The difference between the edge's capacity and the current flow along the edge
  4. The edge's capacity minus the maximum flow that can be sent along the edge
Question 2 Multiple Choice (Single Answer)

Which algorithm is commonly used to find the maximum flow in a network?

  1. Dijkstra's algorithm
  2. Prim's algorithm
  3. Kruskal's algorithm
  4. Ford-Fulkerson algorithm
Question 3 Multiple Choice (Single Answer)

What is the relationship between a minimum cut and a maximum flow in a network?

  1. The minimum cut is equal to the maximum flow
  2. The minimum cut is always less than or equal to the maximum flow
  3. The minimum cut is always greater than or equal to the maximum flow
  4. There is no relationship between the minimum cut and the maximum flow
Question 4 Multiple Choice (Single Answer)

A bipartite graph is a graph in which:

  1. Every vertex is connected to every other vertex
  2. The vertices can be partitioned into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set
  3. The graph has no cycles
  4. The graph is connected
Question 5 Multiple Choice (Single Answer)

Which algorithm is commonly used to find a maximum matching in a bipartite graph?

  1. Dijkstra's algorithm
  2. Prim's algorithm
  3. Kruskal's algorithm
  4. Hungarian algorithm
Question 6 Multiple Choice (Single Answer)

In a network flow problem, what is the purpose of a residual network?

  1. To represent the current flow in the network
  2. To represent the maximum flow in the network
  3. To represent the minimum cut in the network
  4. To represent the residual capacity of each edge in the network
Question 7 Multiple Choice (Single Answer)

Which of the following is a valid flow in a network?

  1. A flow that satisfies the flow conservation constraint at every vertex
  2. A flow that satisfies the capacity constraint on every edge
  3. A flow that maximizes the total flow in the network
  4. A flow that minimizes the total cost of the flow
Question 8 Multiple Choice (Single Answer)

In a network flow problem, what is the purpose of a cut?

  1. To divide the network into two disjoint sets of vertices
  2. To identify the minimum cut in the network
  3. To find the maximum flow in the network
  4. To determine the residual capacity of each edge in the network
Question 9 Multiple Choice (Single Answer)

Which of the following is a valid matching in a bipartite graph?

  1. A set of edges that connects each vertex in one set to a unique vertex in the other set
  2. A set of edges that connects each vertex in one set to at least one vertex in the other set
  3. A set of edges that connects each vertex in one set to at most one vertex in the other set
  4. A set of edges that connects each vertex in one set to exactly one vertex in the other set
Question 10 Multiple Choice (Single Answer)

In a network flow problem, what is the purpose of an augmenting path?

  1. To find the minimum cut in the network
  2. To find the maximum flow in the network
  3. To increase the flow in the network
  4. To decrease the flow in the network
Question 11 Multiple Choice (Single Answer)

Which of the following is a valid cut in a network?

  1. A set of edges that divides the network into two disjoint sets of vertices
  2. A set of edges that connects each vertex in one set to a unique vertex in the other set
  3. A set of edges that connects each vertex in one set to at least one vertex in the other set
  4. A set of edges that connects each vertex in one set to at most one vertex in the other set
Question 12 Multiple Choice (Single Answer)

In a network flow problem, what is the purpose of the source and sink vertices?

  1. To represent the starting and ending points of the flow
  2. To represent the maximum and minimum flow in the network
  3. To represent the residual capacity of each edge in the network
  4. To represent the flow conservation constraint at every vertex
Question 13 Multiple Choice (Single Answer)

Which of the following is a valid matching in a bipartite graph?

  1. A set of edges that connects each vertex in one set to a unique vertex in the other set
  2. A set of edges that connects each vertex in one set to at least one vertex in the other set
  3. A set of edges that connects each vertex in one set to at most one vertex in the other set
  4. A set of edges that connects each vertex in one set to exactly one vertex in the other set
Question 14 Multiple Choice (Single Answer)

In a network flow problem, what is the purpose of the capacity constraint on each edge?

  1. To limit the amount of flow that can be sent along the edge
  2. To ensure that the flow conservation constraint is satisfied at every vertex
  3. To find the maximum flow in the network
  4. To determine the residual capacity of each edge in the network
← Back to Quizzes