Cette UE présente les propriétés mathématiques fondamentales des graphes, et analyse les principaux algorithmes sur ceux-ci. Programme :
Graphes orientés et non-orientés : adjacence, degrés, voisinages ; chaînes, chemins, cycles et circuits ; composantes (fortement) connexes ; graphes eulériens ; arbres et arborescences. Algorithmes sur les graphes : parcours en largeur et en profondeur, tri topologique, composantes fortement connexes ; arbres couvrants minimum ; recherche de plus courts chemins ; réseaux de transports et recherche de flots maximaux. Couplages dans les graphes bipartis, applications.

À l'issue de cette UE une étudiante devrait savoir :
- les propriétés fondamentales des graphes et des arbres ;
- exprimer des problèmes dans le langage des graphes ;
- pratiquer les algorithmes sur les graphes.

Références :
C. Berge : Graphes, 2e édition, Dunod, 1973.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein : Introduction to Algorithms, PHI Learning, 2010. Traduction française : Algorithmique. Dunod, 2010.

À l'entrée de cette UE, une étudiante devrait :
- connaître les rudiments de mathématiques discrètes (cf. PSC en S4) ;
- pratiquer la programmation impérative, choisir les structures de données appropriées et connaître l'algorithmique de base (cf. SDA1 en S3 et SDA2 en S4).