Algorithme De Ford-Fulkerson

Algorithme De Ford-Fulkerson#

L’algorithme de Ford-Fulkerson sert à calculer le flot de valeur maximale (ou simplement flot maximal (maximal flow)) sur un réseau entre deux points donnés. C’est la quantité maximale de «fluide» que l’on peut faire «couler» de la source vers la cible.

Le principe de l’algorithme est simple : on part du flot nul (toutes les valeurs sont à 0) et on augmente le flot jusqu’à ce que cela 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 définit 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 \(p_{min}\) ,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 \(p_{min}\).

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 \(p_{min} = 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é de \(p_{min}\) :

F.global_value()

Exercice

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 augmentantes 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()

Question

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#

Définition

Pour un flot donné, on appelle coupe (cut) un ensemble \(S\) de sommets tels que :

  • la source du flot est dans \(S\);

  • la cible du flot n’est pas dans \(S\).

La capacité \(c(S)\) de la coupe est définie par :

\[c(S) = \sum_{v \in S, t \notin S} c(v,t)\,,\]

où \(c(v,t)\) est la capacité de l’arête \((v,t)\).

La capacité de la coupe décompte le flot maximal qui pourrait passer à travers la frontière séparant les sommets à l’extérieur de la coupe et ceux à l’intérieur de la coupe.

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

Définition

Pour une coupe \(S\), la valeur de flot de la coupe est donnée par :

\[ f(S) = \sum_{v \in S, t \notin S} f(v,t) - \sum_{v \notin S, t \in S} f(v,t)\]

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

Remarque

La valeur du flot \(f(S)\) est majorée par sa capacité \(c(S)\).

En effet, toute quantité traversant le réseau de la source à la cible doit traverser la frontière de la coupe au moins une fois.

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.

D’après les remarques précédentes, pour chaque coupe \(S\) et chaque flot \(F\), la capacité \(c(S)\) de la coupe est un majorant de la valeur du flot \(f(F)\). De ce fait, si on a une coupe \(S\) et un flot \(F\) tels que \(c(S) = f(F)\), alors on peut directement en déduire que \(F\) est un flot maximal et \(C\) une coupe minimale.

\(C\) sert alors de certificat de la maximalité de \(F\) donnant une preuve immédiate de cette maximalité, sans avoir à faire de démonstration ou calcul supplémentaire. Réciproquement, \(F\) sert de certificat de la maximalité de \(C\),

Mais est-ce toujours possible de trouver une telle coupe et un tel flot? Oui, et c’est le théorème central de ce cours :

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.

Pour démontrer ce théorème, nous allons nous appuyer sur l’algorithme de Ford-Fulkerson; en retour cela démontrera que l’algorithme de Ford-Fulkerson produit bien un 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

\[ f(S) \leq c(S)\]

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()

Démonstration (suite)

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})

Démonstration (fin)

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:

\[c(S) = f(S)\]

Maintenant, on met ces éléments ensemble :

  1. La valeur globale d’un flot \(F\) sur un réseau \(N\) est égale à \(f(S)\) quelle que soit la coupe \(S\) de \(N\).

  2. Quelque soit le flot \(F\) sur \(N\) et quelle que soit la coupe \(S\) de \(N\), on a \(f(S) \leq c(S)\)

  3. 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

\[ F_{max} \geq f(S_m) = c(S_m) \geq C_{min}\]

Le flot maximal est à la fois plus petit ou égal et plus grand ou égal à la coupe minimale : on a donc nécessairement

\[ F_{max} = f(S_m) = c(S_m) = C_{min}\]

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!