Graphes et applications

Crédit : 3 ECTS
Langue du cours : anglais

Cet enseignement vise à montrer la richesse des concepts et outils issus de la théorie des graphes pour la modélisation et la résolution de nombreux problèmes concrets. Outre l’étude d’algorithmes et de leurs fondements théoriques, on montrera comment les concepts issus des graphes permettent de modéliser, de façon plus ou moins directe, certaines situations concrètes en les ramenant par exemple à un des problèmes classiques ou à un problème voisin. Concepts de base de théorie des graphes,
Etude de problèmes classiques de couplage, couverture, stable
Différents problèmes de flot
Problèmes de coloration
Applications

R. Ahuja, T. Magnanti and J. Orlin. Networks Flows, Theory, Algorithms, Applications. Prentice Hall, Englewood Cliffs, New Jersey (1993).
M. Gondran et M. Minoux. Graphes et algorithmes, Eyrolles, 2009, 4e édition.
L. Lovasz, M. D. Plummer, Matching Theory, Elsevier Science Ltd, 1986



Année universitaire 2019 - 2020 - Fiche modifiée le : 04-06-2019 (10H57) - Sous réserve de modification.