Cet ouvrage présente l’étude des principaux aspects de la théorie des graphes et de ses applications, en particulier celles relevant de l’optimisation combinatoire.
Il expose des sujets significatifs associés, tels que, par exemple, le problème de l’emploi du temps avec les colorations, l’affectation optimale avec les couplages, le « voyageur de commerce » avec les cycles hamiltoniens, etc.
Introduction
Chapitre 1. Généralités.
Chapitre 2. Arbres.
Chapitre 3. Colorations.
Chapitre 4. Graphes orientés.
Chapitre 5. Recherche arborescente.
Chapitre 6. Chemins optimaux.
Chapitre 7. Couplages.
Chapitre 8. Flots.
Chapitre 9. Tournées eulériennes.
Chapitre 10. Tournées hamiltonniennes.
Chapitre 11 Représentations planes.
Chapitre 12. Problèmes commentés.
Appendice. Algorithmes randomisés de graphes.
Annexe 1 : expression des algorithmes
Annexe 2 : bases de la théorie de la complexité