This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Cut Vertices”.
1. A vertex in a graph, on the removal of whose increases the number of connected components is called?
a) Articulation point
b) Bridge
c) Edge connectivity
d) Independent set
View Answer
Explanation: In a simple graph G with V vertices and E edges, there exist a vertex on removal of who’s the graph gets disconnected, this vertex is called the articulation point of the graph. Corresponding edges of the vertices are also removed from the graph.
2. Which of the following algorithm can be used for finding articulation points in a graph?
a) Simplex algorithm
b) Aging algorithm
c) Tarjan’s algorithm
d) DSW algorithm
View Answer
Explanation: Tarjan’s algorithm: We can use a simple DFS algorithm and make small changes. Let us consider the first case where we apply the DFS algorithm from a vertex v, which is root and if and only if v has more than one child in the DFS tree, it is said to be the articulation point. In the second case, we apply the DFS algorithm from a vertex v which is not the root. If the current edge (v, e) is such a way that neither e nor its descendants have a back edge to any of the ancestors of v, then vertex v is said to be the articulation point.
3. What will be the cut vertex set of the graph given below?
a) {C, A}
b) {C, F}
c) {A, E}
d) {B, F}
View Answer
Explanation: Removal of a set of vertices from a graph will make a graph disconnected, this is called a cut vertex set of a graph. The edges are also deleted along with the vertices. The removal of the vertex C and F along with their edges will make the graph disconnected. Hence, the cut vertex set of the graph will be {C, F}. The removal of the vertex D and B will also make the graph disconnected.
4. What will be the time complexity of the brute force approach used to find the articulation points in a given graph?
For every vertex V, do: Remove V from the graph See if the graph remains connected If graph is disconnected, add V to the resultant set Add V back to the graph
a) O(V*(V + E))
b) O(V log V)
c) O(V + log V)
d) O(E log V)
View Answer
Explanation: In a graph G with V vertices and E edges, this brute force approach removes all vertices one by one and checks whether the removal of a vertex gives a disconnected graph or not. Hence, if the graph is represented using the adjacency list, then the time complexity of this approach will be O(V*(V + E)).
5. The pendant vertex of the graph can also be an articulation point of the graph.
a) True
b) False
View Answer
Explanation: A vertex with degree one is called a pendant vertex or end vertex. A vertex of which the deletion disconnects the graph is called a cut vertex. The deletion of the end vertex doesn’t lead the graph to be disconnected. Hence, end vertices cannot be cut vertices.
6. A connected graph has a maximum of (n – 2) cut vertices.
a) True
b) False
View Answer
Explanation: Removal of a cut vertex from a graph, may give a disconnected graph. This increases the number of connected components in the graph. The leaves of any tree of order n has at least two vertices that are not cut vertices. Hence, any spanning tree of the graph has a maximum of n – 2 articulation points.
7. In which of the following applications can we use the concept of articulation points?
a) Designing a microprocessor
b) Designing a router
c) Designing a network
d) Designing a building
View Answer
Explanation: The concept of articulation points can be used to design a network, to find vulnerabilities in a network. If there is a point in a network, which divides the whole network into more than two parts, then the failure of this point might lead to vulnerabilities in a network. Hence, they are very useful in designing a reliable network.
8. Which among the following best represents the time complexity to find articulate points in a graph?
a) O(V)
b) O(E)
c) O(V + E)
d) O(V * E)
View Answer
Explanation: To find articulate points in a graph, we use the DFS algorithm with additional arrays. Time required for DFS is O(V+E) when the graph is stored in the adjacency list. Hence, the time complexity to find articulate points is O(V + E).
9. A biconnected graph contains how many cut vertices?
a) At least one
b) At most one
c) Zero
d) Only one
View Answer
Explanation: There are no cut vertices for a biconnected graph. It is a non-separable graph, if any vertex is removed from the graph, the graph will remain connected. Such types of graphs are called a biconnected graph.
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.
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Data Structure MCQ
- Check Programming Books
- Practice Computer Science MCQs
