a
g
b
c
e
d
f
Figure 7.22
Consider any node n that is a leaf of the depth-first search tree (attached to the
end of a single tree arc). Such a leaf may be a leaf of the graph itself, that is, a node
of degree 1, in which case it is clearly not an articulation point. If not, then the
other arcs emanating from n were not used in the depth-first search, so the nodes
adjacent to n are reachable through alternative paths that do not go through n.
Because n is not needed on a path to any other node, its removal does not disconnect the graph. Therefore no leaves of the depth-first search tree are articulation
points. In Figure 7.21 node c, for example, is a leaf of the depth-first search tree;
the arc from c to a is a back arc, so node a is accessible through another route that
does not require node c. Node c can be removed without disconnecting the graph.
Now consider a node n that is not a leaf in the depth-first search tree and is
not the starting node. Because n is not a leaf, there are one or more subtrees below
n. Suppose there is a single subtree; let x be a node on this subtree. If x has a back
arc to some node that precedes n in the depth-first search (an “ancestor” of n), then
this arc provides part of an alternative path for x—and all other nodes in the subtree—to be connected with the rest of the graph without using node n. In this case
n is not an articulation point. (See Figure 7.23a, where removing n and its attached
arcs does not disconnect the graph.) If there is more than one subtree below n, then
n will not be an articulation point if and only if each subtree has such an “escape
route” allowing it to connect with the rest of the graph—including the other subtrees—without going through n. (See Figure 6.23b; note that the back arc from y
to z does not help because it does not reach back to an ancestor of n.)
n
x
r
n
z
y
x
r
Escape route
Escape route
Escape route
(a)
(b)
Figure 7.23
Section 7.5 Articulation Points and Computer Networks
609
g
b
c
e
d
f
Figure 7.22
Consider any node n that is a leaf of the depth-first search tree (attached to the
end of a single tree arc). Such a leaf may be a leaf of the graph itself, that is, a node
of degree 1, in which case it is clearly not an articulation point. If not, then the
other arcs emanating from n were not used in the depth-first search, so the nodes
adjacent to n are reachable through alternative paths that do not go through n.
Because n is not needed on a path to any other node, its removal does not disconnect the graph. Therefore no leaves of the depth-first search tree are articulation
points. In Figure 7.21 node c, for example, is a leaf of the depth-first search tree;
the arc from c to a is a back arc, so node a is accessible through another route that
does not require node c. Node c can be removed without disconnecting the graph.
Now consider a node n that is not a leaf in the depth-first search tree and is
not the starting node. Because n is not a leaf, there are one or more subtrees below
n. Suppose there is a single subtree; let x be a node on this subtree. If x has a back
arc to some node that precedes n in the depth-first search (an “ancestor” of n), then
this arc provides part of an alternative path for x—and all other nodes in the subtree—to be connected with the rest of the graph without using node n. In this case
n is not an articulation point. (See Figure 7.23a, where removing n and its attached
arcs does not disconnect the graph.) If there is more than one subtree below n, then
n will not be an articulation point if and only if each subtree has such an “escape
route” allowing it to connect with the rest of the graph—including the other subtrees—without going through n. (See Figure 6.23b; note that the back arc from y
to z does not help because it does not reach back to an ancestor of n.)
n
x
r
n
z
y
x
r
Escape route
Escape route
Escape route
(a)
(b)
Figure 7.23
Section 7.5 Articulation Points and Computer Networks
609