139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Advanced Graph Theory focuses on some of the main notions arising in graph theory with an emphasis from the very start of the book on the possible applications of the theory and the fruitful links existing with linear algebra. The second part of the book covers basic material related to linear recurrence relations with application to counting and the asymptotic estimate of the rate of growth of a sequence satisfying a recurrence relation.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 438
Veröffentlichungsjahr: 2016
Ähnliche
Table of Contents
Cover
Dedication
Title
Copyright
Foreword
Introduction
1 A First Encounter with Graphs
1.1. A few definitions
1.2. Paths and connected components
1.3. Eulerian graphs
1.4. Defining Hamiltonian graphs
1.5. Distance and shortest path
1.6. A few applications
1.7. Comments
1.8. Exercises
2 A Glimpse at Complexity Theory
2.1. Some complexity classes
2.2. Polynomial reductions
2.3. More hard problems in graph theory
3 Hamiltonian Graphs
3.1. A necessary condition
3.2. A theorem of Dirac
3.3. A theorem of Ore and the closure of a graph
3.4. Chvátal’s condition on degrees
3.5. Partition of
K
n
into Hamiltonian circuits
3.6. De Bruijn graphs and magic tricks
3.7. Exercises
4 Topological Sort and Graph Traversals
4.1. Trees
4.2. Acyclic graphs
4.3. Exercises
5 Building New Graphs from Old Ones
5.1. Some natural transformations
5.2. Products
5.3. Quotients
5.4. Counting spanning trees
5.5. Unraveling
5.6. Exercises
6 Planar Graphs
6.1. Formal definitions
6.2. Euler’s formula
6.3. Steinitz’ theorem
6.4. About the four-color theorem
6.5. The five-color theorem
6.6. From Kuratowski’s theorem to minors
6.7. Exercises
7 Colorings
7.1. Homomorphisms of graphs
7.2. A digression: isomorphisms and labeled vertices
7.3. Link with colorings
7.4. Chromatic number and chromatic polynomial
7.5. Ramsey numbers
7.6. Exercises
8 Algebraic Graph Theory
8.1. Prerequisites
8.2. Adjacency matrix
8.3. Playing with linear recurrences
8.4. Interpretation of the coefficients
8.5. A theorem of Hoffman
8.6. Counting directed spanning trees
8.7. Comments
8.8. Exercises
9 Perron–Frobenius Theory
9.1. Primitive graphs and Perron’s theorem
9.2. Irreducible graphs
9.3. Applications
9.4. Asymptotic properties
9.5. The case of polynomial growth
9.6. Exercises
10 Google’s Page Rank
10.1. Defining the Google matrix
10.2. Harvesting the primitivity of the Google matrix
10.3. Computation
10.4. Probabilistic interpretation
10.5. Dependence on the parameter
α
10.6. Comments
Bibliography
Index
End User Licence Agreement
List of Tables
1 A First Encounter with Graphs
Table 1.1.
An adjacency list
Table 1.2.
Algorithm to compute
succ
∗
(
v
)
Table 1.3.
Fleury’s algorithm [FLE 83]
Table 1.4.
Dijkstra’s algorithm
Table 1.5.
In bold face is indicated the choice made at line 8
Table 1.6.
Roy-Warshall algorithm for connectivity
3 Hamiltonian Graphs
Table 3.1.
A de Bruijn “chain”
4 Topological Sort and Graph Traversals
Table 4.1.
Algorithm returning a spanning tree of G
Table 4.2.
Depth first search of T starting with v
1
Table 4.3.
Algorithm determining whether G has a cycle
6 Planar Graphs
Table 6.1.
The five platonic solids
Table 6.2.
The first few values of c
g
7 Colorings
Table 7.1.
Number of edge-colorings of K
n
10 Google’s Page Rank
Table 10.1.
Needed iterations depending on the chosen α
Table 10.2.
Some powers of the Google matrix
Table 10.3.
The matrix encoding the soccer 2009–2010 season
Table 10.4.
Comparing sport ranking with PageRank
Table 10.5.
Changing the weights changes the ranking
Landmarks
Cover
Table of Contents
Begin Reading
Pages
C1
ii
iii
iv
v
ix
xi
xii
xiii
xiv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
85
86
87
88
89
90
91
92
93
94
95
96
97
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
G1
G2
G3
G4
G5
G6
G7
To Christelle, Aurore and Maxime
Series Editor
Valérie Berthé
Advanced Graph Theory and Combinatorics
Michel Rigo
First published 2016 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
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 transmitted, 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 and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK
www.iste.co.uk
John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA
www.wiley.com
© ISTE Ltd 2016
The rights of Michel Rigo to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2016953238
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-84821-616-7
Foreword
The book content reflects the (good) taste of the author for solid mathematical concepts and results that have exciting practical applications. It is an excellent textbook that should appeal to students and instructors for its very clear presentation of both classical and more recent concepts in graph theory.
Vincent BLONDEL
Professor of Applied Mathematics, University of LouvainSeptember 2016
Introduction
This book is a result of lecture notes from a graph theory course taught at the University of Liège since 2005. Through the years, this course evolved and lectures were given at different levels ranging from second-year undergraduates in mathematics to students in computer science entering master’s studies. It was therefore quite challenging to find a suitable title for this book.
Advanced or not so advanced material?
I hope that the reader will not feel cheated by the title (which is always tricky to choose). In some aspects, the material is rather elementary: we will start from scratch and present basic results on graphs such as connectedness or Eulerian graphs. In the second part of the book, we will analyze in great detail the strongly connected components of a digraph and make use of Perron–Frobenius theory and formal power series to estimate asymptotics on the number of walks of a given length between two vertices. Topics with an algebraic or a combinatorial flavor such as Ramsey numbers, introduction to Robertson–Seymour theorem or PageRank can be considered as more advanced.
In the history of mathematics, we often mention the seven bridges of Königsberg problem as the very first problem in graph theory. It was studied by the famous mathematician L. Euler in 1736. It took two centuries to develop and build a complete theory from a few scattered results. Probably the first book on graphs is Theorie der endlichen und unendlichen Graphen [KÖN 90] written by the Hungarian mathematician D. König in 1936, a student of J. Kürschák and H. Minkowski. In the middle of the 20th Century, graph theory matured into a well-defined branch of discrete mathematics and combinatorics. We observe many mathematicians turning their attention to graph theory with books by C. Berge, N. Biggs, P. Erdős, C. Kuratowski, W. T. Tutte, K. Wagner, etc. We have seen an important growth during the past decades in combinatorics because of the particular interactions existing with optimization, randomized algorithms, dynamical programming, ergodic or number theory, theoretical computer science, computational geometry, molecular biology, etc. On MathSciNet, if you look for research papers with a Primary Mathematics Subject Classification equal to 05C (which stands for graph theory and is divided into 38 subfields ranging from planar graphs to connectivity, random walks or hypergraphs), then we find for the period 2011–2015 between 3, 300 and 3, 700 papers published every single year.
In less than a century, many scientists and entrepreneurs have seen the importance of graph theory in real-life applications. In a recent issue of Wired magazine (March 2014), we can read an article entitled Is graph theory a key to understanding big data? by R. Marsten. Let us quote his conclusion: “The data that we have today, and often the ways we look at data, are already steeped in the theory of graphs. In the future, our ability to understand data with graphs will take us beyond searching for an answer. Creating and analyzing graphs will bring us to answers automatically”. Later, in the same magazine (May 2014), E. Eifrem wrote: “We’re all well aware of how Facebook and Twitter have used the social graph to dominate their markets, and how Facebook and Google are now using their Graph Search and Knowledge Graph, respectively, to gear up for the next wave of hyper-accurate and hyper-personal recommendations, but graphs are becoming very widely deployed in a host of other industries”.
This book reflects the tastes of the author but also includes some important applications such as Google’s PageRank. It is only assumed that the reader has a working knowledge of linear algebra. Nevertheless, all the definitions and important results are given for the sake of completeness. The aim of the book is to provide the reader with the necessary theoretical background to tackle new problems or to easily understand new concepts in graph theory. Algorithms and complexity theory occupy a very small portion of the book (mostly in the first chapters).
This book, others and inspiration
Many other books on graphs do exist and the reader should not limit himself or herself to a single source. The Internet is also a formidable resource. Even if we have to be cautious when looking for information on the Web, Wikipedia contains a wealth of relevant information (but keep a critical eye). The present book starts with some unavoidable general material, then moves on to some particular topics with a combinatorial flavor. Powers of the adjacency matrix and Perron theory have a predominant role. The reader could probably start with this book and then move to [BRU 11] as a good companion to get a deeper knowledge of the links between linear algebra and graphs. See also [BAP 14] or the classical [GOD 01] in algebraic graph theory. Similarly, a comprehensive presentation of PageRank techniques can be found in [LAN 06]. The authors of that book, A. Langville and C. D. Meyer, also specialized in ranking techniques (see [LAN 12]). Another general reference discussing partially the same topics as here – and I do hope, with the same philosophy – is by R. Diestel where much more material and a particular emphasis on infinite graphs may be found. The present book is smaller and is thus well suited for readers who do not want to spend too much time on a specialized topic.
Having given a graph theory course for more than 10 years, I’m probably unconsciously tempted to take ownership of the proofs that I found somewhere else. It is no easy task to cite and give credits to all the sources that inspired me in this process. Let me mention [BIG 93] for algebraic aspects and chromatic polynomial, [TUT 01] for its first chapters and [ORE 90] for planar graphs and his proof of the 5-color theorem. I should also mention [BOL 98] (with an impressive collection of exercises) and [BER 89]. Finally, I remember that projects available on the Web and run by D. Arnold (College of Redwoods) were inspiring.
Practical organization
For a one-semester course, here is the time I usually devote to selected topics with 15 lectures of 90 min. Moreover, sessions for exercises take the same amount of time. The book contains extra material and more than 115 exercises:
– digraphs, paths, connected components (
sections 1.1
and
1.2
);
– Eulerian graphs, distance and shortest path (
sections 1.3
and
1.5
);
– introduction to Hamiltonicity, applications (
sections 1.4
and
1.6
);
– trees (
section 4.1
);
– homomorphisms, group of automorphisms (
sections 7.1
and
7.2
);
– Hamiltonian graphs (
sections 3.1
–
3.4
);
– topological sort (
Chapter 4
);
– adjacency matrix, counting walks (
sections 8.2
and
8.3
);
– primitivity, Perron’s theorem and asymptotics (
sections 9.1
and
9.4
);
– irreducibility and asymptotics (
sections 9.2
and
9.4
);
– applications of Perron–Frobenius theory (
section 9.3
);
– Google’s PageRank (
Chapter 10
);
– planar graphs and Euler’s formula (
sections 6.1
–
6.3
);
– colorings, the five-color theorem (
section 6.5
);
– Ramsey numbers (
section 7.4
).
Definitions are emphasized and the most important ones are written in bold face, so that definitions of recurrent notions can be found more easily. Labels of bibliographic entries are based on the first three letters of the last name of the first author and then the year of publication. In the bibliography, entries are sorted in alphabetical order using these labels.
I address special thanks to Émilie Charlier, Aline Parreau and Manon Stipulanti for their great feedback leading to some major improvements in this book. Of course, Valérie Berthé always plays a special role. I am very pleased to blame her (indeed, this adventure produced some pressure from time to time) for what this project finally looks like. She is always supportive and enthusiastic. I also thanks several colleagues: Benoît Donnet, Eric Duchêne, Fabien Durand, Narad Rampersad, Eric Rowland and Élise Vandomme for the valuable time they spent reading drafts of parts of this book. I will not forget Laurent Waxweiler who gave and prepared the very first exercise classes for my course. I also thank my many students along the years. Their questions, queries and enthusiasm allowed me to improve, over the time, the overall presentation and sequencing of this book.
Michel RIGOSeptember, 2016
