L’objectif de cet article est d’expliquer une méthode permettant de calculer la quantité maximale de matière que l’on peut faire transiter entre un point A et un point B en empruntant un réseau de routes ou de conduits dont les caractéristiques sont connues.

Voici un problème concret qui devrait éclaircir et préciser le sens de la phrase précédente. Les pompiers viennent de recevoir un appel d’urgence car une maison de leur quartier est en flammes. Question : comment doivent-ils utiliser leurs ressources pour faire transiter un maximum d’eau du lac voisin à la maison qui brûle ? Pour nous permettre de raisonner, on a besoin d’un schéma représentant les différentes installations hydrauliques qui entrent en ligne de compte. Le voici :

On voit, par exemple, sur ce schéma que deux conduites d’eau partent du lac : l’une d’entre elles arrive directement à la caserne des pompiers, tandis que la seconde dessert une station d’épuration (représentée par la bulle en haut à gauche).
La caserne des pompiers est directement reliée à une borne incendie (que l’on supposera située à proximité de la maison en flammes) ainsi qu’à un camion de pompiers pouvant faire le chemin jusqu’à la maison. Etc.
Les flèches symbolisent donc les conduites entre les divers acteurs entrant en jeu. On remarque que chaque flèche est décorée en son milieu d’un petit rectangle dont la longueur varie ; cette longueur représente le débit de la conduite symbolisée. On observe, par exemple, que la conduite reliant le lac à la station d’épuration est d’un bien plus gros calibre que celle reliant la station d’épuration à la borne incendie.

Cela étant dit, la question qui nous préoccupe devient claire : on cherche à déterminer quelle quantité d’eau faire passer à travers chacune des conduites de façon à ce qu’in fine un maximum d’eau arrive à la maison (ou, ce qui revient au même, un maximum d’eau parte du lac).

Une méthode de résolution

La construction de base : une idée naturelle

Comme nous venons de l’expliquer, notre objectif est de faire passer le plus d’eau possible du lac à la maison. Pour cela, il est naturel de commencer par chercher un chemin reliant le lac à la maison et de faire passer le maximum d’eau le long de ce chemin.
Concrètement, on peut choisir le chemin passant d’abord par la caserne puis la borne incendie (mais ce n’est bien sûr pas le seul choix possible). Le long de ce chemin, le plus faible débit est atteint par les deux dernières canalisations à égalité. On décide donc, pour commencer, de faire circuler une quantité d’eau égale à ce débit commun le long du chemin retenu.
Après cette décision, la situation devient celle-ci :

où, vous l’aurez compris, les zones bleutées sur les flèches représentent l’eau qui transite par l’intermédiaire des conduits respectifs.

On peut à présent reproduire le même raisonnement que précédemment sauf que, bien sûr, on ne prend plus en compte les conduits reliant la caserne à la borne incendie d’une part et la borne incendie à la maison d’autre part puisque ceux-ci sont saturés (cela signifie que l’on ne peut plus faire passer d’eau supplémentaire par ces conduits).
On peut néanmoins à nouveau trouver un chemin reliant le lac à la maison qui évite ces deux conduits saturés : par exemple celui qui passe successivement par la caserne puis par le camion. On décide donc d’envoyer le long de ce chemin juste la quantité maximale d’eau possible, c’est-à-dire la quantité d’eau exacte nécessaire à saturer la canalisation reliant le lac à la caserne (qui se trouve, cette fois-ci, être le facteur limitant). On se retrouve ainsi dans la situation suivante :

On constate qu’il existe encore un chemin, n’empruntant aucun conduit saturé, qui relie le lac à la maison : c’est celui qui passe successivement par la station d’épuration, la caserne, puis le camion. Le conduit limitant est, cette fois-ci, celui reliant la station d’épuration à la caserne et on envoie donc le long du chemin trouvé l’exacte quantité d’eau nécessaire pour saturer ce conduit.

