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.
