1
$\begingroup$

I am going through Professor Skiena's textbook and he says that there are 3 types of cut-nodes - root, bridge cut node, and parent cut node.

Now if the earliest reachable ancestor from a node is itself, it's parent and the node (if not leaf) become bridge cut nodes.

My question is that we have a simple 2-node undirected graph -> A --- B.

In this case, B's earliest reachable ancestor is B itself and hence A becomes the bridge cut node. However, I am unsure that should be the case; since if I delete A, even then B exists and the num_components = 1?

$\endgroup$
  • $\begingroup$ Could you give a more precise reference to what you're talking about than "[somewhere in] Professr Skiena's textbook"? $\endgroup$ – David Richerby Aug 2 '18 at 10:39
1
$\begingroup$

By definition, a graph that has only one vertex is connected.

That's to say if you delete A, the graph B is still connected. Clearly, A is not a cut-node because it can't disconnect the graph. So is vertex B.

A vertex is a parent/bridge cut-node if and only if it is not root vertex.

The concepts of these three types of cut-node are introduced by Skiena's in his own book, so these concepts are not very rigorous. An errata list may be a good supplement.

$\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.