Le désengorgement des conduits

Si l’on observe un instant le schéma auquel on est parvenu (représenté sur la droite), on constate qu’il n’y a plus aucun chemin reliant le lac à la maison n’empruntant que des conduits non saturés. Il n’est donc, semble-t-il, plus possible de répéter la construction que nous venons déjà de faire trois fois. Est-ce à dire pour autant que nous avons une utilisation optimale du réseau ? Malheureusement, non ! En effet, examinons plus attentivement le schéma ci-contre et dégageons les trois remarques suivantes :

• La borne à incendie reçoit toute son eau de la caserne alors que le conduit la reliant à la station d’épuration n’est pas utilisé.
• il est encore possible d’amener de l’eau à la borne à incendie en passant par la station d’épuration, les conduits intervenant dans ce parcours n’étant pas saturé. (Cela n’a pas été fait jusqu’à présent car la borne incendie ne peut retransmettre plus d’eau que ce qu’elle ne reçoit actuellement.)
• Désengorger le conduit saturé entre la caserne et la borne permettrait de facto à la caserne de faire transiter de l’eau supplémentaire jusqu’à la maison en utilisant le camion.

On a ainsi trouvé une solution pour convoyer de l’eau supplémentaire du lac à la maison :

• premièrement, on demande à la caserne de procéder à une nouvelle répartition de sa distribution en utilisant davantage d’eau pour le camion mais, en contrepartie, en en envoyant moins à la borne incendie et,
• deuxièmement, on compense les pertes de la borne incendie en faisant transiter de l’eau via la station d’épuration.

Ceci revient encore à dire que l’on fait passer de l’eau selon le chemin représenté sur le schéma à gauche. On remarque que ce chemin « remonte » la conduite que l’on souhaite désengorger... et c’est d’ailleurs justement cette « remontée » qui symbolise le désengorgement. Si l’on veut (bien que ce ne soit pas cela qui se passe en pratique), on peut dire que l’on fait passer de l’eau à contre-courant dans cette conduite et que ceci compense une partie du débit qui traversait déjà la conduite dans le bon sens.

Récapitulatif : l’algorithme de Ford-Fulkerson

En quelques mots, la méthode que l’on vient de présenter peut se résumer comme suit :

1. On cherche un chemin reliant la source (ici, le lac) au but (ici, la maison) qui n’emprunte (dans le sens de parcours) aucun conduit saturé et peut éventuellement emprunter à contresens un conduit dans lequel passe déjà de l’eau.
2. On fait passer la quantité maximale de matière (ici d’eau) possible le long du chemin trouvé à l’étape précédente
3. On revient à la première étape.

Cette méthode porte le nom d’algorithme de Ford-Fulkerson, du nom de ses deux inventeurs.

Le moment où l’on s’arrête

En effectuant les dernières modifications sur notre exemple, on arrive à la situation suivante :

À présent, on ne trouve plus aucun chemin reliant le lac à la maison et n’empruntant que des conduits non saturés, quand bien même on s’autoriserait à remonter certains conduits. Est-ce à dire que l’on a trouvé une utilisation optimale des installations ? Cette fois-ci, la réponse est oui ! Mais, comment peut-on en être certain ?

Sur notre schéma, grisons le lac ainsi que les installations auxquelles on peut encore faire parvenir de l’eau depuis le lac en empruntant des conduites non saturées ou en remontant des conduites utilisées. On obtient le schéma représenté sur la droite.
Par exemple, la station d’épuration est grisée car elle peut encore être alimentée en eau directement en puisant dans le lac. De même, la caserne est grisée à cause du chemin passant par la station d’épuration et la borne incendie puis remontant la conduite reliant cette dernière à la caserne. De façon générale, il résulte de la façon dont on a grisé les installations que :

• tout conduit reliant une installation grisée à une installation non grisée est saturé, et
• tout conduit reliant une installation non grisée à une installation grisée n’est pas utilisé.

