Minimum Cut Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Minimum Cut”.

1. Which algorithm is used to solve a minimum cut algorithm?
a) Gale-Shapley algorithm
b) Ford-Fulkerson algorithm
c) Stoer-Wagner algorithm
d) Prim’s algorithm
View Answer

2. ___________ is a partition of the vertices of a graph in two disjoint subsets that are joined by atleast one edge.
a) Minimum cut
b) Maximum flow
c) Maximum cut
d) Graph cut
View Answer

3. Minimum cut algorithm comes along with the maximum flow problem.
a) true
b) false
View Answer

4. What does the given figure depict?

a) min cut problem
b) max cut problem
c) maximum flow problem
d) flow graph
View Answer

5. ______________ separates a particular pair of vertices in a graph.
a) line
b) arc
c) cut
d) flow
View Answer

6. What is the minimum number of cuts that a graph with ‘n’ vertices can have?
a) n+1
b) n(n-1)
c) n(n+1)/2
d) n(n-1)/2
View Answer

7. What is the running time of Karger’s algorithm to find the minimum cut in a graph?
a) O(E)
b) O(|V|²)
c) O(V)
d) O(|E|)
View Answer

8. _____________ is a family of combinatorial optimization problems in which a graph is partitioned into two or more parts with constraints.
a) numerical problems
b) graph partition
c) network problems
d) combinatorial problems
View Answer

9. The weight of the cut is not equal to the maximum flow in a network.
a) true
b) false
View Answer

10. __________ is a data structure used to collect a system of cuts for solving min-cut problem.
a) Gomory-Hu tree
b) Gomory-Hu graph
c) Dancing tree
d) AA tree
View Answer

11. In how many ways can a Gomory-Hu tree be implemented?
a) 1
b) 2
c) 3
d) 4
View Answer

12. The running time of implementing naïve solution to min-cut problem is?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N²)
View Answer

13. What is the running time of implementing a min-cut algorithm using bidirected edges in a graph?
a) O(N)
b) O(N log N)
c) O(N⁴)
d) O(N²)
View Answer

14. Which one of the following is not an application of max-flow min-cut algorithm?
a) network reliability
b) closest pair
c) network connectivity
d) bipartite matching
View Answer

15. What is the minimum cut of the following network?

a) ({1,3},{4,3},{4,5})
b) ({1,2},{2,3},{4,5})
c) ({1,0},{4,3},{4,2})
d) ({1,2},{3,2},{4,5})
View Answer

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]