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 nombreueses 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 arêtes
  • Coloration des graphes planaires

• Programmation linéaire
  • 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.

L'examen a eu lieu le 29 Avril 2004. Voici le sujet et sa correction.

-- HavetFrederic - 14 Jan 2004

to top