图论经典教材：GTM 244 - Bondy J.A.,Murty U.S.R. - Graph Theory

xz1988117-5236649-16359647748892324488.pdf-第1页.png

第1页 / 共655页

xz1988117-5236649-16359647748892324488.pdf-第2页.png

第2页 / 共655页

xz1988117-5236649-16359647748892324488.pdf-第3页.png

第3页 / 共655页

xz1988117-5236649-16359647748892324488.pdf-第4页.png

第4页 / 共655页

xz1988117-5236649-16359647748892324488.pdf-第5页.png

第5页 / 共655页

xz1988117-5236649-16359647748892324488.pdf-第6页.png

第6页 / 共655页

xz1988117-5236649-16359647748892324488.pdf-第7页.png

第7页 / 共655页

xz1988117-5236649-16359647748892324488.pdf-第8页.png

第8页 / 共655页

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 Afﬁne 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 Classiﬁcation (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 speciﬁc 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 ﬁrst 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 ﬁnding 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 speciﬁed 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 eﬃcient algorithms has fuelled much research into the structure of graphs. The importance of spanning trees of various special types, such as breadth-ﬁrst and depth-ﬁrst 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 eﬃcient 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 eﬀect. 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 ﬂour- ishing discipline. It contains a body of beautiful and powerful theorems of wide applicability. The remarkable growth of the subject is reﬂected 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 ﬁnd monographs on colouring by Jensen and Toft (1995), on ﬂows 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 signiﬁcant 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

资料库

图论经典教材：GTM 244 - Bondy J.A.,Murty U.S.R. - Graph Theory - Spring....pdf

相关推荐

课程资源

热门标签

最新资料