Skip to topic | Skip to bottom
Home
Minfo05
Minfo05.OptimisationCombinatoirer1.20 - 09 Apr 2007 - 16:37 - 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

Le cours commencera le mardi 31 janvier 2006.

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.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 (flot.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 (proglin.pdf)
    • 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.

-- HavetFrederic - 14 Jan 2004
to top

I Attachment sortdown Action Size Date Who Comment
coloration.pdf manage 134.0 K 14 Dec 2006 - 05:51 BrunoB  
coloration.ps manage 480.1 K 18 Jan 2006 - 15:24 HavetFrederic La coloration
connexite.pdf manage 157.9 K 14 Dec 2006 - 05:51 BrunoB  
connexite.ps manage 575.7 K 18 Jan 2006 - 15:34 HavetFrederic Connexite
couplage.pdf manage 123.9 K 14 Dec 2006 - 05:52 BrunoB  
couplage.ps manage 458.4 K 18 Jan 2006 - 15:22 HavetFrederic Les couplages
flot.pdf manage 190.5 K 14 Dec 2006 - 05:52 BrunoB  
flot.ps manage 638.5 K 18 Jan 2006 - 15:23 HavetFrederic Les flots
proglin.pdf manage 160.7 K 14 Dec 2006 - 06:02 BrunoB  
proglin.ps manage 532.7 K 18 Jan 2006 - 15:34 HavetFrederic Programmation lineaire
rappels.pdf manage 84.5 K 14 Dec 2006 - 06:02 BrunoB  
rappels.ps manage 346.3 K 18 Jan 2006 - 15:15 HavetFrederic Les rappels

Minfo.OptimisationCombinatoire moved from Minfo03.OptimisationCombinatoire on 20 Oct 2004 - 14:37 by OlivierDalle
You are here: Minfo05 > 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