Jeudi 9 avril 2026 de 9h30 à 12h30 puis de 14h à 16h30, à Télécom Paris [y aller]
Les flots constituent un sujet important en théorie des graphes et permettent de modéliser et de résoudre différents problèmes. Le stage propose une présentation de la théorie des flots en abordant notamment les points suivants :
- définitions du problème du flot de valeur maximum et du problème de la coupe de capacité minimum dans les graphes ;
- liens avec l’optimisation linéaire et la théorie de la dualité linéaire ;
- description de l’algorithme de Ford et Fulkerson pour résoudre les deux problèmes précédents ; évocation d’autres algorithmes ;
- problème du flot de valeur maximum et de coût minimum, algorithme de Busacker et Gowen ;
- quelques applications des flots et des coupes : problèmes de transport, problème du couplage maximum dans un graphe biparti, problèmes d’affectation, théorèmes de Menger…
Le stage ne comporte pas de partie consacrée à la programmation des algorithmes cités plus haut.
Intervenant : Olivier Hudry
Inscription prochainement disponible
