Flots


Un exemple classique permet d'introduire la résolution de problème de flot au moyen de graphes :

-soit des stations de pompage pouvant puiser (et produire) une certaine quantité d'eau ;

-soit des villes ou usines utilisant cette eau, éventuellement nécessitant une quantité minimale de cette eau pour pouvoir fonctionner ;

-comment vérifier que les raccordements permettant de relier ces éléments permettent effectivement à l'ensemble de fonctionner correctement ?


La théorie des graphes permet de résoudre un tel problème en utilisant un " graphe de flot ".


Nous voyons tout d'abord les éléments théoriques nécessaires (définitions et propriétés) :

flot, graphe de flot, capacités, loi de Kirshoff

flot compatible, complet, maximal, ...


Nous introduisons la notion de "suite améliorante" afin de présenter la méthode de Ford-Fulkerson permettant de calculer un flot à valeur maximale.

Cette méthode converge plus rapidement si l'on part d'un flot complet. Nous voyons un algorithme permettant, partant d'un flot à valeur nulle, de déterminer un flot complet.

Ces deux méthodes sont présentées et illustrées dans leurs versions de base. Elles sont ensuite optimisées afin d'effectuer les plus fortes augmentations possible du flot à chaque étape.


Ces méthodes de recherche de flot complet / à valeur maximale nécessitent de connaître, au départ, un flot dit compatible. Dans nombre de problèmes, un flot à valeur nulle est compatible. Nous voyons une techniques permettant de trouver un flot compatible, si le flot à valeur nulle ne l'est pas, et si ce flot compatible existe (ce qui n'est pas toujours le cas).