PREFACE On August 15 and 16, 1981, an American Mathematical Society Short Course was held on The Mathematics of Networks at the Summer Meeting in Pitts- burgh, Pennsylvania. This volume represents a considerable expansion of the lecture notes that were prepared by the speakers for the benefit of the partici- pants. We, the speakers and the organizer, were very pleased with the substantial attendance at the Short Course and by the enthusiastic support of the AMS staff and of the Short Course subcommittee. It was also a pleasure to have contri- buted to such a distinguished series this Short Course was the seventeenth in the series, which began in August, 1973. The theory of networks is a very lively one, both in terms of developments in the theory itself and in terms of the variety of its applications as the chapters in this volume should show. The range of theory and applications is so great that neither the Short Course nor this volume could hope to give a full and sys- tematic treatment of the subject. However, it was my intention that both would introduce most of the basic ideas of network theory and develop some of these ideas to a considerable extent. In addition, my plan was to introduce a number of more specialized topics, including a number of areas of active research and quite a wide variety of applications, in order to indicate the breadth and depth of the field. Thanks to the contributors, these objectives were met. The first chapter, Introduction to Basic Network Problems, sets the stage. Here, Frank Boesch gives the basic definitions in the mathematics of networks and in the closely-related topic of graph theory. (Indeed, problems that are graph-theoretical in the mathematical sense are often thought of as being net- work problems when the intended application relates to a physical network.) Then, he discusses two of the most fundamental network problems, the shortest path problem and the minimum spanning tree problem, and some of their vari- ants. Finally, he discusses the less basic, but very interesting, area of network reliability. In the second chapter, Maximum Flows in Networks, Frances Yao considers the problem most often thought of in connection with the mathematics of networks. It would not be unfair to think of network flows as the most funda- mental of all problems in the field. The history of this topic is one of steady ix

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.