Recall & Review
beginner
What is an articulation point in a graph?
An articulation point is a vertex in a graph which, when removed along with its edges, increases the number of connected components. It is a critical node that disconnects parts of the graph.
Click to reveal answer
intermediate
Which algorithm is commonly used to find articulation points in a graph?
Tarjan's algorithm is commonly used to find articulation points. It uses Depth First Search (DFS) and tracks discovery times and low values of vertices.
Click to reveal answer
intermediate
In Tarjan's algorithm, what does the 'low' value of a vertex represent?
The 'low' value of a vertex is the earliest discovery time reachable from that vertex or its descendants by following DFS tree edges and back edges.
Click to reveal answer
intermediate
Why is the root of the DFS tree treated differently when finding articulation points?
The root is an articulation point only if it has two or more children in the DFS tree. Removing it disconnects the graph if it has multiple subtrees.
Click to reveal answer
beginner
What is the time complexity of finding articulation points using Tarjan's algorithm?
The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because it uses a single DFS traversal.
Click to reveal answer
What happens if you remove an articulation point from a connected graph?
✗ Incorrect
Removing an articulation point increases the number of connected components, making the graph disconnected.
Which data structure is primarily used in Tarjan's algorithm to find articulation points?
✗ Incorrect
Tarjan's algorithm uses DFS recursion to explore the graph and compute discovery and low values.
In Tarjan's algorithm, if a vertex u has a child v such that low[v] >= disc[u], what does it indicate?
✗ Incorrect
If low[v] >= disc[u], it means v or its descendants cannot reach an ancestor of u, so u is an articulation point.
How many children must the root of DFS tree have to be an articulation point?
✗ Incorrect
The root is an articulation point only if it has two or more children in the DFS tree.
What is the initial value assigned to discovery time of each vertex before DFS starts?
✗ Incorrect
Discovery times are initialized to -1 to indicate unvisited vertices before DFS traversal.
Explain how Tarjan's algorithm finds articulation points in a graph using DFS.
Think about how discovery and low values help identify critical vertices.
You got /5 concepts.
Describe why removing an articulation point increases the number of connected components in a graph.
Consider the role of articulation points as bridges in the graph.
You got /4 concepts.