### 基本信息

- 原书名：Introduction to Graph Theory,Second Edition
- 原出版社： Prentice Hall/Pearson

- 作者：
**（美）Douglas B.West** - 丛书名：
**经典原版书库** - 出版社：机械工业出版社
- ISBN：
**9787111152156** - 上架时间：2004-10-12
- 出版日期：2004 年10月
- 开本：16开
- 页码：588
- 版次：2-1
- 所属分类：数学 > 代数，数论及组合理论 > 模糊数学

教材

### 编辑推荐

全书力求保持按证明的难度和算法的复杂性循序渐进的风格，使学生能够深入理解书中的内容。

### 内容简介

### 目录

Preface

Chapter 1 Fundamental Concepts

1.1 What Is a Graph?

The Definition, 1

Graphs as Models, 3

Matrices and Isomorphism, 6

. Decomposition and Special Graphs, 11

Exercises, 14

1.2 Paths, Cycles, and Trails

Connection in Graphs, 20

Bipartite Graphs, 24

Eulerian Circuits, 26

Exercises, 31

1.3 Vertex Degrees and Counting

Counting and Bijections, 35

Extremal Problems, 38

Graphic Sequences, 44

Exercises, 47

1.4 Directed Graphs

### 前言

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-Holland [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.

Optional material within non-optional sections is now designated by (.); such material is not used later and can be skipped. Most of it is intended to be skipped in a one-semester course. When a subsection is marked "optional", the entire subsection is optional, and hence no individual items are starred.

For less-experienced students, Appendix A has been added as a reference sum mary of helpful material on sets, logical statements, induction, counting arguments, binomial coefficients, relations, and the pigeonhole principle.

~ Many proofs have been reworded in more patient language with additional details, and more examples have been added.

~ More than 350 exercises have been added, mostly easier exercises in Chapters 1-7. There are now more than 1200 exercises.

~ More than 100 illustrations have been added; there are now more than 400. In illustrations showing several types of edges, the switch to bold and solid edges instead of solid and dashed edges has increased clarity.

~ Easier problems are now grouped at the beginning of each exercise section, usable as warm-ups. Statements of some exercises have been clarified.

~ In addition to hints accompanying the exercise statements, there is now an appendix of supplemental hints.

~ For easier access, terms being defined are in bold type, and the vast majority of them appear in Definition items.

~ For easier access, the glossary of notation has been placed on the inside covers.

~ Material involving Eulerian circuits, digraphs, and Turan's Theorem has been relocated to facilitate more efficient learning.

~ Chapters 6 and 7 have been switched to introduce the idea ofplanarity earlier, and the section on complexity has become an appendix.

~ The glossary has been improved to eliminate errors and to emphasize items more directly related to the text.

Features

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").