Advanced graph theory and combinatorics

Advanced graph theory and combinatorics

Detalles Bibliográficos
Otros Autores: Rigo, Michel, author (author)
Formato: Libro electrónico
Idioma:Inglés
Publicado: London, England ; Hoboken, New Jersey : ISTE 2016.
Edición:1st ed
Colección:Computer engineering series (London, England)
Materias:
Graph theory.
Combinatorial analysis.
Ver en Biblioteca Universitat Ramon Llull:https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009849126106719
Tabla de Contenidos:
  • Intro
  • Table of Contents
  • 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 Kn 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.

Ejemplares similares