Description rapide : Les graphes : Une structure conceptuelle au service de la résolution de problèmes pratiques.

Objectif : Permettre à l'étudiant de se familiariser avec ce modèle mathématique et maîtriser les techniques algorithmiques efficaces portant sur des problèmes classiques d'optimisation pouvant s'exprimer en termes des graphes.

Pré-requis : STS.INFO.4.4

Programme :

• Définitions de base
• Connexité et forte connexité,
• Arbres et arborescences,
• Centres et rayon,
• Diamètre ...
• Parcours de graphes et algorithmes fondamentaux
• Parcours en largeur, en profondeur, LexBFS ...
• Composantes fortement connexes, blocs et points d’articulation, parcours euleriens et hamiltoniens, ...
• Arbre recouvrant de poids minimal
• Algorithmes du plus court chemin
• Familles particulières des graphes
• graphes de tournois, graphes sans circuits, graphes bipartis ...
• Graphes et Algorithmes d'optimisation.
• Flot et couplage, coloriage, clique et stable maximum, ordonnancement optimal...

Bibliographie :

• C. Berge, Graphes et Hypergraphes, Dunod 1970.
• M. Gondran et M. Minoux, Graphes et Algorithmes, Eyrolles 1985.
• Thomas Cormen, Charles Leiserson et Ronald Rivest, Introduction à l'algorithmique, Dunod, 1994.