Très simples à décrire, les graphes sont des outils très puissants de modélisation de problèmes. L’objectif de ce cours est de reconnaitre différents problèmes d'optimisation et d’associer à chacun d'eux une méthode de résolution. Pour ce faire, les outils nécessaires au développement, à la compréhension et à la description des principales méthodes d’optimisation en théorie des graphes sont décrits. Les principaux algorithmes de théorie des graphes sont prouvés (description, analyse de complexité, preuve qu’il répond à la question posée) et implémentés avec les structures de données adéquates.

Le cours couvre les sujets suivants :
  • Notions de base et avancées sur les graphes 
  • Cheminement 
  • Arbres 
  • Plus courts chemins 
  • Coloration 
  • Couplage