Back
0

Network Optimization: Flows, Cuts, and Matching

Description: 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.
Number of Questions: 14
Created by:
Tags: network optimization flows cuts matching algorithms
Start the Quiz
Attempted 0/14 Correct 0 Score 0
‹
›

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

Show answer
Correct Option: C
Explanation:

The residual capacity of an edge is the amount of additional flow that can be sent along the edge without exceeding its capacity.

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

Show answer
Correct Option: D
Explanation:

The Ford-Fulkerson algorithm is a widely used algorithm for finding the maximum flow in a network. It iteratively finds augmenting paths, which are paths from the source to the sink that have positive residual capacity, and pushes flow along these paths until no more augmenting paths can be found.

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

Show answer
Correct Option: A
Explanation:

In a network, the minimum cut and the maximum flow have the same value. This is known as the max-flow min-cut theorem.

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

Show answer
Correct Option: B
Explanation:

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set.

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

Show answer
Correct Option: D
Explanation:

The Hungarian algorithm is a widely used algorithm for finding a maximum matching in a bipartite graph. It iteratively finds augmenting paths, which are paths from an unmatched vertex to an unmatched vertex that alternate between matched and unmatched edges, and pushes flow along these paths until no more augmenting paths can be found.

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

Show answer
Correct Option: D
Explanation:

The residual network is a network that is derived from the original network by subtracting the current flow from the capacity of each edge. It is used to find augmenting paths and to determine the maximum flow in the network.

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

Show answer
Correct Option: A
Explanation:

A valid flow in a network is a flow that satisfies the flow conservation constraint at every vertex, meaning that the total flow entering a vertex is equal to the total flow leaving the vertex.

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

Show answer
Correct Option: A
Explanation:

A cut in a network is a set of edges that, when removed, divides the network into two disjoint sets of vertices. Cuts are used to analyze the flow in a network and to find the minimum cut.

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

Show answer
Correct Option: D
Explanation:

A valid matching in a bipartite graph is a set of edges that connects each vertex in one set to exactly one vertex in the other set.

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

Show answer
Correct Option: C
Explanation:

An augmenting path in a network flow problem is a path from the source to the sink that has positive residual capacity. Augmenting paths are used to increase the flow in the network by pushing flow along these paths.

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

Show answer
Correct Option: A
Explanation:

A valid cut in a network is a set of edges that divides the network into two disjoint sets of vertices.

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

Show answer
Correct Option: A
Explanation:

The source and sink vertices in a network flow problem represent the starting and ending points of the flow, respectively.

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

Show answer
Correct Option: D
Explanation:

A valid matching in a bipartite graph is a set of edges that connects each vertex in one set to exactly one vertex in the other set.

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

Show answer
Correct Option: A
Explanation:

The capacity constraint on each edge in a network flow problem limits the amount of flow that can be sent along the edge.

- Hide questions
ADVERTISEMENT

Find more quizzes from top tags

general knowledge
3615 Quizzes
119858 Questions
 technology
307 Quizzes
36705 Questions
 sports
963 Quizzes
19148 Questions
 history
1187 Quizzes
13475 Questions
 physics
598 Quizzes
13441 Questions
 biology
1160 Quizzes
12174 Questions
 science & technology
551 Quizzes
11015 Questions
 chemistry
490 Quizzes
9892 Questions
 maths
518 Quizzes
9324 Questions
 softskills
0 Quizzes
7131 Questions