612
Graph Algorithms
S e c t i o n 7 . 5 revieW
tecHniQue
• Find articulation points in a simple, connected
graph (using algorithm ArtPoint)
main iDea
• Articulation points represent single points of failure in a computer network, but an algorithm exists
to detect their presence.
praCtiCe 18 In Figure 7.25, the depth-first search began at node a. Explain why each node is marked as
it is and how it is concluded that c is an articulation point.
c = articulation point
b (2, 1)
a (1, 1)
c (3, 1)
d (4, 4)
Figure 7.25
W
exeRciSeS 7.5
For Exercises 1–6, draw the depth-first search trees, where node a is the starting node of the depth-first search.
Identify the back arcs.
1.
b
a
c
e
d
2.
g
a
c
h
b
e
f
i
d
3.
b
a
c
d
g
e
f
h
4.
e
a
g
f
c
b
5.
d
a
b
g
f
e
c
h
6.
d
a
b
g
e
f
c
h
■