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