1
$\begingroup$

I have learnt about both articulation points and bridges and I have understood the algorithm used to find the number of bridges in O(n) time which is Tarjan's algorithm. But now, can I simply say that the vertices connecting the bridges are the articulation points with the additional condition that they should have degree>1? I tried drawing several graphs and in all of them, I found this to be true. So is this or is this not true?

$\endgroup$
1
  • $\begingroup$ Give context information, we are not reading above your shoulder. $\endgroup$
    – user16034
    Jul 28, 2022 at 12:32

1 Answer 1

0
$\begingroup$

Yes, an endpoint of a bridge is an articulation point iff it has degree > 1.

Be careful, however. There could be articulation points that are not endpoints of any bridge. For example, the red vertex in the graph below is an articulations point. However, there is no bridge in the graph.

enter image description here

The graph above was drawn by user sorry.

An efficient algorithm that finds all articulation points is presented here on Wikipedia and here on GeeksforGeeks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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