Optimisation Combinatoire

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

Plan du cours:

(Les versions postcript du support de cours ne sont pas finalisées : de nombreuses typos et erreurs sont susceptibles de s'y trouver.)

• Rappels rappels.ps
  • Parcours dans les graphes
  • Connexité
  • Graphes bipartis et eulériens

• Algorithmique classique dans les graphes algo.ps
  • Calcul de plus courts chemins : algorithmes de Dijkstra et de Bellmann-Ford
  • Arbre couvrant de poids minimum : algorithmes de Prim et de Kruskal

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

• Problèmes de flots flot.ps
  • 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.ps
  • Introduction et premières relations. Théoreme de Brooks
  • Coloration des graphes planaires
  • Coloration des arètes

• Programmation linéaire proglin.ps
  • Introduction
  • Méthode du simplexe

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.

Informations pratiques

Le cours du 22 Mars 2005 a été annulé. Il est reporté au Lundi 18 avril 2005 à 13h30 en salle M308.

L'examen aura lieu le Mardi 26 Avril 2005 à 15h15 en salle habituelle (MA).

-- HavetFrederic - 14 Jan 2004

to top