Master Informatique - Université de Bordeaux

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====Optimisation Combinatoire====

Responsables : [[https://dept-info.labri.fr/~baudon/| Olivier Baudon]]

Ce cours du S8 vaut 6ECTS.

===Résumé===

Partie 1 (Olivier Baudon) : [[https://dept-info.labri.fr/~baudon/Master/OptiComb/OptiComb.html| Coloration de graphes]]

Cette partie concerne les problèmes de la coloration de graphes, c'est à dire : 

- comment colorier les sommets d'un graphe de façon à ce que deux sommets voisins aient toujours des couleurs différentes ;

- comment colorier les arêtes d'un graphe de façon que deux arêtes partageant un sommet aient toujours des couleurs différentes.

Après avoir montré les bornes classiques sur le nombre de couleurs nécessaires, nous nous intéressons plus particulièrement à la classes des graphes parfaits, ce qui nous permet d'aborder des classes de graphes classiques, très souvent utilisées comme exemples pour différents paramètres : graphes d'intervalles, graphes de comparabilité, graphes scindés ...

Partie 2 (à compléter) : Programmation Linéaire

Cette partie du cours est consacrée à la programmation linéaire et à son utilisation pour résoudre des problèmes de graphes. Nous présentons l'algorithme du simplexe, la notion de dualité, ..., avant de passer à la question de l'utilisation des programmes linéaires pour les graphes, pour lesquels les solutions demandées sont forcément entières.

Master Informatique - Université de Bordeaux

Outils pour utilisateurs

Outils du site

Outils de la page