Applications of graph theory for the determination of optimum locations in certain networks

The purpose of this thesis is to illustrate methods of finding optimum locations in networks. As an application of these methods, the places to build fire stations are determined such that the expected losses due to fires will be minimal. A general discussion of the fundamental concepts of graph theory is given. This discussion is by no means exhaustive as there are excellent books on the subject of graph theory. The concept of a distance matrix is extended to that of a weighted distance matrix. This matrix is built from a model of some municipal structure. The concept of a multimedian is generalized and two algorithms, The Extent Vector Method and the Multiple Distance Matrix Algorithm, are developed for locating optimum points in networks. Examples of the necessary analysis needed prior to applying the algorithms are included as well as the applications of the algorithms. Other methods for locating sites for fire stations are then discussed. Conclusions and suggestions for further research are included in the final chapter.