608
Graph Algorithms
The presence of articulation points is clearly an undesirable feature of a network. Although it is easy to spot an articulation point in a graph as small as that
of Figure 7.20a, we will develop an algorithm that will detect such points no matter how large the graph (and, of course, does not require a visual representation
of the graph). Articulation points separate the graph into biconnected components, subgraphs that are biconnected and are not subgraphs of larger biconnected
subgraphs. In Figure 7.20, a–b–d–c and d–e–g–f are biconnected components.
the idea behind the Algorithm
The key to this algorithm is depth-first search. We know from the previous section
that a depth-first search determines a nonrooted tree. An arc is added to the tree
whenever the search progresses to a previously unvisited node. Arcs of the graph
belonging to this tree are called tree arcs. The remaining arcs in the graph are
called back arcs.
example 15
In Figure 7.20 a depth-first search from node a visits nodes in the order a, b, d, c,
e, g, and f. In Figure 7.21 the tree arcs are dark, and the back arcs are light.
a
g
b
c
e
d
f
Figure 7.21
The depth-first search tree passes through all nodes. To detect nodes that are
articulation points, we examine their relative positions in the tree. First consider
the single node that is the starting point of the depth-first search tree. If only one
tree arc emanates from the starting node, then as the tree continues, all other
nodes in the graph can be reached from the node at the other end of that tree arc.
Therefore, removing the starting node will not disconnect the graph. However, if
two or more tree arcs emanate from the starting node, then the only way to get
from one subtree to another is to pass back through the starting node. In this case,
removing the starting node disconnects the graph.
Thus in Figure 7.21 node a is the starting node of the depth-first search tree,
and there is a single tree arc emanating from a. Removing node a (and its two arcs)
does not disconnect the graph. Had we begun a depth-first search at node d, however, the tree would have looked like Figure 7.22. There would be two tree arcs
coming from node d, showing that d is an articulation point.
Graph Algorithms
The presence of articulation points is clearly an undesirable feature of a network. Although it is easy to spot an articulation point in a graph as small as that
of Figure 7.20a, we will develop an algorithm that will detect such points no matter how large the graph (and, of course, does not require a visual representation
of the graph). Articulation points separate the graph into biconnected components, subgraphs that are biconnected and are not subgraphs of larger biconnected
subgraphs. In Figure 7.20, a–b–d–c and d–e–g–f are biconnected components.
the idea behind the Algorithm
The key to this algorithm is depth-first search. We know from the previous section
that a depth-first search determines a nonrooted tree. An arc is added to the tree
whenever the search progresses to a previously unvisited node. Arcs of the graph
belonging to this tree are called tree arcs. The remaining arcs in the graph are
called back arcs.
example 15
In Figure 7.20 a depth-first search from node a visits nodes in the order a, b, d, c,
e, g, and f. In Figure 7.21 the tree arcs are dark, and the back arcs are light.
a
g
b
c
e
d
f
Figure 7.21
The depth-first search tree passes through all nodes. To detect nodes that are
articulation points, we examine their relative positions in the tree. First consider
the single node that is the starting point of the depth-first search tree. If only one
tree arc emanates from the starting node, then as the tree continues, all other
nodes in the graph can be reached from the node at the other end of that tree arc.
Therefore, removing the starting node will not disconnect the graph. However, if
two or more tree arcs emanate from the starting node, then the only way to get
from one subtree to another is to pass back through the starting node. In this case,
removing the starting node disconnects the graph.
Thus in Figure 7.21 node a is the starting node of the depth-first search tree,
and there is a single tree arc emanating from a. Removing node a (and its two arcs)
does not disconnect the graph. Had we begun a depth-first search at node d, however, the tree would have looked like Figure 7.22. There would be two tree arcs
coming from node d, showing that d is an articulation point.