Objectifs : 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.

Contenu :

• 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

• 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