Articulation Edges and Vertexes
(Page 1 of 4 )
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.
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.
Next: Articulation Edges: Code Snippet >>
More Code Examples Articles
More By Gabor Bernat
