0
$\begingroup$

Say I have a bidirectional graph G and I have the list of articulation points and bridges of this graph. Say, the list of articulation points is ap[] and the list of bridges are bridges[]. Now, if I remove a node which does not belong to the list of ap[], meaning, this node is not an articulation point and deleting this node will not divide the nodes of this graph into different connected components. Now, do I have to update the list of the articulation points ap[]? I mean after deleting the node, is it possible that some more node(s) in the graph will become articulation points? The same question is for the list of bridges. If I remove an edge which is not a bridge in the graph, after deleting it, is it possible that some more existing edge(s) will become bridge?

$\endgroup$
2
  • $\begingroup$ This question is somewhat related; it may be worthwhile to check the sources provided in the answer. $\endgroup$ Jun 21, 2017 at 14:01
  • $\begingroup$ Learned some new things. Thanks! So is it possible the list of articulation points will be invalid after deleting a node? $\endgroup$ Jun 21, 2017 at 14:32

1 Answer 1

1
$\begingroup$

Yes and yes. Look at this graph:

  • $V=\{1,2,3,4\}$
  • $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$

There is neither articulation point nor bridge. But if you delete any node/edge...

$\endgroup$

Your Answer

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

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