36. a. Describe the order in which nodes are visited in a breadth-first search of the bipartite complete graph K m,n .
b. Describe the order in which nodes are visited in a depth-first search of the bipartite complete graph K m,n .
S e c t i o n 7 . 5 artiCul ation points anD Computer net Works
the Problem statement
In a graph that represents a computer network, the nodes denote the communicating entities (end-user computers, servers, routers, and so on) and the arcs denote
the communications medium (coaxial cable, fiber optic, and so on). Such a graph
should be a connected graph, so that there is a path between every pair of nodes.
To minimize the length of cable or wire required, we would choose a minimum
spanning tree. However, if an arc in a minimum spanning tree is removed (for
example, that section of cable or wire is damaged or broken), then the graph is no
longer connected. Each arc becomes a single point of failure for the network. That
is why such a network usually contains more arcs than just those of a minimal
spanning tree. However, even in a graph sufficiently rich in arcs to withstand the
loss of a single arc, a node may be a single point of failure. If the node fails (and
thus is logically removed), the arcs of which that node is an endpoint are disabled
and the result may be a disconnected graph.
Definition ARticulAtioN PoiNt
A node in a simple, connected graph is an articulation point if its removal
(along with its attached arcs) causes the remaining graph to be disconnected.
example 14
Node d in the graph of Figure 7.20a is an articulation point. Removing d results in
the disconnected graph of Figure 7.20b.
a
a
g
g
b
c b
c
e
d
f
e
f
(a)
(b)
Figure 7.20
Definition BicoNNecteD GRAPh
A simple, connected graph is biconnected if it has no articulation points.
Section 7.5 Articulation Points and Computer Networks
607
b. Describe the order in which nodes are visited in a depth-first search of the bipartite complete graph K m,n .
S e c t i o n 7 . 5 artiCul ation points anD Computer net Works
the Problem statement
In a graph that represents a computer network, the nodes denote the communicating entities (end-user computers, servers, routers, and so on) and the arcs denote
the communications medium (coaxial cable, fiber optic, and so on). Such a graph
should be a connected graph, so that there is a path between every pair of nodes.
To minimize the length of cable or wire required, we would choose a minimum
spanning tree. However, if an arc in a minimum spanning tree is removed (for
example, that section of cable or wire is damaged or broken), then the graph is no
longer connected. Each arc becomes a single point of failure for the network. That
is why such a network usually contains more arcs than just those of a minimal
spanning tree. However, even in a graph sufficiently rich in arcs to withstand the
loss of a single arc, a node may be a single point of failure. If the node fails (and
thus is logically removed), the arcs of which that node is an endpoint are disabled
and the result may be a disconnected graph.
Definition ARticulAtioN PoiNt
A node in a simple, connected graph is an articulation point if its removal
(along with its attached arcs) causes the remaining graph to be disconnected.
example 14
Node d in the graph of Figure 7.20a is an articulation point. Removing d results in
the disconnected graph of Figure 7.20b.
a
a
g
g
b
c b
c
e
d
f
e
f
(a)
(b)
Figure 7.20
Definition BicoNNecteD GRAPh
A simple, connected graph is biconnected if it has no articulation points.
Section 7.5 Articulation Points and Computer Networks
607