Java Reference
In-Depth Information
13.
Revise the unweighted, directed graph in Figure 28-15a by adding a directed edge from
D
to
H
. The resulting
graph has two paths from
A
to
H
that are shortest among all paths between these two vertices. Which of these two
paths will the algorithm
getShortestPath
in Segment 28.19 find?
14.
Repeat the previous exercise, but remove the directed edge from
E
to
H
instead of adding a directed edge from
D
to
H
.
15.
Revise the weighted, directed graph in Figure 28-18a by adding a directed edge from
D
to
H
. Let the weight of
this new edge be 3. The resulting graph has two paths from
A
to
H
that are cheapest among all paths between these
two vertices. Which of these two paths will the algorithm
getCheapestPath
in Segment 28.24 find?
16.
Find a map of the routes of a major U. S. airline. Such maps are usually printed at the back of in-flight magazines.
You could also search the Internet for one. The map is a graph like the one in Figure 28-6. Consider the following
pairs of cities:
Providence (RI) and San Diego (CA)
Albany (NY) and Phoenix (AZ)
Boston (MA) and Baltimore (MD)
Dallas (TX) and Detroit (MI)
Charlotte (NC) and Chicago (IL)
Portland (ME) and Portland (OR)
a.
Which pairs of cities in this list have edges (nonstop flights) between them?
b.
Which pairs are not connected by any path?
c.
For each of the remaining pairs, find the path with the fewest edges.
17.
Find the trail map of a cross-country ski area. Represent the trail map as an undirected graph, where each intersection
of trails is a vertex, and each section of trail between intersections is an edge. Consider a cross-country skier who
wishes to take the longest tour possible, but does not want to ski on any trail more than once. What is the longest path
that starts and ends at the ski lodge and does not traverse any section of trail more than once? (Intersections may be
passed through more than once, and some sections of trail may be left unskied.)
18.
Find the trail map of a downhill ski area. Represent the trail map as a graph, where each intersection of trails is a
vertex, and each section of trail between intersections is an edge.
a.
Is the graph directed or undirected?
b.
Does the graph have cycles?
c.
Find the longest path possible that begins at the top of the mountain and ends at the ski lodge.
19.
Write statements appropriate for the client of the class
UndirectedGraph
that create the graph in Figure 28-3.
Assume that
UndirectedGraph
implements
GraphInterface
.
20.
Write statements appropriate for the client of the class
DirectedGraph
that create the graph in Figure 28-8.
Assume that
DirectedGraph
implements
GraphInterface
. Then write statements to find and display a
topological order for this graph.
21.
A graph is said to be
biconnected
if two paths that do not share edges or vertices exist between every pair of vertices.
a.
Which graphs in Figure 28-1 and 28-4 are biconnected?
b.
What are some applications that would use a biconnected graph?
22.
A
critical path
in a weighted, directed, acyclic graph is the path with the greatest weight. Let's assume that all
edge weights are positive. Give each vertex a value equal to the weight of a path to that vertex. Initially, each
vertex's value is zero.
We can find the critical path by considering the vertices one at a time in topological order. For each vertex,
consider all the edges that leave the vertex. For each of these edges, add the weight of the edge and the value of
the edge's source vertex. Compare the sum with the value of the edge's destination vertex. Make the larger of
these values the value of the destination vertex. After all vertices have been visited, the largest value stored in a
vertex will be the weight of the critical path.
Find the critical path for the graph in Figure 28-23.