Considérons à présent une hypothétique meilleure solution et comparons les flux d’eau qui transitent entre les régions grisée et non grisée dans la solution que l’on a trouvée d’une part et dans la solution dont on suppose l’existence d’autre part.

• Dans le sens « grisé » → « non grisé », il y a certainement plus d’eau qui transite dans la solution à laquelle nous sommes parvenus puisque, dans celle-ci, tous les conduits sont saturés.
• Dans le sens « non grisé » → « grisé », il y a certainement plus d’eau qui transite dans la solution hypothétique puisque dans la solution à laquelle nous sommes parvenus, il n’y en a pas du tout.

Ainsi, si l’on fait le bilan, la solution que nous avons trouvée fait passer plus d’eau de la zone grisée à la zone non grisée (en comptant négativement l’eau passant dans l’autre sens) que n’importe quelle autre solution hypothétique. Mais, par ailleurs, la quantité d’eau passant de la zone non grisée à la zone grisée n’est autre que la quantité d’eau passant du lac à la maison étant donné qu’il n’y a d’accumulation d’eau dans aucune installation. Ainsi, on a bien démontré que la solution que nous avons trouvée est meilleure ou équivalente à toute autre solution ; en d’autres mots, on a bien trouvé l’optimum !

Quelles applications ?

Bien sûr, l’algorithme de Ford-Fulkerson que l’on vient de présenter ne permet pas simplement de résoudre l’exemple jouet présenté dans cet article mais s’applique à de nombreux autres problèmes concrets.
Sans changer véritablement de registre, il peut par exemple être utilisé par une entreprise qui voudrait calculer quelle quantité maximale de marchandise elle peut faire livrer depuis son site de fabrication jusqu’à son site de vente en empruntant les voies ferrées.

Cet article (en anglais) explique comment utiliser l’algorithme de Ford-Fulkerson pour résoudre le problème dit des mariages, dont le but est d’établir la plus longue liste possible de mariages sachant que chacune et chacun (tous supposés hétérosexuels) ont préétabli une liste de personnes avec lesquelles ils acceptent de se marier. Voir aussi cet article sur Images des Maths pour une autre présentation du lemme des mariages (sans lien explicite avec l’algorithme de Ford-Fulkerson).

L’algorithme de Ford-Fulkerson trouve aussi des applications dans le domaine des mathématiques pures. Par exemple, il peut être utilisé pour donner une autre démonstration (qui a l’avantage de s’étendre à des situations plus générales) du résultat de l’article Un problème de remplissage de verres sur ce site. Saurez-vous la trouver ?

Voici une autre application plus étonnante : il est utilisé en traitement d’images pour ce que l’on appelle la texturisation d’images. Pratiquement, on dispose d’un motif de petite taille que l’on souhaite répéter de la façon la plus jolie possible sur une grande surface. Par exemple, à partir d’une photographie de quelques épis de blé, on aimerait à partir de là fabriquer une image représentant tout un champ de blé. Vous avez peut-être déjà fait l’expérience par vous-même : disposer simplement les images les unes à côté des autres comme sur la figure ci-dessous donne généralement un résultat médiocre.

Pour améliorer ceci, l’idée naturelle consiste à faire des superpositions et des découpages. C’est dans la partie « découpage » que l’algorithme de Ford-Fulkerson apporte une contribution décisive. Nous vous renvoyons à [1] (article en anglais) pour de plus amples détails à ce sujet.

Jouez par vous-même

Les auteurs de cet article ont programmé une petite application web vous montrant l’algorithme de Ford-Fulkerson à l’œuvre dans un certain nombre de situations. Elle est ici. Attention, un navigateur récent est nécessaire.

Références

[1]
V. Kwatra, A. Schodl, I. Essa, G. Turk, A. Bobick, Graphcut Textures : Image and Video Synthesis Using Graph Cuts, disponible ici