# Minimum Cut MCQ

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

Answer: c

The minimum cut algorithm is solved using the Stoer-Wagner algorithm. The maximum flow problem is solved using the Ford-Fulkerson algorithm. The stable marriage problem is solved using the Gale-Shapley algorithm.

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

Answer: a

The minimum cut is a partition of the vertices in graph 4. in two disjoint subsets joined by one edge. It is a cut that is minimal in some sense.

3. Minimum cut algorithm comes along with the maximum flow problem.

a) true

b) false

Answer: a

The minimum cut algorithm is considered to be an extension of the maximum flow problem. Minimum cut is finding a minimal cut.

4. What does the given figure depict?

a) min-cut problem

b) max cut problem

c) maximum flow problem

d) flow graph

Answer: a

The given figure is a depiction of a min-cut problem since the graph is partitioned to find the minimum cut.

5. ___________ separates a particular pair of vertices in a graph.

a) line

b) arc

c) cut

d) flow

Answer: c

A cut separates a particular pair of vertices in a weighted undirected graph and has minimum possible weight.

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

Answer: c

The mathematical formula for a graph with ‘n’ vertices can at the most have n(n-1)/2 distinct vertices.

7. What is the running time of Karger’s algorithm to find the minimum cut in a graph?

a) O(E)

b) O(|V|^{2})

c) O(V)

d) O(|E|)

Answer: b

The running time of Karger’s algorithm to find the minimum cut is mathematically found to be O(|V|^{2}).

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

Answer: b

Graph partition is a problem in which the graph is partitioned into two or more parts with additional conditions.

9. The weight of the cut is not equal to the maximum flow in a network.

a) true

b) false

Answer: b

According to the max-flow min-cut theorem, the weight of the cut is equal to the maximum flow that is sent from source to sink.

10. __________ is a data structure used to collect a system of cuts for solving the min-cut problems.

a) Gomory-Hu tree

b) Gomory-Hu graph

c) Dancing tree

d) AA tree

Answer: a

The gomory-Hu tree is a weighted tree that contains the minimum cuts for all pairs in a graph. It is constructed in |V|-1 max-flow computations.

11. In how many ways can a Gomory-Hu tree be implemented?

a) 1

b) 2

c) 3

d) 4

Answer: b

Gomory-Hu tree can be implemented in two ways- sequential and parallel.

The Gomory–Hu tree of an undirected graph with capacities is a weighted tree that represents the minimum s-t cuts for all s-t pairs in the graph.

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^{2})

Answer: d

The running time of the min-cut algorithm using naïve implementation is mathematically found to be O(N^{2}).

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^{4})

d) O(N^{2})

Answer: c

The running time of a min-cut algorithm using the Ford-Fulkerson method of making edges birected in a graph is mathematically found to be O(N^{4}).

14. Which one of the following is not an application of the max-flow min-cut algorithm?

a) network reliability

b) closest pair

c) network connectivity

d) bipartite matching

Answer: b

Network reliability, connectivity, and bipartite matching are all applications of the min-cut algorithm whereas the closest pair is a different kind of problem.

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})

Answer: a

The minimum cut of the given graph network is found to be ({1,3},{4,3},{4,5}) and its capacity is 23.