Page 376 -

356 CHAPTER 8 NETWORK MODELS

Figure 8.14 Minimal Spanning Tree Communications Network for the Regional
Computer Centre

5
2 30
20
3
1 30 10
4

20

6

Repeating the step of always adding the closest unconnected node to the con-
nected segment of the network provides the minimal spanning tree solution
shown in Figure 8.14. Follow the steps of the algorithm, and see whether you
obtain this solution. The minimal length of the spanning tree is given by the sum
of the distances on the arcs forming the spanning tree. In this case, the total
distance is 110km for the computer centre’s communications network. Note that
while the computer centre’s network arcs were measured in distance, other
network models may measure the arcs in terms of other criteria such as cost,
time and so on. In such cases, the minimal spanning tree algorithm will identify
the optimal solution (minimal cost, minimal time, etc.) for the criterion being
Can you now find a considered.
minimal spanning tree The computer solution to the regional computer centre’s problem is shown in
for a network? Try Figure 8.15. The Management Scientist was used to obtain the minimal spanning
Problem 7.
tree solution of 110km.

NOTES AND COMMENTS

1 The Management Science in Action, EDS Designs a action available at that stage. Following this
Communication Network, describes an interesting strategy at each successive stage will provide the
application of the minimal spanning tree algorithm. overall optimal solution. Cases in which a greedy
2 The minimal spanning tree algorithm is algorithm provides the optimal solution are rare.
considered a greedy algorithm because at each For many problems, however, greedy algorithms
stage we can be ‘greedy’ and take the best are excellent heuristics.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.