Format des notes

Numérique sur 20

Littérale/grade européen

Programme détaillé

Dans la première partie, des résultats généraux seront présentés (Graphes k-partis, k-connexité, line graph et connectivité, rappel coupe min/flot max, isthme… Puis on traitera les couplages, facteurs, couvertures et stables. Dans la deuxième partie du cours, on s'intéressera aux relations entre les problèmes d'optimisation dans les graphes et la programmation mathématique, en particulier via la dualité et les approches primales-duales. On s'intéressera aux cas où la matrice associée au problème de graphe est totalement unimodulaire. Des problèmes "difficiles" seront présentés: multiflots/multicoupes, arbres de Steiner, ainsi que la réduction à des problèmes "simples" de l'optimisation dans les graphes dans certains cas particuliers. Enfin, dans la troisième partie, le sujet sera la coloration des graphes dont les applications sont très nombreuses: aspects de complexité, algorithmiques, études dans des graphes particuliers...