Chapter 20 – Minimal Spanning Tree
True / False
1. The arcs in a minimal spanning tree problem can be measured in terms of criteria other than distance.
a.
True
b.
False
2. Cases in which a greedy algorithm provides the optimal solution are rare.
a.
True
b.
False
3. The minimum spanning tree allows a person to visit every node without backtracking.
a.
True
b.
False
4. In the minimal spanning tree algorithm, you must consider the unconnected nodes that can be reached from any of the
connected nodes, rather than arbitrarily considering only one of the connected nodes.
a.
True
b.
False
5. The minimum spanning tree algorithm is considered a heuristic.
a.
True
b.
False
6. The minimal spanning tree algorithm will lead to an optimal solution regardless of which node is chosen at the start of
the algorithm.
a.
True
b.
False
7. It is possible for minimal spanning tree problems to have alternative optimal solutions.
a.
True
b.
False
Multiple Choice
8. Consider a minimal spanning tree problem in which pipe must be laid to connect sprinklers on a golf course. When
represented with a network,
a.
the pipes are the arcs and the sprinklers are the nodes.
b.
the pipes are the nodes and the sprinklers are the arcs.
c.
the pipes and the sprinklers are the tree.
d.
each sprinkler must be connected to every other sprinkler.
Chapter 20 – Minimal Spanning Tree
9. The minimal spanning tree algorithm is considered to be:
a.
a greedy algorithm.
b.
an arc algorithm.
c.
a non-optimal algorithm.
d.
a non-feasible algorithm.
10. The minimal spanning tree algorithm has connected nodes 8 and 9. Node 8 could be connected to nodes 11 (distance
6) and 12 (distance 5) and node 9 could be connected to node 12 (distance 3) and node 13 (distance 2). Which will you do
next?
a.
connect 8 to 11
b.
connect 8 to 12
c.
connect 9 to 12
d.
connect 9 to 13
11. For a network consisting of N nodes, a minimal spanning tree will consist of:
a.
N − 2 arcs.
b.
N − 1 arcs.
c.
N arcs.
d.
N + 1 arcs.
12. The minimal spanning tree algorithm will:
a.
sometimes fail to produce a feasible solution.
b.
always produce a feasible, but not necessarily optimal, solution.
c.
always produce an optimal solution.
d.
always produce an optimal, but not necessarily feasible, solution.
Subjective Short Answer
13. For the following eight cities with the given distances, find the minimal spanning tree path.
To City
From City
1
2
3
4
5
6
7
1
—
5
2
6
—
—
—
2
5
—
—
4
6
—
—
3
2
—
—
3
—
12
—
4
6
4
3
—
9
8
—
5
—
6
—
9
—
0
14
6
—
—
12
8
0
—
4
7
—
—
—
—
14
4
—
14. Find the minimal spanning tree for this network.
Chapter 20 – Minimal Spanning Tree
15. Find the minimal spanning tree for this network.
16. The numbers on this network represent times to distribute a message. Use the minimal spanning tree algorithm to
determine how messages should be passed in order to minimize total time.
Chapter 20 – Minimal Spanning Tree
17.
Ethernet cable costs $25 per foot to install. The table below gives the approximate direct routing distance in feet between
various pairs of machines.
WS1
WS2
LP1
LP2
CC
FM
WS1
0
46
16
23
100
29
WS2
0
81
44
67
98
LP1
0
45
57
36
LP2
0
38
73
CC
0
52
a. Use the minimal spanning tree algorithm to determine the least cost method of connecting all machines.
b. How much cheaper would it be if the company decided not to hook up the second printer to this system?
18.
Wondercamp is planning a new resort for the urban professional who wishes to “get back to nature”. For a hefty fee, it
plans to transport clients up the Crocodile River by canoe and then have their clients camp at one of eight designated
campsites.
Chapter 20 – Minimal Spanning Tree
They must build a 1000-yard trail from the river to the first campsite as there are no feasible alternatives. It then wishes to
build a sequence of trails (of minimum total length) so that every campsite can be reached from any other campsite. A
study of the terrain of the area has yielded the following possibilities for trails between campsites. Which trails should be
built?
19.
Griffith’s Cherry Preserve is a combination wild animal habitat and amusement park. Besides their phenomenally
successful wild animal safari tour, there are eight different theme areas in the amusement park.
Chapter 20 – Minimal Spanning Tree
Essay
20. What is a greedy algorithm? What is an example of a greedy algorithm?
21. What are some other criteria (measures), besides distance, that might be minimized in a minimal spanning tree
problem? Provide an example situation for each criterion.
22. Describe three examples of minimal spanning tree problems.