This book fills a need for a thorough introduction to graph theory that features both the understanding and writing of proofs about graphs. Verification that algorithms work is emphasized more than their complexity. An effective use of examples, and huge number of interesting exercises, demonstrate the topics of trees and distance, matchings and factors, connectivity and paths, graph coloring, edges and cycles, and planar graphs. For those who need to learn to make coherent arguments in the fields of mathematics and computer science.
"synopsis" may belong to another edition of this title.
This text offers the most comprehensive and up–to–date presentation available of the fundamental topics in graph theory. It develops a thorough understanding of the structure of graphs and the techniques used to analyze problems in graph theory. It includes basic graph algorithms and particularly thought-provoking exercises.Excerpt. © Reprinted by permission. All rights reserved.:
Graph theory is a delightful playground for the exploration of proof techniques in discrete mathematics, and its results have applications in many areas of the computing, social, and natural sciences. The design of this book permits usage in a one-semester introduction at the undergraduate or beginning graduate level, or in a patient two-semester introduction. No previous knowledge of graph theory is assumed. Many algorithms and applications are included, but the focus is on understanding the structure of graphs and the techniques used to analyze problems in graph theory.
Many textbooks have been written about graph theory. Due to its emphasis on both proofs and applications, the initial model for this book was the elegant text by J.A. Bondy and US.R. Murty, Graph Theory with Applications (Macmillan/NorthHolland 1976). Graph theory is still young, and no consensus has emerged on how the introductory material should be presented. Selection and order of topics, choice of proofs, objectives, and underlying themes are matters of lively debate. Revising this book dozens of times has taught me the difficulty of these decisions. This book is my contribution to the debate.
The Second Edition
The revision for the second edition emphasizes making the text easier for the students to learn from and easier for the instructor to teach from. There have not been great changes in the overall content of the book, but the presentation has been modified to make the material more accessible, especially in the early parts of the book. Some of the changes are discussed in more detail later in this preface; here I provide a brief summary.
Various features of this book facilitate students' efforts to understand the material. There is discussion of proof techniques, more than 1200 exercises of varying difficulty, more than 400 illustrations, and many examples. Proofs are presented in full in the text.
Many undergraduates begin a course in graph theory with little exposure to proof techniques. Appendix A provides background reading that will help them get started. Students who have difficulty understanding or writing proofs in the early material should be encouraged to read this appendix in conjunction with Chapter 1. Some discussion of proof techniques still appears in the early sections of the text (especially concerning induction), but an expanded treatment of the basic background (especially concerning sets, functions, relations, and elementary counting) is now in Appendix A.
Most of the exercises require proofs. Many undergraduates have had little practice at presenting explanations, and this hinders their appreciation of graph theory and other mathematics. The intellectual discipline of justifying an argument is valuable independently of mathematics; I hope that students will appreciate this. In writing solutions to exercises, students should be careful in their use of language ("say what you mean"), and they should be intellectually honest ("mean what you say").
Although many terms in graph theory suggest their definitions, the quantity of terminology remains an obstacle to fluency. Mathematicians like to gather definitions at the start, but most students succeed better if they use a concept before receiving the next. This, plus experience and requests from reviewers, has led me to postpone many definitions until they are needed. For example, the definition of cartesian product appears in Section 5.1 with coloring problems. Line graphs are defined in Section 4.2 with Menger's Theorem and in Section 7.1 with edge-coloring. The definitions of induced subgraph and join have now been postponed to Section 1.2 and Section 3.1, respectively.
I have changed the treatment of digraphs substantially by postponing their introduction to Section 1.4. Introducing digraphs at the same time as graphs tends to confuse or overwhelm 'students. Waiting to the end of Chapter 1 allows them to become comfortable with basic concepts in the context of a single model. The discussion of digraphs then reinforces some of those concepts while clarifying the distinctions. The two models are still discussed together in the material on connectivity.
This book contains more material than most introductory texts in graph theory. Collecting the advanced material as a final optional chapter of "additional topics" permits usage at different levels. The undergraduate introduction consists of the first seven chapters (omitting most optional material), leaving Chapter 8 as topical reading for interested students. A graduate course can treat most of Chapters 1 and 2 as recommended reading, moving rapidly to Chapter 3 in class and reaching some topics in Chapter 8. Chapter 8 can also be used as the basis for a second course in graph theory, along with material that was optional in earlier chapters.
Many results in graph theory have several proofs; illustrating this can increase students' flexibility in trying multiple approaches to a problem. I include some alternative proofs as remarks and others as exercises.
Many exercises have hints, some given with the exercise statement and others in Appendix C. Exercises marked "(-)" or "(+)" are easier or more difficult, respectively, than unmarked problems. Those marked "(+)" should not be assigned as homework in a typical undergraduate course. Exercises marked "(!)" are especially valuable, instructive, or entertaining. Those marked "(*)" use material labeled optional in the text.
Each exercise section begins with a set of "(-)" exercises, ordered according to the material in the section and ending with a line of bullets. These exercises either check understanding of concepts or are immediate applications of results in the section. I recommend some of these to my class as "warmup" exercises to check their understanding before working the main homework problems, most of which are marked "(!)". Most problems marked "(-)" are good exam questions. When using other exercises on exams, it may be a good idea to provide hints from Appendix C.
Exercises that relate several concepts appear when the last is introduced. Many pointers to exercises appear in the text where relevant concepts are discussed. An exercise in the current section is cited by giving only its item number among the exercises of that section. Other cross-references are by Chapter. Section. Item.
Organization and Modification
In the first edition, I sought a development that was intellectually coherent and displayed a gradual (not monotonic) increase in difficulty of proofs and in algorithmic complexity.
Carrying this further in the second edition, Eulerian circuits and Hamiltonian cycles are now even farther apart. The simple characterization of Eulerian circuits is now in Section 1.2 with material closely related to it. The remainder of the former Section 2.4 has been dispersed to relevant locations in other sections, with Fleury's Algorithm dropped.
Chapter 1 has been substantially rewritten. I continue to avoid the term "multigraph"; it causes more trouble than it resolves, because many students assume that a multigraph must have multiple edges. It is less distracting to append the word "simple" where needed and keep "graph" as the general object, with occasional statements that in particular contexts it makes sense to consider only simple graphs.
The treatment of definitions in Chapter 1 has been made more friendly and precise, particularly those involving paths, trails, and walks. The informal groupings of basic definitions in Section 1.1 have been replaced by Definition items that help students find definitions more easily.
In addition to the material on isomorphism, Section 1.1 now has a more precise treatment of the Petersen graph and an explicit introduction of the notions of decomposition and girth. This provides language that facilitates later discussion in various places, and it permits interesting explicit questions other than isomorphism.
Sections 1.2-1.4 have become more coherent. The treatment of Eulerian circuits motivates a...
"About this title" may belong to another edition of this title.
Book Description PEARSON EDUCACION. Book Condition: Muy Bueno / Very Good. Bookseller Inventory # 100000000853250
Book Description Prentice Hall, 2007. Hardcover. Book Condition: Used: Good. We ship International with Tracking Number! May not contain Access Codes or Supplements. Buy with confidence, excellent customer service! j. Bookseller Inventory # 0131437372D