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

Contact

Responsable du master: Daniel VANDERPOOTEN

Secrétariat :
  Bureau : B530
  Tél. : 01 44 05 42 47
 email : master-modo@dauphine.fr

Adresse :
  Université Paris Dauphine
  Master MODO - Bureau P619
  Place du Maréchal de Lattre de Tassigny
  75775 Paris Cedex 16