Proceedings of Symposia in Applied Mathematics Volume 26, 1982 INTRODUCTION TO BASIC NETWORK PROBLEMS FRANK BOESCH ABSTRACT. A great many problems of design and analysis of large sys- tems can be formulated and resolved using the tools of graph and net- work theory. Herein we present the basic concepts of this theory. We introduce the shortest path problem and give its solution. The problem of finding a minimum cost, connected subnetwork is discussed. In addition, certain problems related to the design of reliable net- works are introduced. INTRODUCTION Large communications, transmission, and transportation systems are all characterized by the fact that they involve the interconnection of many com- ponents to form the system. Typical examples of such systems are "computer networks", "gas pipe-line grids", "power grids", and "highway networks". [16,3] The basic mathematical concept underlying the systems is that of a graph or a network. Geometric graphs are defined first, subsequently we define networks. Probably the first problem to be formulated and solved by a graph model is the famous Konigsberg bridge problem. It is used here to illustrate basic concepts. For a survey account of graph theory, consult Harary E18^• The city of Konigsberg in East Prussia is divided by the Pregel River, which con- tains two islands that are part of that city, cf., Fig. 1. Konigsberg (now Kaliningrad) is perhaps most famous for being the birthplace of "The Fox of Konigsberg," immanuel Kant (1724-1804). However, it is also the birthplace of the following graph theory puzzle: "Is it possible to cross each bridge once and only once and return to where you started?". Figure 1 1980 Mathematics Subject Classification. 94C15 © 1982 American Mathematical Society 0160-7634/82/0000-0841/$08.25 1 http://dx.doi.org/10.1090/psapm/026/9893

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 1982 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.