# 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

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

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

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

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

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

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

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

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

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

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

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(N2)

The running time of the min-cut algorithm using naïve implementation is mathematically found to be O(N2).

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(N4)
d) O(N2)

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(N4).

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

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