第1页 / 共654页
第2页 / 共654页
第3页 / 共654页
第4页 / 共654页
第5页 / 共654页
第6页 / 共654页
第7页 / 共654页
第8页 / 共654页
Graph Theory - Bondy J.A. Murty U.S.R编的完美打印版.pdf
Preface
Contents
1 Graphs
2 Subgraphs
3 Connected Graphs
4 Trees
5 Nonseparable Graphs
6 Tree-Search Algorithms
7 Flows in Networks
8 Complexity of Algorithms
9 Connectivity
10 Planar Graphs
11 The Four-Colour Problem
12 Stable Sets and Cliques
13 The Probabilistic Method
14 Vertex Colourings
15 Colourings of Maps
16 Matchings
17 Edge Colourings
18 Hamilton Cycles
19 Coverings and Packings in Directed Graphs
20 Electrical Networks
21 Integer Flows and Coverings
Appendix
Unsolved Problems
References
General Mathematical Notation
Graph Parameters
Operations and Relations
Families of Graphs
Structures
Other Notation
Index
Graduate Texts in Mathematics 244
Editorial Board
S. Axler K.A. Ribet
Graduate Texts in Mathematics
1 TAKEUTI/ZARING. Introduction to Axiomatic
38 GRAUERT/FRITZSCHE. Several Complex
25 HEWITT/STROMBERG. Real and Abstract
Mechanics. 2nd ed.
30 JACOBSON. Lectures in Abstract Algebra I.
66 WATERHOUSE. Introduction to Affine Group
14 GOLUBITSKY/GUILLEMIN. Stable Mappings
2nd ed.
Set Theory. 2nd ed.
2 OXTOBY. Measure and Category. 2nd ed.
3 SCHAEFER. Topological Vector Spaces. 2nd ed.
4 HILTON/STAMMBACH. A Course in
Homological Algebra. 2nd ed.
5 MAC LANE. Categories for the Working
Mathematician. 2nd ed.
6 HUGHES/PIPER. Projective Planes.
7 J.-P. Serre. A Course in Arithmetic.
8 TAKEUTI/ZARING. Axiomatic Set Theory.
9 HUMPHREYS. Introduction to Lie Algebras and
Representation Theory.
10 COHEN. A Course in Simple Homotopy Theory.
11 CONWAY. Functions of One Complex
Variable I. 2nd ed.
12 BEALS. Advanced Mathematical Analysis.
13 ANDERSON/FULLER. Rings and Categories of
Modules. 2nd ed.
15 BERBERIAN. Lectures in Functional Analysis
and Their Singularities.
and Operator Theory.
16 WINTER. The Structure of Fields.
17 ROSENBLATT. Random Processes. 2nd ed.
18 HALMOS. Measure Theory.
19 HALMOS. A Hilbert Space Problem Book.
2nd ed.
20 HUSEMOLLER. Fibre Bundles. 3rd ed.
21 HUMPHREYS. Linear Algebraic Groups.
22 BARNES/MACK. An Algebraic Introduction to
Mathematical Logic.
23 GREUB. Linear Algebra. 4th ed.
24 HOLMES. Geometric Functional Analysis and
Its Applications.
Analysis.
26 MANES. Algebraic Theories.
27 KELLEY. General Topology.
28 ZARISKI/SAMUEL. Commutative Algebra.
29 ZARISKI/SAMUEL. Commutative Algebra.
Vol. I.
Vol. II.
Basic Concepts.
31 JACOBSON. Lectures in Abstract
Algebra II. Linear Algebra.
32 JACOBSON. Lectures in Abstract Algebra III.
Theory of Fields and Galois Theory.
33 HIRSCH. Differential Topology.
34 SPITZER. Principles of Random Walk. 2nd ed.
35 ALEXANDER/WERMER. Several Complex
Variables and Banach Algebras. 3rd ed.
36 KELLEY/NAMIOKA et al. Linear Topological
Spaces.
37 MONK. Mathematical Logic.
Variables.
39 ARVESON. An Invitation to C-Algebras.
40 KEMENY/SNELL/KNAPP. Denumerable Markov
Chains. 2nd ed.
41 APOSTOL. Modular Functions and Dirichlet
Series in Number Theory. 2nd ed.
42 J.-P. SERRE. Linear Representations of Finite
Groups.
Functions.
43 GILLMAN/JERISON. Rings of Continuous
44 KENDIG. Elementary Algebraic Geometry.
45 LO `Eve. Probability Theory I. 4th ed.
46 LO `Eve. Probability Theory II. 4th ed.
47 MOISE. Geometric Topology in Dimensions
2 and 3.
48 SACHS/WU. General Relativity for
Mathematicians.
49 GRUENBERG/WEIR. Linear Geometry.
50 EDWARDS. Fermat’s Last Theorem.
51 KLINGENBERG. A Course in Differential
Geometry.
52 HARTSHORNE. Algebraic Geometry.
53 MANIN. A Course in Mathematical Logic.
54 GRAVER/WATKINS. Combinatorics with
Emphasis on the Theory of Graphs.
55 BROWN/PEARCY. Introduction to Operator
Theory I: Elements of Functional Analysis.
56 MASSEY. Algebraic Topology: An Introduction.
57 CROWELL/FOX. Introduction to Knot Theory.
58 KOBLITZ. p-adic Numbers, p-adic Analysis,
and Zeta-Functions. 2nd ed.
59 LANG. Cyclotomic Fields.
60 ARNOLD. Mathematical Methods in Classical
61 WHITEHEAD. Elements of Homotopy Theory.
62 KARGAPOLOV/MERIZJAKOV. Fundamentals of
the Theory of Groups.
63 BOLLOBAS. Graph Theory.
64 EDWARDS. Fourier Series. Vol. I. 2nd ed.
65 WELLS. Differential Analysis on Complex
Manifolds. 2nd ed.
67 SERRE. Local Fields.
68 WEIDMANN. Linear Operators in Hilbert
Schemes.
Spaces.
69 LANG. Cyclotomic Fields II.
70 MASSEY. Singular Homology Theory.
71 FARKAS/KRA. Riemann Surfaces. 2nd ed.
72 STILLWELL. Classical Topology and
Combinatorial Group Theory. 2nd ed.
73 HUNGERFORD. Algebra.
74 DAVENPORT. Multiplicative Number Theory.
3rd ed.
(continued after index)
J.A. Bondy U.S.R. Murty
Graph Theory
J.A. Bondy, PhD
Universit´e Claude-Bernard Lyon 1
Domaine de Gerland
50 Avenue Tony Garnier
69366 Lyon Cedex 07
France
Editorial Board
S. Axler
Mathematics Department
San Francisco State University
San Francisco, CA 94132
USA
U.S.R. Murty, PhD
Mathematics Faculty
University of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada
N2L 3G1
K.A. Ribet
Mathematics Department
University of California, Berkeley
Berkeley, CA 94720-3840
USA
Graduate Texts in Mathematics series ISSN: 0072-5285
ISBN: 978-1-84628-969-9
DOI: 10.1007/978-1-84628-970-5
e-ISBN: 978-1-84628-970-5
Library of Congress Control Number: 2007940370
Mathematics Subject Classification (2000): 05C; 68R10
c J.A. Bondy & U.S.R. Murty 2008
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted
under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or trans-
mitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of
reprographic reproduction in accordance with the terms of licenses issued by the Copyright Licensing Agency.
Enquiries concerning reproduction outside those terms should be sent to the publishers.
The use of registered name, trademarks, etc. in this publication does not imply, even in the absence of a specific
statement, that such names are exempt from the relevant laws and regulations and therefore free for general use.
The publisher makes no representation, express or implied, with regard to the accuracy of the information
contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that
may be made.
Printed on acid-free paper
9 8 7 6 5 4 3 2 1
springer.com
Dedication
To the memory of our dear friends and mentors
Claude Berge
Paul Erd˝os
Bill Tutte
Preface
For more than one hundred years, the development of graph theory was inspired
and guided mainly by the Four-Colour Conjecture. The resolution of the conjecture
by K. Appel and W. Haken in 1976, the year in which our first book Graph Theory
with Applications appeared, marked a turning point in its history. Since then, the
subject has experienced explosive growth, due in large measure to its role as an
essential structure underpinning modern applied mathematics. Computer science
and combinatorial optimization, in particular, draw upon and contribute to the
development of the theory of graphs. Moreover, in a world where communication
is of prime importance, the versatility of graphs makes them indispensable tools
in the design and analysis of communication networks.
Building on the foundations laid by Claude Berge, Paul Erd˝os, Bill Tutte, and
others, a new generation of graph-theorists has enriched and transformed the sub-
ject by developing powerful new techniques, many borrowed from other areas of
mathematics. These have led, in particular, to the resolution of several longstand-
ing conjectures, including Berge’s Strong Perfect Graph Conjecture and Kneser’s
Conjecture, both on colourings, and Gallai’s Conjecture on cycle coverings.
One of the dramatic developments over the past thirty years has been the
creation of the theory of graph minors by G. N. Robertson and P. D. Seymour. In
a long series of deep papers, they have revolutionized graph theory by introducing
an original and incisive way of viewing graphical structure. Developed to attack
a celebrated conjecture of K. Wagner, their theory gives increased prominence to
embeddings of graphs in surfaces. It has led also to polynomial-time algorithms
for solving a variety of hitherto intractable problems, such as that of finding a
collection of pairwise-disjoint paths between prescribed pairs of vertices.
A technique which has met with spectacular success is the probabilistic method.
Introduced in the 1940s by Erd˝os, in association with fellow Hungarians A. R´enyi
and P. Tur´an, this powerful yet versatile tool is being employed with ever-increasing
frequency and sophistication to establish the existence or nonexistence of graphs,
and other combinatorial structures, with specified properties.
VIII
Preface
As remarked above, the growth of graph theory has been due in large measure
to its essential role in the applied sciences. In particular, the quest for efficient
algorithms has fuelled much research into the structure of graphs. The importance
of spanning trees of various special types, such as breadth-first and depth-first
trees, has become evident, and tree decompositions of graphs are a central ingre-
dient in the theory of graph minors. Algorithmic graph theory borrows tools from
a number of disciplines, including geometry and probability theory. The discovery
by S. Cook in the early 1970s of the existence of the extensive class of seemingly
intractable NP-complete problems has led to the search for efficient approxima-
tion algorithms, the goal being to obtain a good approximation to the true value.
Here again, probabilistic methods prove to be indispensable.
The links between graph theory and other branches of mathematics are becom-
ing increasingly strong, an indication of the growing maturity of the subject. We
have already noted certain connections with topology, geometry, and probability.
Algebraic, analytic, and number-theoretic tools are also being employed to consid-
erable effect. Conversely, graph-theoretical methods are being applied more and
more in other areas of mathematics. A notable example is Szemer´edi’s regularity
lemma. Developed to solve a conjecture of Erd˝os and Tur´an, it has become an
essential tool in additive number theory, as well as in extremal conbinatorics. An
extensive account of this interplay can be found in the two-volume Handbook of
Combinatorics.
It should be evident from the above remarks that graph theory is a flour-
ishing discipline. It contains a body of beautiful and powerful theorems of wide
applicability. The remarkable growth of the subject is reflected in the wealth of
books and monographs now available. In addition to the Handbook of Combina-
torics, much of which is devoted to graph theory, and the three-volume treatise on
combinatorial optimization by Schrijver (2003), destined to become a classic, one
can find monographs on colouring by Jensen and Toft (1995), on flows by Zhang
(1997), on matching by Lov´asz and Plummer (1986), on extremal graph theory by
Bollob´as (1978), on random graphs by Bollob´as (2001) and Janson et al. (2000),
on probabilistic methods by Alon and Spencer (2000) and Molloy and Reed (1998),
on topological graph theory by Mohar and Thomassen (2001), on algebraic graph
theory by Biggs (1993), and on digraphs by Bang-Jensen and Gutin (2001), as
well as a good choice of textbooks. Another sign is the significant number of new
journals dedicated to graph theory.
The present project began with the intention of simply making minor revisions
to our earlier book. However, we soon came to the realization that the changing
face of the subject called for a total reorganization and enhancement of its con-
tents. As with Graph Theory with Applications, our primary aim here is to present
a coherent introduction to the subject, suitable as a textbook for advanced under-
graduate and beginning graduate students in mathematics and computer science.
For pedagogical reasons, we have concentrated on topics which can be covered
satisfactorily in a course. The most conspicuous omission is the theory of graph
minors, which we only touch upon, it being too complex to be accorded an adequate
treatment. We have maintained as far as possible the terminology and notation of
our earlier book, which are now generally accepted.
Preface
IX
Particular care has been taken to provide a systematic treatment of the theory
of graphs without sacrificing its intuitive and aesthetic appeal. Commonly used
proof techniques are described and illustrated. Many of these are to be found in
insets, whereas others, such as search trees, network flows, the regularity lemma
and the local lemma, are the topics of entire sections or chapters. The exercises,
of varying levels of difficulty, have been designed so as to help the reader master
these techniques and to reinforce his or her grasp of the material. Those exercises
which are needed for an understanding of the text are indicated by a star. The
more challenging exercises are separated from the easier ones by a dividing line.
A second objective of the book is to serve as an introduction to research in
graph theory. To this end, sections on more advanced topics are included, and a
number of interesting and challenging open problems are highlighted and discussed
in some detail. These and many more are listed in an appendix.
Despite this more advanced material, the book has been organized in such a way
that an introductory course on graph theory may be based on the first few sections
of selected chapters. Like number theory, graph theory is conceptually simple, yet
gives rise to challenging unsolved problems. Like geometry, it is visually pleasing.
These two aspects, along with its diverse applications, make graph theory an ideal
subject for inclusion in mathematical curricula.
We have sought to convey the aesthetic appeal of graph theory by illustrating
the text with many interesting graphs — a full list can be found in the index.
The cover design, taken from Chapter 10, depicts simultaneous embeddings on the
projective plane of K6 and its dual, the Petersen graph.
A Web page for the book is available at
http://blogs.springer.com/bondyandmurty
The reader will find there hints to selected exercises, background to open problems,
other supplementary material, and an inevitable list of errata. For instructors
wishing to use the book as the basis for a course, suggestions are provided as to
an appropriate selection of topics, depending on the intended audience.
We are indebted to many friends and colleagues for their interest in and
help with this project. Tommy Jensen deserves a special word of thanks. He
read through the entire manuscript, provided numerous unfailingly pertinent com-
ments, simplified and clarified several proofs, corrected many technical errors and
linguistic infelicities, and made valuable suggestions. Others who went through
and commented on parts of the book include Noga Alon, Roland Assous, Xavier
Buchwalder, Genghua Fan, Fr´ed´eric Havet, Bill Jackson, Stephen Locke, Zsolt
Tuza, and two anonymous readers. We were most fortunate to benefit in this way
from their excellent knowledge and taste.
Colleagues who offered advice or supplied exercises, problems, and other help-
ful material include Michael Albertson, Marcelo de Carvalho, Joseph Cheriyan,
Roger Entringer, Herbert Fleischner, Richard Gibbs, Luis Goddyn, Alexander
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
