Graphes et algorithmes (4e éd.) (Coll. EDF R&D)

Les modèles et les algorithmes de graphes se sont imposés aujourd'hui dans de nombreuses disciplines, aussi bien dans les sciences de base (physique, chimie, biologie, sciences humaines, informatique théorique et algorithmique) que dans les sciences de l'ingénieur (automatique, optimisation de systèmes, économie et recherche opérationnelle, analyse de données, ingénierie des grands réseaux de communication de type internet). Cette nouvelle édition est la seule à offrir un panorama aussi complet de ces outils et de leurs plus récents développements.
Graphes et algorithmes rend compte de la puissance de modélisation procurée par les graphes, et de la disponibilité d'une vaste panoplie d'algorithmes opérationnels. Cette nouvelle édition développe les nombreux résultats, souvent fins, conduisant à la réduction de la complexité des algorithmes (flots, chemins, arbres), les nouvelles familles d'algorithmes approchés (ou métaheuristiques) en particulier ceux inspirés de la biologie (algorithmes génétiques, ou ceux imitant le comportement des colonies de fourmis), les algorithmes fondés sur des processus aléatoires (algorithmes itératifs aléatoires ou algorithmes gloutons aléatoires).
Proposant au lecteur environ 230 exercices et plus de 100 problèmes concrets modélisés, cette nouvelle édition s'est enrichie aussi d'une présentation plus aérée et de nombreuses références bibliographiques.
Graphes et algorithmes s'adresse à un large éventail de chercheurs et ingénieurs des laboratoires et bureaux d'études, et de futurs ingénieurs et étudiants en licence et master.

1. Généralités sur les graphes. Définitions et concepts de base. Matrices associées à un graphe. Connexité. Cycles et cocycles - Nombre cyclomatique. Quelques graphes particuliers. Les hypergraphes. Graphes aléatoires et connexité. 2. Le problème du plus court chemin. Définitions et exemples. Les algorithmes. Le problème central de l'ordonnancement. 3. Algèbres de chemins et dioïdes. L'algèbre du plus court chemin. Définitions et propriétés. Quelques exemples. Algorithmes généraux. Algèbres de chemins dans un graphe sans circuit. Un dioïde particulier. Les dioïdes à gauche et à droite. Généralisation des algèbres de chemins. Théorie des dioïdes et applications. 4. Arbres et arborescences. Arbres - Définitions et propriétés. Le problème de l'arbre de poids minimum. Arborescences. 5. Flots et réseaux de transport. Définitions et propriétés. Le problème du flot maximum dans un réseau de transport. Le problème du flot compatible - Théorème de compatibilité. Flots et connexité. Flots à coût minimum. 6. Flots avec multiplicateurs - Multiflots. Flots avec multiplicateurs. Problèmes de multiflots. 7. Couplages et b-couplages. Le problème du couplage maximum. Algorithme de recherche d'un couplage maximum. Couplage de poids maximum. Un algorithme pour le problème du couplage de poids maximum. b-Couplages - b-Couplages maximum et b-couplage de poids maximum. 8. Parcours eulériens et hamiltoniens. Cycles et chaînes eulériens. Le problème du "Postier chinois" (non orienté). Circuits et cycles hamiltoniens. 9. Matroïdes. Définitions et résultats fondamentaux. Dualité. Le problème du sous-ensemble indépendant de poids maximum : l'algorithme glouton. Intersection de matroïdes. Matroïdes avec conditions de parité et généralisations. Polymatroïdes. 10. Les problèmes difficiles de la classe NP. Réductions et relations d'équivalence entre problèmes. Partition et recouvrement d'un hypergraphe. Le problème du couplage d'un hypergraphe. Coloration d'un graphe et d'un hypergraphe. Le problème du sac à dos multidimensionnel. Les problèmes de coûts fixes et les fonctions d'ensemble. Les problèmes d'ordonnancement. Quelques autres problèmes concrets. Problèmes NP-complets et réductions entre problèmes. 11. Les algorithmes d'énumération par séparation, évaluation et propagation de contraintes. Un exemple d'exploration par séparation, évaluation et propagation. Les procédures d'exploration par séparation et évaluation. Deux exemples d'applications. Évaluation par défaut et pénalités. "ALICE". 12. Algorithmes approchés et métaheuristiques. Les algorithmes itératifs de voisinage. Les algorithmes gloutons. Les métaheuristiques inspirés de la biologie. Régularisation des coûts. Optimalité des algorithmes approchés. Annexe 1. Programmation linéaire. Annexe 2. Programmation linéaire en nombres entiers. Annexe 3. Relaxation lagrangienne et résolution du problème dual. Annexe 4. Programmation dynamique. Annexe 5. Les problèmes de ratio minimum. Index. (Exercices et références bibliogra­phiques en fin de chaque chapitre).