Ce cours s'intéresse aux graphes en tant qu'outil de modélisation pour la recherche opérationnelle.

Les détails se trouvent sur la page du module.

* * * * * *

Les problèmes de graphes, pertinents pour les applications, que nous étudierons, sont :

• Parcours de graphes
• Algorithmes de recherche (en profondeur / largeur) Recherche "informée" (A*)
• Coloration, en particulier pour des classes spécifiques (par ex.: graphes planaires)
• Couverture / domination
• Cheminements / flots
• Connexité / coupes / clusterisation, omposants fortement connexes
• Décomposition de graphes 
• Graphes et la logique MSO

Pour les problèmes mentionnés, nous étudions des algorithmes génériques et des spécialisations efficaces, et nous étudions leur complexité. Nous nous intéressons surtout à des algorithmes à paramètre fixé qui permettent des solutions efficaces à des problèmes "difficiles".

Les problèmes seront discutés en relation avec les applications suivantes :

• transport, affectation de ressources
• allocation de fréquences
• détection de défaillances
• tournées de véhicules
• emplois du temps / plannings
• clusterisation / réseaux sociaux
• réseaux de distribution

La bibliographie du cours est la suivante :

• J. H. van Lint, R. M. Wilson, A course in combinatorics, Cambridge University Press
• R. Diestel, Graph Theory, Springer
• A. Bondy, U. S. R. Murty, Graph Theory with Applications, Springer
• M. R. Garey, D. S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, Freeman

Illustration de la méthode de déchargement pour un problème sur la bande infinie de hauteur 2.

Décomposition récursive pour l'analyse d'un problème dans les arbres orientés.

[Département d'informatique de l'UPS]