没有合适的资源？快使用搜索试试~ 我知道了~

首页Graph Theory III - Reinhard Diestel 图论经典教材 英文版 超清晰版 非扫描 完整书签

资源详情

资源评论

资源推荐

Reinhard Diestel

Graph Theory

Electronic Edition 2005

c

Springer-Verlag Heidelberg, New York 1997, 2000, 2005

This is an electronic version of the third (2005) edition of the above

Springer book, from their series Graduate Texts in Mathematics ,vol. 173.

The cross-references in the text and in the margins are active links: click

on them to be taken to the appropriate page.

The printed edition of this book can be ordered via

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/

where also errata, reviews etc. are posted.

Substantial discounts and free copies for lecturers are available for course

adoptions; see here

.

Preface

Almost two decades have passed since the appearance of those graph the-

ory texts that still set the agenda for most introductory courses taught

today. The canon created by those books has helped to identify some

main ﬁelds of study and research, and will doubtless continue to inﬂuence

the development of the discipline for some time to come.

Yetmuch has happened in those 20 years, in graph theory no less

than elsewhere: deep new theorems have been found, seemingly disparate

methods and results have become interrelated, entire new branches have

arisen. To name just a few such developments, one may think of how

the new notion of list colouring has bridged the gulf between invari-

ants such as average degree and chromatic number, how probabilistic

methods and the regularity lemma have pervaded extremal graph theory

and Ramsey theory, or how the entirely new ﬁeld of graph minors and

tree-decompositions has brought standard methods of surface topology

to bear on long-standing algorithmic graph problems.

Clearly, then, the time has come for a reappraisal: what are, today,

the essential areas, methods and results that should form the centre of

an introductory graph theory course aiming to equip its audience for the

most likely developments ahead?

Ihave tried in this book to oﬀer material for such a course. In

view of the increasing complexity and maturity of the subject, I have

broken with the tradition of attempting to cover both theory and appli-

cations: this book oﬀers an introduction to the theory of graphs as part

of (pure) mathematics; it contains neither explicit algorithms nor ‘real

world’ applications. My hope is that the potential for depth gained by

this restriction in scope will serve students of computer science as much

as their peers in mathematics: assuming that they prefer algorithms but

will beneﬁt from an encounter with pure mathematics of some kind, it

seems an ideal opportunity to look for this close to where their heart lies!

In the selection and presentation of material, I have tried to ac-

commodate two conﬂicting goals. On the one hand, I believe that an

viii Preface

introductory text should be lean and concentrate on the essential, so as

to oﬀer guidance to those new to the ﬁeld. As a graduate text, moreover,

it should get to the heart of the matter quickly: after all, the idea is to

convey at least an impression of the depth and methods of the subject.

On the other hand, it has been my particular concern to write with

suﬃcient detail to make the text enjoyable and easy to read: guiding

questions and ideas will be discussed explicitly, and all proofs presented

will be rigorous and complete.

Atypical chapter, therefore, begins with a brief discussion of what

are the guiding questions in the area it covers, continues with a succinct

account of its classic results (often with simpliﬁed proofs), and then

presents one or two deeper theorems that bring out the full ﬂavour of

that area. The proofs of these latter results are typically preceded by (or

interspersed with) an informal account of their main ideas, but are then

presented formally at the same level of detail as their simpler counter-

parts. I soon noticed that, as a consequence, some of those proofs came

out rather longer in print than seemed fair to their often beautifully

simple conception. I would hope, however, that even for the professional

reader the relatively detailed account of those proofs will at least help

to minimize reading time...

If desired, this text can be used for a lecture course with little or

no further preparation. The simplest way to do this would be to follow

the order of presentation, chapter by chapter: apart from two clearly

marked exceptions, any results used in the proof of others precede them

in the text.

Alternatively, a lecturer may wish to divide the material into an easy

basic course for one semester, and a more challenging follow-up course

for another. To help with the preparation of courses deviating from the

order of presentation, I have listed in the margin next to each proof the

reference numbers of those results that are used in that proof. These

references are given in round brackets: for example, a reference (4.1.2)

in the margin next to the proof of Theorem 4.3.2 indicates that Lemma

4.1.2 will be used in this proof. Correspondingly, in the margin next to

Lemma 4.1.2 there is a reference [ 4.3.2 ] (in square brackets) informing

the reader that this lemma will be used in the proof of Theorem 4.3.2.

Note that this system applies between diﬀerent sections only (of the same

or of diﬀerent chapters): the sections themselves are written as units and

best read in their order of presentation.

The mathematical prerequisites for this book, as for most graph

theory texts, are minimal: a ﬁrst grounding in linear algebra is assumed

for Chapter 1.9 and once in Chapter 5.5, some basic topological con-

