In the lives of each of us there exist some key moments that uniquely define us and become symbolic. These are the critical points; without these, all that we know now would drastically change. Articulation edges and vertexes are something like this to graphs; however, finding them is a lot more complicated than it may seem at first.
Contributed by Gabor Bernat Rating: / 1 May 21, 2009
This is the sixth part of the article series I am dedicating to graph techniques, so if you missed any of the earlier ones I invite you to search for them on this site and read them as well. For this article, it is critical that you understand the Depth First Search algorithm, as the solution heavily relies on it; in fact, it is a prime example of how, by changing the DFS and accommodating it to our needs, we can resolve complex problems.
Any edge which, if we delete it, will increase the connective components count inside the graph, is an articulation edge. We define this as graphs that have edges with no direction.
To translate this to a little more practical problem, let's assume a war. If we represent the road system with a graph, these roads will be the strategically points whose removal will allow us to divide the enemy. To find the solution, let us first define what can be an articulation edge.
An edge from vertex u to node v is an articulation edge only if it is part of the tree edge formed during the DFS (recall the classification of the edges from the previous articles), and from the sub-tree of the v there are no edges that point back to a parent of the vertex u.
A back-pointing edge would place the edge on a circle, and if we delete any edge from a circle, we can still travel from any edge to any other edge, so the first part is obvious. Here you should also know that in a graph with no directed edges, there will not be any forward-pointing or cross-pointing edges.
Moreover, if we have an edge pointing back in the sub-tree of v to a parent of the u, that would place the edge on a circle, and so double the u -v edge connection. This would lose the articulation edge property, because by deleting it we could use the back-pointing edge to travel to any of the nodes of the parents of u.
The earliest point at which we may have this information in our grasp is when we come back from the neighbor edges in a DFS, and we are setting the color of the vertex to black. We will transform the DFS from method to function, and a DFS call to a vertex. Each will return the highest level where there exists a back-pointing edge in the sub-tree.
For an easier determination of the level, we will add an additional parameter to the DFS function, one that will show our current level. If there are no back-pointing edges, the function will send back infinity (limited in our code to INT_MAX).
When we dropped by all of neighbors of a vertex, the level of the sub-tree's minimal back-pointing edge will be the lowest from the ones returned by the children of u. If this is infinity, the u-v edge is an articulation edge, as v-u will not be a back-pointing edge, because it already is part of the tree.
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.
We made it to the end of this article. The source file you may download from the above link contains everything we did during our last three articles, including how the Depth First Search works and how we may use the additional information generated during the search. We also saw how, by refining the search a little and making minimal modifications, we turned it into a complex problem-solving technique.
I am honored to catch your attention for the time you read this article, and I would like to remind you of the rating possibilities you have by simply giving a mark to the article or expressing your thoughts in the blog dedicated to this article. Eventually you may also join the DevHardware forum and act in the same manner there. During the next article, the subject will be spanning trees with minimal cost. Until next time Live With Passion!
Code Examples 
Circles and Connectivity in Graphs
