вход по аккаунту



код для вставкиСкачать
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
/ 8U10$$0BR1
06-09-97 15:20:38
W: Networks
Без категории
Размер файла
19 Кб
Пожаловаться на содержимое документа