Graphs and Applications

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

Contents:

• Basic concepts in graph theory,

• Study of classical problems: flows, matching, covering, independent set, coloring

• Applications

Bibliography:

• 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