1
$\begingroup$

I am trying to find the articulation points in a connected undirected graph and I'm finding it difficult to figure out if the root node of the DFS is an articulation point.
Based on the literature I've read the root node is considered an articulation point if it has more than one child link1

My question is around the graph (0 - 1) (0 - 2) (1 - 2) (1 - 3) (2 - 4) (2 - 5)

When we the DFS rooted at 0 should 0 be considered an articulation point? it does have more than one child, however, the children are connected so removing 0 does not increase the number of connected component (doesn't cut the graph)

I would appreciate if someone can shed some light on this for me.

|cite|improve this question
$\endgroup$
1
$\begingroup$

In the example above running DFS rooted at 0 the vector 0 will only have one tree link as the algorithm will follow the route: 0 -> 1 -> 2 -> 0 Since the edge 0-2 is considered a back link and not a tree link 0 is not considered an articulation point.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This is correct. I think you see now that it does not matter how many neighbors the root has in the graph; what matters is how many of them are children in the DFS tree. $\endgroup$ – Vincenzo Mar 19 '19 at 14:43
0
$\begingroup$

By definition, a vertex is an articulation point if its removal increases the number of connected components. Thus, in general, the root node of a DFS is not necessarily an articulation point.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.