CD6s-1
CD Supplement to Chapter 6 Minimum Spanning Tree Problems
Review Questions
6s-1 The nodes are given, but the links need to be designed.
6s-2 A state-of-the-art fiber-optic network is being designed.
6s-3 A tree is a network that does not have any paths that begin and end at the same node
without backtracking. A spanning tree is a tree that provides a path between every pair of
6s-6 No, it is not a special type of a minimum cost flow problem.
6s-7 A greedy algorithm will solve a minimum spanning tree problem.
Problems
6s.1
A C E
B
D F
G
2 2
13 1
5
CD6s-3
6s.2
AC
E
B
D
F
G
41
2
4 1
6
1. B—C: Cost = 1 *lowest 4. B—E: Cost = 7
2. B—A: Cost = 4 C—F: Cost = 4 *lowest
B—E: Cost = 7 C—E: Cost = 5
C—E: Cost = 5 F—E: Cost = 1 *lowest
3. B—A: Cost = 4 *lowest F—G: Cost = 8
B—E: Cost = 7 6. E—G: Cost = 6 *lowest
6s.3
A D
E H
I
F
G
4
1
2
4
B
C J
K
3
3
2
2
3
CD6s-4
F—J: Cost = 5 F—C: Cost = 6
G—D: Cost = 2 F—J: Cost = 5
G—E: Cost = 2 H—K: Cost = 7
F—J: Cost = 5 D—C: Cost = 4
G—D: Cost = 2 *lowest F—C: Cost = 6
G—E: Cost = 2 F—J: Cost = 5
4. D—A: Cost = 6 D—A: Cost = 6
D—B: Cost = 5 D—C: Cost = 4
D—E: Cost = 2 *lowest F—C: Cost = 6
I—K: Cost = 8 H—K: Cost = 7
I—J: Cost = 3 I—K: Cost = 8
5. D—A: Cost = 6 J—K: Cost = 4
6s.4 a) The company wants a path between each pair of nodes (groves) that minimizes cost
(length of road).
CD6s-5
b) 7—8 : Distance = 0.5
7—6 : Distance = 0.6
6—5 : Distance = 0.9
6s.5 a) The bank wants a path between each pair of nodes (offices) that minimizes cost
(distance).
b) B1—B5 : Distance = 50
B5—B3 : Distance = 80
B1—B2 : Distance = 100
6s.6 The creation of the new communications network is a minimum spanning tree problem. As
usual, a greedy algorithm solves this type of problem.
Arcs are added to the network in the following order (one of several optimal solutions):
Rostov – Orenburg
120
Ufa – Orenburg
75
Saratov – Orenburg
95
Saratov – Samara
100
Samara – Kazan
95
Ufa – Yekaterinburg
125
Perm – Yekaterinburg
85