EC Algorithmique des graphes et complexité

Cet enseignement comporte quatre parties :

1. Cycles et cocycles dans un graphe : exemples, algorithmes et applications.

2. Théorie des graphes appliquée à la recherche opérationnelle : réseaux de transport, graphes et réseaux de transport canalisés ; théorèmes de Ford-Fulkerson et de Hoffman ; algorithmes de Ford-Fulkerson et d'Edmonds-Karp ; applications.

3. Couplages et recouvrements : algorithmes dans le cas général et dans le cas de graphes bipartis.

4. Introduction à la théorie de la complexité : problèmes de décision, classes de problèmes (P et NP), problèmes NP-complets et problèmes NP-durs, réduction polynomiale, solutions approchées de problèmes NP-durs.

Cette UE vise à étudier, comprendre et utiliser des algorithmes issus de la théorie des graphes, très utiles en recherche opérationnelle. Ceci doit permettre de mettre en évidence divers types de complexité, notamment les classes de problèmes NP et P, que l'étudiant doit être capable d'identifier et pour lequel il doit savoir mettre en oeuvre quelques techniques d'attaque.

Connaître les concepts de base de théorie des graphes et savoir mettre en oeuvre les algorithmes élémentaires correspondants.

Connaître et savoir mettre en oeuvre quelques techniques de la recherche opérationnelle.

Maitriser des connaissances de base en théorie de la complexité.

Etre capable d'identifier un problème NP-complet et savoir mettre en oeuvre quelques techniques d'attaque.