cepts about the Euclidean plane and 3-space are used in Chapter 4, and

a previous ﬁrst encounter with elementary probability will help with

Chapter 11. (Even here, all that is assumed formally is the knowledge

of basic deﬁnitions: the few probabilistic tools used are developed in the

Preface ix

text.) There are two areas of graph theory which I ﬁnd both fascinat-

ing and important, especially from the perspective of pure mathematics

adopted here, but which are not covered in this book: these are algebraic

graph theory and inﬁnite graphs.

At the end of each chapter, there is a section with exercises and

another with bibliographical and historical notes. Many of the exercises

were chosen to complement the main narrative of the text: they illus-

trate new concepts, show how a new invariant relates to earlier ones,

or indicate ways in which a result stated in the text is best possible.

Particularly easy exercises are identiﬁed by the superscript

−

, the more

challenging ones carry a

+

. The notes are intended to guide the reader

on to further reading, in particular to any monographs or survey articles

on the theme of that chapter. They also oﬀer some historical and other

remarks on the material presented in the text.

Ends of proofs are marked by the symbol . Where this symbol is

found directly below a formal assertion, it means that the proof should

be clear after what has been said—a claim waiting to be veriﬁed! There

are also some deeper theorems which are stated, without proof, as back-

ground information: these can be identiﬁed by the absence of both proof

and .

Almost every book contains errors, and this one will hardly be an

exception. I shall try to post on the Web any corrections that become

necessary. The relevant site may change in time, but will always be

accessible via the following two addresses:

http://www.springer-ny.com/supplements/diestel/

http://www.springer.de/catalog/html-ﬁles/deutsch/math/3540609180.html

Please let me know about any errors you ﬁnd.

Little in a textbook is truly original: even the style of writing and

of presentation will invariably be inﬂuenced by examples. The book that

no doubt inﬂuenced me most is the classic GTM graph theory text by

Bollob´as: it was in the course recorded by this text that I learnt my ﬁrst

graph theory as a student. Anyone who knows this book well will feel

its inﬂuence here, despite all diﬀerences in contents and presentation.

I should like to thank all who gave so generously of their time,

knowledge and advice in connection with this book. I have beneﬁted

particularly from the help of N. Alon, G. Brightwell, R. Gillett, R. Halin,

M. Hintz, A. Huck, I. Leader, T. Luczak, W. Mader, V. R¨odl, A.D. Scott,

P.D. Seymour, G. Simonyi, M.

ˇ

Skoviera, R. Thomas, C. Thomassen and

P. Valtr. I am particularly grateful also to Tommy R. Jensen, who taught

me much about colouring and all I know about k-ﬂows, and who invested

immense amounts of diligence and energy in his proofreading of the pre-

liminary German version of this book.

March 1997 RD

x Preface

About the second edition

Naturally, I am delighted at having to write this addendum so soon after

this book came out in the summer of 1997. It is particularly gratifying

to hear that people are gradually adopting it not only for their personal

use but more and more also as a course text; this, after all, was my aim

when I wrote it, and my excuse for agonizing more over presentation

than I might otherwise have done.

There are two major changes. The last chapter on graph minors

now gives a complete proof of one of the major results of the Robertson-

Seymour theory, their theorem that excluding a graph as a minor bounds

the tree-width if and only if that graph is planar. This short proof did

not exist when I wrote the ﬁrst edition, which is why I then included a

short proof of the next best thing, the analogous result for path-width.

That theorem has now been dropped from Chapter 12. Another addition

in this chapter is that the tree-width duality theorem, Theorem 12.3.9,

now comes with a (short) proof too.

The second major change is the addition of a complete set of hints

for the exercises. These are largely Tommy Jensen’s work, and I am

grateful for the time he donated to this project. The aim of these hints

is to help those who use the book to study graph theory on their own,

but not to spoil the fun. The exercises, including hints, continue to be

intended for classroom use.

Apart from these two changes, there are a few additions. The most

noticable of these are the formal introduction of depth-ﬁrst search trees

in Section 1.5 (which has led to some simpliﬁcations in later proofs) and

an ingenious new proof of Menger’s theorem due to B¨ohme, G¨oring and

Harant (which has not otherwise been published).

Finally, there is a host of small simpliﬁcations and clariﬁcations

of arguments that I noticed as I taught from the book, or which were

pointed out to me by others. To all these I oﬀer my special thanks.

The Web site for the book has followed me to

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/

I expect this address to be stable for some time.

Once more, my thanks go to all who contributed to this second

edition by commenting on the ﬁrst—and I look forward to further com-

ments!

December 1999 RD

剩余421页未读，继续阅读

安全验证

文档复制为VIP权益，开通VIP直接复制

信息提交成功

## 评论3