An articulation point in a connected graph is a vertex such that removing the…
GATE · 2021 · CS · Set 1 · Computer Science & IT
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?
- A.
Root of T can never be an articulation point in G.
- B.
Root of T is an articulation point in G if and only if it has 2 or more children.
- C.
A leaf of T can be an articulation point in G.
- D.
If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
Attempted by 202 students.
Sign up free to check your answer
Sign up freeLoading lesson…