ECTS : 3
Description du contenu de l'enseignement :
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
Bibliographie, lectures recommandées :
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