SIAM Review, January 1983

Graphs, Networks and Algorithms by M.N.S.Swamy and K.Thulasiraman, John-Wiley, New York, 1981, xviii+592 pp.37.50.

This book is composed of three parts, as suggested by title. Each of these parts could have been a book by itself. I prefer to think of this work as being a merger of three books. Because of the vast amount of material, it would take two or three semesters to teach most of the topics covered. This first part is Graph Theory. This part contains a through discussion of most of the topics usually covered in a graph theory text.(Emphasis is placed on those topics which will be applied in the second and third parts. There are ten chapters in the first part: they are titled Basic Concepts, Trees, Cutsets and Circuits, Eulerian and Hamiltonian Graphs, Graphs and Vector Spaces, Directed Graphs, Matrices of a Graph, Planarity and Duality, Connectivity and Matching, Covering and Coloring and Matroids. There is an excellent discussion of 1-isomorphism and 2-isomorphism of graphs. This isomorphism discussion is the best that I have found in the many graph theory texts that I have read. Duality is presented in such a way that the reader sees its importance to electrical network theory from the outset. There is an excellent discussion of how to construct a graph( if such a graph exists) having a specified degree sequence. The chapter titled matroid is the best chapter on matroids that I have found in any book.

The second part of the book is Electrical Network Theory. There are three chapters in this part: they are titled Graphs and Networks, Resistance N-Port Networks, and Network Functions and Network Sensitivity. I feel that the reader would need at least an undergraduate background in electrical engineering to be able to understand most of the material in this part. I do not have this background; I obtained very little from reading this part. From what I understood, the authors were developing electrical network theory by applying some of the theorems of graph theory presented in the first part of this book. One of my electrical engineering friends pointed out that the chapter on n-port networks is the most difficult chapter of the three chapters on electrical networks.

The third of the book is Algorithmic Graph Theory. There are two chapters in this part: they are titled Algorithmic Analysis and Algorithmic Optimization. On page 427, the authors make the following observation: " Graphs which arise in the study of real-life problems are very large and complicated. Analysis of such graphs in an efficient manner, therefore, involves the design of efficient computer algorithms." Algorithms considered in this part of the book include algorithms for constructing the transitive closure of a directed graph, finding a transitive orientation (if it exists) of an undirected graph, depth-first searching in both undirected and directed graphs, determining biconnected components of an undirected graph, determining strongly connected components of a directed graph, studying certain aspects of program graphs, determining shortest paths in weighted graphs, finding maximal matchings in graphs, and finding a maximal flow in a transport network. On p.569, the authors list 14 algorithm topics for further study. Each of the 15 chapters in the book ends with a list of many references. For example, the Algorithmic Optimization chapter has 108 references. These numerous references make it possible tofurther explore topics which interest the reader.

In conclusion, I found that reading this book from cover to cover took a very long time. The authors packed a lot of information into it. The first part of this book is acceptable to a wide audience. The second and third parts of this book are accessible to experts, namely, electrical engineers and computer scientists, respectively.

Earl Glen Whitehead, Jr.

University of Pittsburgh