Skip to topic | Skip to bottom
Home
Minfo06
Minfo06.OptimisationCombinatoirer1.2 - 10 Mar 2007 - 02:36 - BrunoBtopic end

Start of topic | Skip to actions

Optimisation Combinatoire

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

Informations pratiques

Les deux dernières journées de cours/TD auront lieu les 13 et 20 mars 2007, de 10h15 à 12h15 en M.I.7 et de 15h15 à 18h30 en M.II.5.

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

  • 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.

-- BrunoB - 09 Mar 2007
to top


You are here: Minfo06 > OptimisationCombinatoire

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback