Graphes et réseaux : modélisation et algorithmes

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 :

* * * * * *

illustration de la methode de dechargement

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

methode de decomposition recursive pour l'analyse d'un probleme sur les arbres

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


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

Dernière mise à jour : 24 Oct 2017