Book Review Introduction to Graph Theory, by Douglas B. West, Prentice-Hall, Upper Saddle River, NJ, 1996, 512 pp., Price: $66.00 Introduction to Graph Theory is a welcome replacement for the longawaited revision of the classic text by Bondy and Murty, which the author claims was his initial model. West has provided an up-to-date and equally elegantly written text. As in his model, emphasis is on understanding the structure of graphs and the techniques used to analyze problems. Numerous algorithms and applications are included, but the focus remains on proofs. Many texts in graph theory create a dead zone of definitions in the introductory chapters. West avoids this by emphasizing proof techniques while providing the basic terminology and definitions in Chapters 1 (Fundamental Concepts) and 2 (Trees and Distance). Early in Chapter 1, he includes discussions of proof by induction, proof by contradiction, algorithmic proof, and the use of ‘‘extremality’’ (for example, to prove that a graph has a path with length at least l, then consider a longest path in the graph). These techniques are illustrated throughout with clearly presented examples of their use, including a section on the ‘‘induction trap.’’ In addition, West’s elegant style of presentation provides a model for the student in writing her/his own arguments. Some highlights from the text: Chapter 1 (Fundamental Concepts) begins with definitions and examples, paths and proofs (induction arguments, extremality, contradiction), counting, degrees and constructive proof; Chapter 2 (Trees and Distance) introduces trees and spanning trees and includes algorithms for finding minimum spanning trees and shortest paths and concludes with Eulerian circuits and digraphs; Chapter 3 (Matchings and Factors) includes Hall’s matching condition and algorithms for finding a maximum bipartite matching and advances to a discussion of factors in graphs; Chapter 4 (Connectivity and Paths) discusses connectivity (both vertex and edge), introduces Menger’s Theorem and network flow problems; Chapter 5 (Graph Coloring) introduces vertex colorings along with investigation of the structure of critical graphs and enumeration of colorings; Chapter 6 (Edges and Cycles) covers line graphs, edge colorings, and Hamiltonian graphs; Chapter 7 (Planar Graphs) includes a discussion of planar embeddings and Euler’s formula, Kuratowski’s Theorem, and parameters of planar graphs; Chapter 8 (Additional Topics) includes material on perfect graphs, matroids, Ramsey theory, random graphs, and eigenvalues. The author suggests Chapters 1–7 for an undergraduate course and Chapters 1–7 and selected parts of Chapter 8, treating Chapters 1 and 2 lightly, for a graduate course. The text includes over 850 exercises of varying difficulty. Most require written proofs and often are related to results in the recent literature. Many are marked ( 0 ), ( / ), or (!) for those the author considers ‘‘especially easy, especially difficult,’’ or ‘‘especially valuable, instructive or entertaining.’’ The easy exercises are particularly useful in elucidating an idea or (sometimes) revealing a pitfall. The text contains a single list of over 500 references to articles and books. These range from classic articles in which important results were introduced to those representing recent research in the field. There are also glossaries of terms and notation. Throughout the text, West motivates the exploration of graph theory through applications, while emphasizing the theoretical foundation for algorithms. In addition he makes brief incursions into areas not usually found in texts, e.g., graceful labelings can be found in the chapter on trees, perfect graphs are discussed in the chapter on coloring, and genus of graphs appears in the chapter on planarity. The inclusion of a‘‘nuts and bolts’’ discussion of complexity is especially useful. A distinguishing feature of the production of this text is that preliminary versions were used by over twenty instructors at various universities. I used preliminary drafts of the text in two different one-semester first-year graduate courses in graph theory at the University of Colorado at Denver. Most of my students were being exposed to graphs for the first time. We covered the first two chapters thoroughly and then found it difficult to cover later chapters to their deserved depth within the time allowed. West has responded by providing a road map for the instructor in the introduction, labeling some sections as ‘‘optional,’’ and by moving some material to later sections. We also provided the author with many comments on the text. The author responded to all of the students’ comments, and in several instances, he rewrote sections where students demonstrated a lack of comprehension. This edition provides an excellent text, balanced between thoroughness and accessibility, for a one-semester graduate or advanced undergraduate course in graph theory. The text still contains much more material than other books to which it might be compared. It contains enough additional material for a two-semester or more advanced graduate course. I also recommend it as a reference for the practitioner, as it includes an introduction to and recent advances in many topics of current interest to researchers in the field. Kathryn L. Fraughnaugh University of Colorado at Denver Denver, CO 80217 q 1997 John Wiley & Sons, Inc. CCC 0028-3045/97/010073-01 73 / 8U10$$0BR1 06-09-97 15:20:38 netwa W: Networks NET-BR-1

1/--страниц