Optimisation Combinatoire

L'objectif de ce cours est de présenter les algorithmes standard en optimisation combinatoire.

Informations pratiques

L'examen aura lieu mardi 3 avril de 15h15 à 17h15 en salle M.II.5. Tous les documents seront autorisés.

Plan du cours:

• Rappels (rappels.pdf)
  • Définitions
  • Graphes bipartis et eulériens

• Connexité (connexite.pdf)
  • Calcul des composantes connexes dans un graphes
  • Calcul des composantes fortement connexes dans un digraphe
  • k-connexité et théorème de Menger

• Couplages dans les graphes (couplage.pdf)
  • Couplage dans les graphes bipartis : méthode hongroise
  • Couplage et couverture
  • Couplages dans les graphes généraux

• Problèmes de flots (flots.pdf)
  • Flot max = coupe min
  • Algorithmes de flots par poussée : algorithme initial de Ford et Fulkerson, algorithme de poussée par les plus courts chemins de Edmonds et Karp, algorithme utilisant un facteur d'échelle.
  • Flot dans les graphes non-orientés
  • Applications : Arête-connexité, couplage dans les graphes bipartis, clôture de bénéfice maximal.

• Coloration de graphes (coloration.pdf)
  • Introduction et premières relations. Théoreme de Brooks
  • Coloration des graphes planaires
  • Coloration des arètes

• Programmation linéaire (introPL.pdf)
  • Introduction
  • Méthode du simplexe

Corrigés des exercices : corrige1.pdf corrige2.pdf

Plusieurs livres reprenant une partie des chapitres de ce cours sont disponibles en ligne. Graph Theory with Applications par J.A. Bondy et U.S.R. Murty et Graph Theory par R. Diestel.

-- BrunoB - 28 Mar 2007
to top