Advanced Graph Theory and Combinatorics (eBook)

(Autor)

eBook Download: EPUB
2016 | 1. Auflage
296 Seiten
John Wiley & Sons (Verlag)
978-1-119-05864-9 (ISBN)

Lese- und Medienproben

Advanced Graph Theory and Combinatorics - Michel Rigo
Systemvoraussetzungen
139,99 inkl. MwSt
  • Download sofort lieferbar
  • Zahlungsarten anzeigen
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.

Michel RIGO, Full professor, University of Liège, Department of Math., Belgium.

Foreword ix

Introduction xi

Chapter 1. A First Encounter with Graphs 1

1.1. A few definitions 1

1.1.1. Directed graphs 1

1.1.2. Unoriented graphs 9

1.2. Paths and connected components 14

1.2.1. Connected components 16

1.2.2. Stronger notions of connectivity 18

1.3. Eulerian graphs 23

1.4. Defining Hamiltonian graphs 25

1.5. Distance and shortest path 27

1.6. A few applications 30

1.7. Comments 35

1.8. Exercises 37

Chapter 2. A Glimpse at Complexity Theory 43

2.1. Some complexity classes 43

2.2. Polynomial reductions 46

2.3. More hard problems in graph theory 49

Chapter 3. Hamiltonian Graphs 53

3.1. A necessary condition 53

3.2. A theorem of Dirac 55

3.3. A theorem of Ore and the closure of a graph 56

3.4. Chvátal's condition on degrees 59

3.5. Partition of Kn into Hamiltonian circuits 62

3.6. De Bruijn graphs and magic tricks 65

3.7. Exercises 68

Chapter 4. Topological Sort and Graph Traversals 69

4.1. Trees 69

4.2. Acyclic graphs 79

4.3. Exercises 82

Chapter 5. Building New Graphs from Old Ones 85

5.1. Some natural transformations 85

5.2. Products 90

5.3. Quotients 92

5.4. Counting spanning trees 93

5.5. Unraveling 94

5.6. Exercises 96

Chapter 6. Planar Graphs 99

6.1. Formal definitions 99

6.2. Euler's formula 104

6.3. Steinitz' theorem 109

6.4. About the four-color theorem 113

6.5. The five-color theorem 115

6.6. From Kuratowski's theorem to minors 120

6.7. Exercises 123

Chapter 7. Colorings 127

7.1. Homomorphisms of graphs 127

7.2. A digression: isomorphisms and labeled vertices 131

7.3. Link with colorings 134

7.4. Chromatic number and chromatic polynomial 136

7.5. Ramsey numbers 140

7.6. Exercises 147

Chapter 8. Algebraic Graph Theory 151

8.1. Prerequisites 151

8.2. Adjacency matrix 154

8.3. Playing with linear recurrences 160

8.4. Interpretation of the coefficients 168

8.5. A theorem of Hoffman 169

8.6. Counting directed spanning trees 172

8.7. Comments 177

8.8. Exercises 178

Chapter 9. Perron-Frobenius Theory 183

9.1. Primitive graphs and Perron's theorem 183

9.2. Irreducible graphs 188

9.3. Applications 190

9.4. Asymptotic properties 195

9.4.1. Canonical form 196

9.4.2. Graphs with primitive components 197

9.4.3. Structure of connected graphs 206

9.4.4. Period and the Perron-Frobenius theorem 214

9.4.5. Concluding examples 218

9.5. The case of polynomial growth 224

9.6. Exercises 231

Chapter 10. Google's Page Rank 233

10.1. Defining the Google matrix 238

10.2. Harvesting the primitivity of the Google matrix 241

10.3. Computation 246

10.4. Probabilistic interpretation 246

10.5. Dependence on the parameter alpha 247

10.6. Comments 248

Bibliography 249

Index 263

Erscheint lt. Verlag 22.11.2016
Sprache englisch
Themenwelt Mathematik / Informatik Informatik Theorie / Studium
Mathematik / Informatik Mathematik Angewandte Mathematik
Mathematik / Informatik Mathematik Graphentheorie
Schlagworte Computational / Numerical Methods • linear algebra • Lineare Algebra • Maschinenbau • Mathematical Modeling • Mathematics • Mathematik • Mathematische Modellierung • mechanical engineering • Rechnergestützte / Numerische Verfahren im Maschinenbau • Rechnergestützte / Numerische Verfahren im Maschinenbau
ISBN-10 1-119-05864-3 / 1119058643
ISBN-13 978-1-119-05864-9 / 9781119058649
Haben Sie eine Frage zum Produkt?
EPUBEPUB (Adobe DRM)
Größe: 7,0 MB

Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM

Dateiformat: EPUB (Electronic Publication)
EPUB ist ein offener Standard für eBooks und eignet sich besonders zur Darstellung von Belle­tristik und Sach­büchern. Der Fließ­text wird dynamisch an die Display- und Schrift­größe ange­passt. Auch für mobile Lese­geräte ist EPUB daher gut geeignet.

Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine Adobe-ID und die Software Adobe Digital Editions (kostenlos). Von der Benutzung der OverDrive Media Console raten wir Ihnen ab. Erfahrungsgemäß treten hier gehäuft Probleme mit dem Adobe DRM auf.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine Adobe-ID sowie eine kostenlose App.
Geräteliste und zusätzliche Hinweise

Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.

Mehr entdecken
aus dem Bereich
Discover tactics to decrease churn and expand revenue

von Jeff Mar; Peter Armaly

eBook Download (2024)
Packt Publishing (Verlag)
25,19