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 :
- Enumération
- Démonstrations par récurrence
- Notions de base et avancées sur les graphes
- Cheminement
- Arbres
- Plus courts chemins
- Coloration
- Couplage
- Flot