Articulation Edges and Vertexes - Articulation Vertexes: Theory
(Page 3 of 4 )
An articulation vertex is similar to the edge. Here we delete a vertex (of course with the edges that are related to it) and see whether or not the number of the connective sub-graphs components increase.
A vertex is an articulation type if, from its child sub-graphs, there exists one from which there is no back-pointing edge to a parent of the vertex. This way, when we cut off the vertex, that specific child sub-graph will be also cut off from the tree and increase the connective sub-graph components of the graph.
The root item of the Depth-First Search is of an articulation vertex type only if it has at least two children, as when we cut off the root, these would fall apart, causing the vertex that holds them together to disappear, and from the root item there can be no back-pointing edges.
-->Image Courtesy of Kátai Zoltán- Introduction to Graphs<--
The example in the upper graph will help you understand it better. Look at vertex number 11. When the DFS arrives at it, the coloring of the graph is just as is drawn on the image (black=finished visited, gray= visit in progress, white=not yet visited).
Now we are going to call the DFS for all of its neighbors that are still white: vertex 12, 13 and 14. From the sub-graph of vertex 12, we got back that there exists a backward-pointing edge to level 4 -- however, this is only a fake back pointing edge, as this will be deleted, along with vertex 11.
In order to have a correct back-pointing edge we need to point it above level 11. The sub-graph of node 14 will satisfy this, however; from the point of view of node 12, the vertex becomes articulated.
We can also tell by how many the delete process will increase the count of the number of connective sub-graphs. This will be the same as the number of child sub-graphs of the vertex we analyze that do not have a back-pointing edge to a parent of the vertex. In the code snippet I am going to present, we will also print this additional information after the vertex.
Next: Articulation Vertexes: Code Snippet >>
More Code Examples Articles
More By Gabor Bernat
