Graphs, Networks, and Algorithms - M.N.S. Swamy and K. Thulasiraman (New York: Wiley, 1981, 592 pp.) Reviewed by Basil R. Myers, Department of Electrical Engineering, University of Maine, Orono, ME 00469.

This substantial book is broken up as follows: Part I - chapters 1-10, 300 pp.-graph theory; Part II - chapters 11-13 - electrical network theory; Part III - chapters 14-15, 153 pp. - algorithmic theory.

Part I gives a broader, more aesthetic introduction to the theory of finite graphs than is usually found in textbooks which, like this one, include electrical engineers among their intended readers. Part I constitutes an admirable textbook in itself on finite graph theory, which should be acceptable to the purist as well as the reader who is not. As noted by the authors in their preface, it includes presentation (along classical, well-developed lines) on trees, Hamiltonian and Euler graphs, planarity, connectivity, matching and coloring, and an introduction to the rapidly expanding theory of matroids and its applications to electrical network theory and combinational optimization problems. Part I is particularly easy to read, understand, and absorb. Hence, it can be highly recommended as course material for students and as a personal library reference source for those who have any interest in or curiosity about graph theory and its application to electrical engineering and computer science.

1. Notation is standard, and the authors do a superb job of blending engineering terminology with the mathematics, without blemish to the mathematics, when called for in reference to applications. At the outset in chapter 1, for example, they have defined the engineering term "short-circuiting" or "identifying" in graph-theoretic term, as an operation on a graph, thus eliminating the sort of fuzzinesses that can arise in thinking of such an operation in physical terms.The text is not flawless; for example the authors' definition of a circuits, p. 10, allows circuits of order 1 (that is, trivial graphs with one edge) and 2 (that is, two parallel edges), whereas it is generally more convenient and more often the case to restrict the order of a circuit to be at least 3.
2. Each chapter in this book ends in a section which recommends articles and topics for further reading and study, followed by a wealth of exercises and a list of both the important classical references and those of recent years which dictate the present state of the art. The exercises generally range in difficulty and challenge from the routine to those that are anything but. The authors have also used some of the exercises very effectively as vehicles to introduce further concepts or results not discussed in the text. For example, the concepts of a traversal matroid, a Fano matroid, and a gammoid are all introduced in chapter 10's exercises, rather than in the text.
3. A hypercritic might complain that there is no treatment of probabilistic graphs in the book, and that Ramsey's name is noticeably absent from the list of references. Many of the results from Ramsey's theory are, in fact, interspersed through out the book, and so this reviewer does not find that the book is of less consequence because of such omission.

Part II is a concise presentation of classical, basic electrical network theory which every serious student of circuits and systems should have at his fingertips. Topics include the application of the principal partition of a graph to mixed-variable analysis, the no-gain property of resistance networks, realization of circuit and cutset matrices of resistance networks, topological (graph-theoretic) formulas for network functions, and Tellegen's important theorem and the beauty of its application to the computation of network sensitivities. This material will be perhaps the least stirring of the three parts of the book to those who do not have much interest in or passion for electrical network theory, more so because it is unavoidably heavy on matrix theory. This material does, however, bring out the beauty of the well-known matrix-tree theorem of graph theory in facilitating the derivation of network functions. The authors have noted in their preface that "Tellegen's theorem … is essentially graph-theoretic in nature, …. It is surprising that such an important theorem lay dormant for so many years …."

Part III, algorithmic graph theory, though only two chapters, constitutes an important feature of this book, and is what makes it different from others which deal with graph theory and its applications. This material is of primary interest to the computer scientist. But today's practical problems are generally complex; when formulated on a graph-theoretic basis, the extraction of useful solutions depends upon the efficiency of the computer algorithms used to obtain them. Thus, this material is requisite to the background of those concerned with applications, and therefore very much a part of the compass of this book.

As stated in the preface, chapter 14 is given to algorithms for the analysis of graphs and chapter 15 to optimization problems. Topics include algorithms for reducibility of flow graphs, dominators, shortest paths, matchings, optimum binary search trees, network flows, optimum branchings, Hopcroft and Karp's analysis of a bipartite matching algorithm, and Edmonds and Karp's analysis of Ford and Fulkerson's labeling algorithm.

The authors' comment, again in the preface, that "A major omission from this book is a discussion of NP-complete problems. However, this topic is beyond the scope of this book," should not bother anyone. Indeed, this comment is adequately compensated for a brief discussion of NP-completeness in the section. "Further reading," at the end of chapter 14.

The material in the two chapters of Part III is supported and supplemented by an extensive and up-to-date list of references; the reader should find the exercises at the end of each chapter anything but disappointing.

This is a very readable, valuable, and authoritative book, which encompasses a wealth of much-needed material. The authors are clearly masters of their respective technical arts and have a unique ability and effectiveness in communicating that mastery to others through the written work.