Зарегистрироваться
Восстановить пароль
FAQ по входу

West D.B. Introduction to Graph Theory

  • Файл формата pdf
  • размером 17,15 МБ
  • Добавлен пользователем
  • Отредактирован
West D.B. Introduction to Graph Theory
Издательство Pearson Education, 2001, -871 pp.
Graph theory is а 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 а one-semester introduction at the undergraduate or beginning graduate level, or in а 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 U.S.R. Murty, Graph Theory with Applications (Macmillan/North-Ноllаnd [1976]). Graph theory is still young, and no consensus has emerged on how the introductory material should Ье 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 to the difficulty of these decisions. This book is my contribution to the debate.
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.
This book contains more material than most introductory texts in graph theory. Collecting the advanced material as а 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. А 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 а 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 С. Exercises marked "(-)" or "(+)" are easier or more difficult, respectively, than unmarked problems. Those marked "(+)" should not be assigned as homework in а 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 а set of "(-)" exercises, ordered according to the material in the section and ending with а 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 а good idea to provide hints from Appendix С.
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.ltem.
Fundamental Concepts
Тrees and Distance
Matchings and Factors
Connectivity and Paths
Coloring of Graphs
Planar Graphs
Edges and Cycles
Additional Topics (optional)
А Mathematical Background
В Optimization and Complexity
С Hints for Selected Exercises
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация