MATHEMATICAL REVIEWS 1982

Review of J605 305

XT138's L

Swamy, M. N. S. and Thulasiraman, K.

Graphs, networks, and algorithms.

John Wiley & Sons, Inc.

New York, NY, 1981.

Classification: O 5 C 99 , 94 C 15 IX+592 pp. $37.50

ISBN: 0-47-03503-3

REVIEWER: Narsingh Deo (Pullman, Wash.)

263

Starting with Gustav Kirchhoff, electrical engineers have been responsible for a great deal of research in graph theory and for enhancing its popularity in and out of the classroom. One of the earliest English textbooks in graph theory (with emphasis on applications to electrical networks) was written by two electrical engineers -Sundaram Seshu and Myril Reed (Linear Graphs and Electrical Networks, Addison-Wesley, 1961). In the intervening 20 years, an impressive amount of work has been done in applied graph theory, not only by electrical engineers but also by researchers in computer science and operations research. A substantial portion of the activity of the past two decades has been in algorithmic graph theory, which is a direct outcome of the widespread availability of the computer.

This book, written by two professors of electrical engineering and computer science, describes in a lucid and clear-cut fashion the theory of finite graphs and its "natural" and immediate applications to the study of electrical networks. It is organized into three parts. Part I provides an introductory treatment of the most basic graph-theoretic concepts: trees, paths, cutsets and cycles, Eulerian and Hamiltonian graphs; matrices and vector spaces associated with graphs; planarity and duality; coloring, covering, matching, and connectivity. There is also a chapter on matroids and their relationship to greedy algorithm. It is unusual and refreshing to see an entire chapter on matroids in a book of this type. With only a small amount of additional effort, matroids provide a good deal of insight into networks. Part I (consisting of the first 300 pages) provides the theoretical foundation for the later parts.

Part II demonstrates the role of graph theory as an important analytical tool in the study of electrical networks. It includes sections on the principal partition of a graph; a proof of the no-gain property of resistance networks; several results in the theory of resistance networks; and a network for realizing cutset and circut matrices. The conc1uding chapter in this part develops topological formulas for network functions and Tellegen's theorem, together with its application to computing network sensitivity. This reviewer was pleased to see that the authors included Tellegen's theorem --the graph-theoretic significance of which is often missed by many.

The third part of the book highlights computational aspects of graph-theoretic problems. It consists of two chapters --one on algorithmic analysis and one on algorithmic optimization. Among the algorithms presented are those for flow graph reducibility, dominators, shortest paths, matchings, optimum binary search trees, network flows and optimum branchings. A comment on the style of describing the algorithms: it is this reviewer's opinion that a structured Algol/Pascal-like style of presenting the f1ow-charts- would have been more readable and easier to implement and analyze, than the classical step-by-step presentation used in these two chapters.

It would have been of general interest to many readers to see a brief explanation of the notion of NP-completeness, chiefly because of its central importance to the concept of an "efficient" algorithm. Although the authors have mentioned in the preface that this was beyond the scope of the book, this reviewer does not see why a brief treatment of NP-completeness should be beyond the scope of a complete and a reasonably advanced-level textbook such as this.

Each chapter is well laid out and contains a set of problems. It also includes a remarkably complete set of references. Since the number of references is so large, the authors have wisely included a section in each chapter to guide the reader through a selected subset of the references. The book has a subject index and an author index --both are done well. The book is attractively printed and appears to be largely free of misprints.

To conclude, Graphs, Networks and Algorithms is a valuable contribution because of its clear-cut exposition of graph-theoretical results together with its description of the applications of these results in electrical networks and computer science. It can serve as an excellent introductory textbook as well as a useful reference book for electrical engineers, computer scientists and operations researchers.