Modern Graph Theory / by Béla Bollobás
(Graduate Texts in Mathematics ; 184)
データ種別 | 電子ブック |
---|---|
出版情報 | New York, NY : Springer New York : Imprint: Springer , 1998 |
本文言語 | 英語 |
大きさ | XIV, 394 p. 3 illus : online resource |
書誌詳細を非表示
内容注記 | I Fundamentals I.1 Definitions I.2 Paths, Cycles, and Trees I.3 Hamilton Cycles and Euler Circuits I.4 Planar Graphs I.5 An Application of Euler Trails to Algebra I.6 Exercises II Electrical Networks II.1 Graphs and Electrical Networks II.2 Squaring the Square II.3 Vector Spaces and Matrices Associated with Graphs II.4 Exercises II.5 Notes III Flows, Connectivity and Matching III.1 Flows in Directed Graphs III.2 Connectivity and Menger’s Theorem III.3 Matching III.4 Tutte’s 1-Factor Theorem III.5 Stable Matchings III.6 Exercises III.7 Notes IV Extremal Problems IV.1 Paths and Cycles IV.2 Complete Subgraphs IV.3 Hamilton Paths and Cycles W.4 The Structure of Graphs IV 5 Szemerédi’s Regularity Lemma IV 6 Simple Applications of Szemerédi’s Lemma IV.7 Exercises IV.8 Notes V Colouring V.1 Vertex Colouring V.2 Edge Colouring V.3 Graphs on Surfaces V.4 List Colouring V.5 Perfect Graphs V.6 Exercises V.7 Notes VI Ramsey Theory VI.1 The Fundamental Ramsey Theorems VI.2 Canonical Ramsey Theorems VI.3 Ramsey Theory For Graphs VI.4 Ramsey Theory for Integers VI.5 Subsequences VI.6 Exercises VI.7 Notes VII Random Graphs VII.1 The Basic Models-The Use of the Expectation VII.2 Simple Properties of Almost All Graphs VII.3 Almost Determined Variables-The Use of the Variance VII.4 Hamilton Cycles-The Use of Graph Theoretic Tools VII.5 The Phase Transition VII.6 Exercises VII.7 Notes VIII Graphs, Groups and Matrices VIII.1 Cayley and Schreier Diagrams VIII.2 The Adjacency Matrix and the Laplacian VIII.3 Strongly Regular Graphs VIII.4 Enumeration and Pólya’s Theorem VIII.5 Exercises IX Random Walks on Graphs IX.1 Electrical Networks Revisited IX.2 Electrical Networks and Random Walks IX.3 Hitting Times and Commute Times IX.4 Conductance and Rapid Mixing IX.5 Exercises IX.6 Notes X The Tutte Polynomial X.1 Basic Properties of the Tutte Polynomial X.2 The Universal Form of the Tutte Polynomial X.3 The Tutte Polynomial in Statistical Mechanics X.4 Special Values of the Tutte Polynomial X.5 A Spanning Tree Expansion of the Tutte Polynomial X.6 Polynomials of Knots and Links X.7 Exercises X.8 Notes Symbol Index Name Index |
---|---|
一般注記 | The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed account of newer topics, including Szemer'edi's Regularity Lemma and its use, Shelah's extension of the Hales-Jewett Theorem, the precise nature of the phase transition in a random graph process, the connection between electrical networks and random walks on graphs, and the Tutte polynomial and its cousins in knot theory. In no other branch of mathematics is it as vital to tackle and solve challenging exercises in order to master the subject. To this end, the book contains an unusually large number of well thought-out exercises: over 600 in total. Although some are straightforward, most of them are substantial, and others will stretch even the most able reader |
著者標目 | *Bollobás, Béla author SpringerLink (Online service) |
件 名 | LCSH:Mathematics LCSH:Algorithms LCSH:Computer science -- Mathematics 全ての件名で検索 LCSH:Combinatorics FREE:Mathematics FREE:Combinatorics FREE:Mathematics of Computing FREE:Algorithm Analysis and Problem Complexity |
分 類 | DC23:511.6 |
巻冊次 | ISBN:9781461206194 |
ISBN | 9781461206194 |
URL | http://dx.doi.org/10.1007/978-1-4612-0619-4 |
目次/あらすじ