Graphs and applications

ECTS : 3

Volume horaire : 15

Description du contenu de l'enseignement :

The goal of this course is to show the variety of concepts and algorithms of graph theory for modeling and solving concrete problems. We also show how to model, more or less directly, some real situations by reducing them to classical problems.

Compétence à acquérir :

• Basic concepts in graph theory,
• Study of classical problems: flows, matching, covering, independent set, coloring
• 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.