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?
1
-
$\begingroup$ Give context information, we are not reading above your shoulder. $\endgroup$– user16034Jul 28, 2022 at 12:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
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.
