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 le nombre maximal d’éléments qu’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 propose ici une stratégie qu’on va implanter sur notre classe Flow.

Algorithme de la chaine 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 et l’arête \((3,6)\) prise dans le mauvais sens a un flot supérieur stricte à 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 une chaîne augmentante ?

Il suffit d’aappliquer 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

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

\(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 :

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

\(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\), \(f(S)\) est constant et égal à la valeur globale du flot.

Théorème flot-max/coupe-min : 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

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

Appliquons à présent l’algorithme de Ford-Fulkerson à \(N\) et soit \(F\) un flot tel qu’il n’y ai plus de chaîne augmentante. Par exemple :

F = flow_examples.small_example2()
F.show()

Cherchons une chaîne augmantante 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 chaine 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 plus petit ou égal à la couple minimale car tout flot est 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}\]