Théorie des graphes

Couverture Page de titre Avant-propos Notations Chapitre 1. Des points et des lignes 1. Généralités 2. Isomorphisme de graphes 3. Degrés Chapitre 2. Algorithmes 1. Exemple 1 : l'algorithme Énigme 2. Exemple 2 : l'algorithme Parité 3. Exemple 3 : l'algorithme PGCD 4. Exemple 4 : l'algorithme ChampDeConnaissances 5. Algorithmes et classification de problèmes Chapitre 3. Connexité. Chaînes et cycles 1. Leçon de choses 2. Chaînes, cycles et parcours 3. Composantes connexes 4. Graphes connexes 5. Quelques propriétés 6. Pour aller plus loin Chapitre 4. Calculs de distances 1. Deux problèmes 2. Distance dans les graphes 3. L'algorithme de Dijkstra Chapitre 5. Arbres 1. Sécuriser des galeries 2. Arbres 3. Arbres recouvrants de coût minimum Chapitre 6. Colorations 1. Quelques problèmes 2. Coloration des sommets d'un graphe 3. Coloration des arêtes 4. Des couleurs pour partitionner 5. Des thèmes célèbres Chapitre 7. Parcours eulériens, cycles hamiltoniens 1. Quelques problèmes 2. Graphes et parcours eulériens 3. Graphes et cycles hamiltoniens 4. Annexe : article de L. Euler Chapitre 8. Couplages 1. Quelques problèmes 2. Couplages 3. Couplages et couvertures dans les graphes bipartis Chapitre 9. Graphes planaires 1. Problèmes et leçon de choses 2. La formule d'Euler 3. Coloration de graphes planaires 4. Le théorème de la galerie d'art 5. Pour aller plus loin: une caractérisation des graphes planaires Lectures Table des figures Index