example 16
We will trace the articulation point algorithm on the graph of Figure 7.20a, where
a is the starting node. The tree begins with arcs a–b, b–d, and d–c. Each new node
is numbered with a consecutive tree number, and its back number is set equal to
its tree number (Figure 7.24a; in the figure, the numbers in parentheses are the tree
number and the back number, respectively). While processing node c, the back
edge to a is discovered, and the back number of c is adjusted to 1, the tree number
of a (line 3 in the algorithm description). This action completes the processing of
node c, and the depth-first search backs up to d. The back number of c is less than
the tree number of d, so the back number of d is adjusted to equal that of c (line 2).
The situation at this point is shown in Figure 7.24b.
The depth-first search moves on to nodes e, g, and f (Figure 7.24c). At f the
back arc to d is found, and the back number of f is set equal to the tree number of d
(line 3). Backing up from f to g, the back number of g is adjusted to equal the back
number of f (line 2) and similarly for e (line 2 again). (See Figure 7.24d.)
a (1, 1)
g
g
g (6, 6)
g (6, 3)
g (6, 3)
b (2, 2)
c (4, 4)
e
d (3, 3)
a (1, 1)
b (2, 2)
c (4, 1)
d (3, 1)
a (1, 1)
(a)
(b)
(d)
(e)
(c)
b (2, 2)
c (4, 1)
d (3, 1)
f
e
f
e (5, 5)
f (7, 7)
e (5, 3)
f (7, 3)
e (5, 3)
d = articulation point
f (7, 3)
a (1, 1)
b (2, 2)
c (4, 1)
d (3, 1)
a (1, 1)
b (2, 1)
c (4, 1)
d (3, 1)
Figure 7.24
Finally, in backing up from e to d, the back number of e is greater than or equal
to the tree number of d, so d is declared an articulation point (line 1). The recursion backs up to node b, adjusting the back number of b, and then node a,
at which point line 1 would seem to apply (Figure 7.24e). But a is the starting
node of the search and so is not an articulation point, because there is only one
tree arc from a.
Section 7.5 Articulation Points and Computer Networks
611
We will trace the articulation point algorithm on the graph of Figure 7.20a, where
a is the starting node. The tree begins with arcs a–b, b–d, and d–c. Each new node
is numbered with a consecutive tree number, and its back number is set equal to
its tree number (Figure 7.24a; in the figure, the numbers in parentheses are the tree
number and the back number, respectively). While processing node c, the back
edge to a is discovered, and the back number of c is adjusted to 1, the tree number
of a (line 3 in the algorithm description). This action completes the processing of
node c, and the depth-first search backs up to d. The back number of c is less than
the tree number of d, so the back number of d is adjusted to equal that of c (line 2).
The situation at this point is shown in Figure 7.24b.
The depth-first search moves on to nodes e, g, and f (Figure 7.24c). At f the
back arc to d is found, and the back number of f is set equal to the tree number of d
(line 3). Backing up from f to g, the back number of g is adjusted to equal the back
number of f (line 2) and similarly for e (line 2 again). (See Figure 7.24d.)
a (1, 1)
g
g
g (6, 6)
g (6, 3)
g (6, 3)
b (2, 2)
c (4, 4)
e
d (3, 3)
a (1, 1)
b (2, 2)
c (4, 1)
d (3, 1)
a (1, 1)
(a)
(b)
(d)
(e)
(c)
b (2, 2)
c (4, 1)
d (3, 1)
f
e
f
e (5, 5)
f (7, 7)
e (5, 3)
f (7, 3)
e (5, 3)
d = articulation point
f (7, 3)
a (1, 1)
b (2, 2)
c (4, 1)
d (3, 1)
a (1, 1)
b (2, 1)
c (4, 1)
d (3, 1)
Figure 7.24
Finally, in backing up from e to d, the back number of e is greater than or equal
to the tree number of d, so d is declared an articulation point (line 1). The recursion backs up to node b, adjusting the back number of b, and then node a,
at which point line 1 would seem to apply (Figure 7.24e). But a is the starting
node of the search and so is not an articulation point, because there is only one
tree arc from a.
Section 7.5 Articulation Points and Computer Networks
611