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$
  • $\begingroup$ This question is somewhat related; it may be worthwhile to check the sources provided in the answer. $\endgroup$ – AProgrammer Jun 21 '17 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$ – Redwanul Sourav Jun 21 '17 at 14:32
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, privacy policy and cookie policy

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