614
Graph Algorithms
c H a p t e R 7 revieW
teRminology
adjacency relation (p. 555)
articulation point(p. 607)
back arc (p. 608)
biconnected component(p. 608)
biconnected graph(p. 607)
breadth-first search (p. 598)
connected component (p. 603)
depth-first search (p. 596)
dequeue (p. 599)
enqueue (p. 599)
Euler path (p. 572)
even node (p. 572)
graph traversal (p. 596)
greedy algorithm (p. 586)
Hamiltonian circuit (p. 576)
minimal spanning tree (p. 587)
odd node (p. 572)
queue (p. 599)
reachable node (p. 557)
reachability matrix (p. 559)
spanning tree (p. 587)
tree arc (p. 608)
Self-teSt
Answer the following true–false questions.
section 7.1
1. Any binary relation on a set N has an associated
adjacency matrix.
2. Transitive closure is the adjacency relation equivalent of reachability.
3. The reachability matrix r for a directed graph G
is computed by taking the powers of the adjacency
matrix up to n
2
.
4. Warshall’s algorithm proceeds by computing, in
turn, the number of paths of length 1, then length 2,
and so on, between nodes.
5. Warshall’s algorithm computes symmetric closure
in the case of a symmetric adjacency relation.
section 7.2
1. A graph with four odd nodes can still be a connected
graph.
2. An Euler path exists in any graph with an even
number of odd nodes.
3. An Θ(n
2
) algorithm exists to test the existence of
an Euler path in a graph with n nodes.
4. A Hamiltonian circuit uses each arc and node of the
graph exactly once except for the starting and ending node.
5. No algorithm to solve the Hamiltonian circuit
problem is known.
section 7.3
1. Dijkstra’s algorithm for the shortest path in a graph
maintains a set IN and adds at each step the node
closest to a node in IN.
2. A greedy algorithm is one that recursively divides
the problem into as many subproblems as possible.
3. The minimal spanning tree for a graph may not be
unique.
4. Using a linked-list representation for nodes not in
IN does not improve the order of magnitude of the
worst-case work done by Dijkstra’s algorithm.
5. The collection of all arcs that are not in a minimal
spanning tree for a graph will also form a spanning
tree, but it may not be minimal.
section 7.4
1. The depth-first search visits nodes at the bottom of
the graph first.
2. In a breadth-first search beginning with node i, all
the nodes adjacent to i are visited in order.
3. An analysis of the depth-first search and the
breadth-first search shows them to be algorithms of
the same order of magnitude.
4. Preorder traversal is the tree equivalent of the
breadth-first search, using the root as the starting node.
5. Topological sorting can be done by a succession of
breadth-first searches on a directed graph.
section 7.5
1. If node n is an articulation point in a connected
graph, then any path between any two nodes in the
graph must pass through n.
2. A biconnected graph is a simple, connected graph
with no articulation points.
3. When a node n is first reached during a depth-first
search, any other arcs from n to previously visited
nodes are back arcs.
4. A node n where every subtree of n in the depth-first
search tree has a back arc to a predecessor of n is
not an articulation point.
5. The root of a depth-first search is always an articulation point in the graph because any node’s back number will be greater than or equal to its tree number.
Graph Algorithms
c H a p t e R 7 revieW
teRminology
adjacency relation (p. 555)
articulation point(p. 607)
back arc (p. 608)
biconnected component(p. 608)
biconnected graph(p. 607)
breadth-first search (p. 598)
connected component (p. 603)
depth-first search (p. 596)
dequeue (p. 599)
enqueue (p. 599)
Euler path (p. 572)
even node (p. 572)
graph traversal (p. 596)
greedy algorithm (p. 586)
Hamiltonian circuit (p. 576)
minimal spanning tree (p. 587)
odd node (p. 572)
queue (p. 599)
reachable node (p. 557)
reachability matrix (p. 559)
spanning tree (p. 587)
tree arc (p. 608)
Self-teSt
Answer the following true–false questions.
section 7.1
1. Any binary relation on a set N has an associated
adjacency matrix.
2. Transitive closure is the adjacency relation equivalent of reachability.
3. The reachability matrix r for a directed graph G
is computed by taking the powers of the adjacency
matrix up to n
2
.
4. Warshall’s algorithm proceeds by computing, in
turn, the number of paths of length 1, then length 2,
and so on, between nodes.
5. Warshall’s algorithm computes symmetric closure
in the case of a symmetric adjacency relation.
section 7.2
1. A graph with four odd nodes can still be a connected
graph.
2. An Euler path exists in any graph with an even
number of odd nodes.
3. An Θ(n
2
) algorithm exists to test the existence of
an Euler path in a graph with n nodes.
4. A Hamiltonian circuit uses each arc and node of the
graph exactly once except for the starting and ending node.
5. No algorithm to solve the Hamiltonian circuit
problem is known.
section 7.3
1. Dijkstra’s algorithm for the shortest path in a graph
maintains a set IN and adds at each step the node
closest to a node in IN.
2. A greedy algorithm is one that recursively divides
the problem into as many subproblems as possible.
3. The minimal spanning tree for a graph may not be
unique.
4. Using a linked-list representation for nodes not in
IN does not improve the order of magnitude of the
worst-case work done by Dijkstra’s algorithm.
5. The collection of all arcs that are not in a minimal
spanning tree for a graph will also form a spanning
tree, but it may not be minimal.
section 7.4
1. The depth-first search visits nodes at the bottom of
the graph first.
2. In a breadth-first search beginning with node i, all
the nodes adjacent to i are visited in order.
3. An analysis of the depth-first search and the
breadth-first search shows them to be algorithms of
the same order of magnitude.
4. Preorder traversal is the tree equivalent of the
breadth-first search, using the root as the starting node.
5. Topological sorting can be done by a succession of
breadth-first searches on a directed graph.
section 7.5
1. If node n is an articulation point in a connected
graph, then any path between any two nodes in the
graph must pass through n.
2. A biconnected graph is a simple, connected graph
with no articulation points.
3. When a node n is first reached during a depth-first
search, any other arcs from n to previously visited
nodes are back arcs.
4. A node n where every subtree of n in the depth-first
search tree has a back arc to a predecessor of n is
not an articulation point.
5. The root of a depth-first search is always an articulation point in the graph because any node’s back number will be greater than or equal to its tree number.