Algorithme De Ford-Fulkerson#
L’algorithme de Ford-Fulkerson sert à calculer le flot de valeur maximale (ou simplement flot maximal) sur un réseau entre deux points donnés. C’est-à-dire la quantité maximale de «fluide» que l’on peut faire «couler» de la source vers la cible.
Le principe de base est simple : on part du flot nul (toutes les valeurs sont à 0) et on augmente le flot jusqu’à ce que ça ne soit plus possible. La question est de savoir comment «augmenter» un flot tout en conservant ses proriétés.
On présente ici une stratégie que l’on implantera ensuite sur notre classe Flow.
Algorithme de la chaîne augmentante#
Une chaîne augmentante est un chemin non-orienté de \(s\) à \(t\) (on peut prendre les arêtes dans n’importe quel sens) tel que :
sur les arêtes prises dans «le bon sens», la valeur du flot est strictement inférieure à la capacité de l’arête;
sur les arêtes prises dans «le mauvais sens», la valeur du flot est strictement supérieure à 0.
Par exemple, \(0 - 3 -6\) est une chaîne augmentante sur l’exemple de flot suivant :
l’arête \((0,3)\) prise dans le bon sens n’a pas atteint sa capacité maximale
l’arête \((3,6)\) prise dans le mauvais sens a un flot strictement supérieur à 0.
from flow import Flow
from flow_examples import flow_examples
F = flow_examples.example1()
F.show(marked_edges = {(0,3), (6,3)})
F.global_value()
On regarde ensuite le potentiel d’augmentation \(p\) pour chaque arête de la chaîne :
pour une arête prise dans le bon sens, \(p\) est égal à la différence entre la capacité de l’arête et la valeur du flot.
pour une arête prise dans le mauvais sens, \(p\) est égal à la valeur du flot (la différence entre la valeur du flot et 0).
On détermine \(pmin\) le potentiel minimum sur la chaîne puis, on augmente le flot des arêtes dans le bon sens et on diminue celui des arêtes dans le mauvais sens de la valeur \(pmin\).
Par exemple, pour notre chaîne \(0 - 3 - 6\), le potentiel de \((0,3)\) est 1 et le potentiel sur \((3,6)\) est 2. Dans ce cas, on a \(pmin = 1\) et on peut : augmenter le flot de \((0,3)\) pour le faire passer à 1 et diminuer le flot de \((3,6)\) pour le faire passer à 1. Le résultat est toujours un flot.
pmin = 1
F.add_flow(0,3,pmin)
F.add_flow(6,3,-pmin)
F.show(marked_edges = {(0,3), (6,3)})
F.check_in_out()
F.check_capacity()
Par ailleurs, on remarque que la valeur du flot a augmenté:
F.global_value()
Peut-on trouver d’autres chaînes augmentantes ?
F.show()
Comment chercher systématiquement une chaîne augmentante ?
Il suffit d’appliquer un algorithme de parcours du graphe (en profondeur ou en largeur). Attention, cependant, le graphe est orienté mais le parcours suit les arêtes dans les deux sens.
Exemple avec un parcours en profondeur
F = flow_examples.example1()
F.show()
F.show(marked_edges = {(0,1)})
F.show(marked_edges = {(0,2)})
F.show(marked_edges = {(0,2)}, marked_nodes = {2})
F.show(marked_edges = {(0,2), (2,1)}, marked_nodes = {2})
F.show(marked_edges = {(0,2), (2,4)}, marked_nodes = {2})
F.show(marked_edges = {(0,2), (5,2)}, marked_nodes = {2})
F.show(marked_edges = {(0,2), (5,2)}, marked_nodes = {2,5})
F.show(marked_edges = {(0,2), (5,2), (5,6)}, marked_nodes = {2,5})
Utiliser les chaînes augmentante pour trouver le flot maximal#
On part du flot nul et on augmente grâce aux chaînes augmentantes.
Exemple :
from flow import Flow
from flow_examples import flow_examples
F = flow_examples.small_example()
F.show()
F.show(marked_edges = {(0,1), (1,2), (2,3)})
F.add_flow(0,1,2)
F.add_flow(1,2,2)
F.add_flow(2,3,2)
F.show(marked_edges = {(0,1), (1,2), (2,3)})
F.show(marked_edges = {(0,1), (1,3)})
F.add_flow(0,1,1)
F.add_flow(1,3,1)
F.show(marked_edges = {(0,1), (1,3)})
F.show(marked_edges = {(0,2), (2,3)})
F.add_flow(0,2,1)
F.add_flow(2,3,1)
F.show(marked_edges = {(0,2), (2,3)})
F.show(marked_edges = {(0,2), (1,2), (1,3)})
F.add_flow(0,2,2)
F.add_flow(1,2,-2)
F.add_flow(1,3,2)
F.show(marked_edges = {(0,2), (1,2), (1,3)})
F.global_value()
Est-on sûr d’avoir obtenu le flot maximal ? On aurait pu faire d’autres choix pour les chaînes augmentantes !
La coupe minimale et théorème flot-max/coupe-min#
Pour un flot donné, on appelle une coupe un ensemble \(S\) de sommets tels que
La source du flot est dans \(S\)
La cible du flot n’est pas dans \(S\)
On calcule la capacité \(c\) de la coupe
où \(c(v,t)\) est la capacité de l’arête \((v,t)\).
Exemple :
F = flow_examples.example1()
F.show()
S = {0,1,2,5,3}
F.show(marked_nodes = S)
edges = set()
for a,b in F.network().edges():
if a in S and b not in S:
edges.add((a,b))
F.show(marked_nodes = S, marked_edges = edges)
c = sum(F.capacity(a,b) for a,b in edges)
c
Pour une coupe \(S\), la valeur de flot de la coupe est donnée par :
où \(f(v,t)\) est la valeur du flot sur l’arête \((v,t)\).
Par exemple :
edges_out = set()
edges_in = set()
for a,b in F.network().edges():
if a in S and b not in S:
edges_out.add((a,b))
if a not in S and b in S:
edges_in.add((a,b))
edges = edges_out.union(edges_in)
F.show(marked_nodes = S, marked_edges = edges)
f = sum(F.flow(a,b) for a,b in edges_out) - sum(F.flow(a,b) for a,b in edges_in)
f
Proposition : pour un flot donné, quelle que soit la coupe \(S\), la valeur de flot \(f(S)\) est constante et égal à la valeur globale du flot.
Théorème flot-max/coupe-min : la capacité de la coupe minimale d’un réseau est égale à la valeur globale de son flot maximal.
Démonstration : Soit \(F\) un flot sur un réseau \(N\) et \(S\) une coupe de \(N\). Par définition il est clair que
Appliquons à présent l’algorithme de Ford-Fulkerson à \(N\) et soit \(F\) un flot tel qu’il n’y ait plus de chaîne augmentante. Par exemple :
F = flow_examples.small_example2()
F.show()
Cherchons une chaîne augmentante par un parcours en profondeur:
F.show(marked_edges = {(0,1)})
F.show(marked_edges = {(0,1)}, marked_nodes = {1})
F.show(marked_edges = {(0,1),(1,2)}, marked_nodes = {1})
F.show(marked_edges = {(0,1), (1,3)}, marked_nodes = {1})
F.show(marked_edges = {(0,2)}, marked_nodes = {1})
F.show(marked_edges = {(0,2)}, marked_nodes = {1,2})
F.show(marked_edges = {(0,2), (2,3)}, marked_nodes = {1,2})
F.show(marked_edges = {(0,2), (1,2)}, marked_nodes = {1,2})
F.show(marked_nodes = {1,2})
Les sommets visités \(0,1,2\) forment une coupe \(S\). Et par ailleurs, on sait que :
toutes les arêtes sortantes de la coupe sont à capacité maximale
toutes les arêtes entrantes dans la coupe sont à 0
(sinon, on aurait pu continuer l’exploration pour chercher une chaîne augmentante) donc:
Maintenant, on met ces éléments ensemble :
La valeur globale d’un flot \(F\) sur un réseau \(N\) est égale à \(f(S)\) quelle que soit la coupe \(S\) de \(N\).
Quelque soit le flot \(F\) sur \(N\) et quelle que soit la coupe \(S\) de \(N\), on a \(f(S) \leq c(S)\)
Il existe un flot \(F_m\) et une coupe \(S_m\) tel que \(f(S_m) = c(S_m)\).
Les points 1 et 2, nous indiquent que le flot maximal est de valeur plus petite ou égale à la couple minimale car tout flot est de valeur plus petite que toute coupe.
Soit \(F_{max}\) la valeur du flot maximal, et \(C_{min}\) la valeur de la coupe minimale, avec le point 3, on a
Le flot maximal est à la fois plus petit ou égal et plus grand ou égal à la coupe minimale : on a donc nécessairement
Mise en perspective#
Les problèmes de flots dans les réseaux sont un cas particulier des problèmes d’optimisation linéaire (recherche d’une solution optimal d’un systèmes d”inéquations linéaires). L’algorithme de Ford-Fulkerson est une spécialisation de l’algorithme du simplexe. Le théorème flot-max coupe min est une spécialisation du théorème du dualité de la programmation linéaire.
Mais alors, pourquoi s’intéresser aux problèmes de flots, alors qu’une théorie plus générale existe?
D’abord parce que c’est une gamme de problèmes importante en pratique. Ensuite parce que les algorithmes se spécialisent bien. Et enfin parce que les problèmes de flots ont des propriétés particulières (théorème d’intégralité) qui permettent d’encoder de nombreux problèmes combinatoires (par exemple: recherche d’un couplage dans un graphe biparti) comme problème de flot pour les résoudre. Cela permet d’en déduire de nombreux théorèmes de type min-max en combinatoire.
Tout cela est le sujet de la combinatoire polyhédrale.
Conclusion#
Après cette description théorique de l’algorithme de Ford-Fulkerson, il est temps de passer à son implantation!