Je viens de regarder une vidéo intitulée Efficient Maximum Flow Algorithms (en anglais), et comme je me demandais depuis quelques jours ce dont je pourrais bien parler dans un TPA, c’est arrivé à point nommé. Donc, aujourd’hui, on va parler de « max flow » ou, en français, « flot maximum ». Commençons par donner un petit exemple. Supposons qu’on veuille trimbaler de l’eau depuis un point A à un point B. Pour cela, on dispose d’un réseau de tuyaux qui ont tous une certaine capacité, en terme de nombre de litres par seconde qui peuvent y circuler, et on se pose la question de savoir combien de litres par seconde peuvent arriver au point A. Faisons un petit dessin :
On a le point A, le point B, quelques points intermédiaires reliés par des tuyaux, et la capacité de chaque tuyau est indiquée sur chaque tuyau. Sur un « petit » réseau comme celui-ci, on peut s’en sortir en regardant très fort le schéma et en tentant de répartir l’eau au maximum dans les tuyaux de façon à ce qu’aucun tuyau ne soit en surcapacité, sinon ça explose et ça fait désordre (spoiler : sauf erreur grossière de ma part, on arrive avec ce réseau à 5600 litres par seconde).
Évidemment, plus le réseau est compliqué, plus le calcul l’est, et au-delà d’une certaine taille ça devient franchement pénible à faire à la main. Beaucoup de gens se sont intéressés au problème, qui est à la fois considéré comme un problème « classique » voire « résolu » (par exemple la bibliothèque C++ Boost a quelques implémentations pour le résoudre), et comme un domaine actif de recherche (il est, par exemple, en couverture du numéro d’août des Communications of the ACM). Au lieu de parler de litres d’eau et de tuyaux, on utilise notre modèle préféré, qui est celui d’un graphe (comme le laisse vaguement sous-entendre mon petit schéma au-dessus) ; le type de graphe qu’on considère a cependant quelques éléments supplémentaires par rapport aux graphes que nous avons manipulés jusqu’ici, par exemple lorsque nous avons parlé du théorème des cinq couleurs. On a, comme d’habitude, des sommets (les points A, B et les points intermédiaires) et des arcs (les tuyaux). Dans les sommets, on a deux sommets « spéciaux », les points A et B, que l’on appelle la source et le puits. Sur les arcs, on a deux informations supplémentaires : la direction, représentée sur le schéma par une flèche (on dit que le graphe est dirigé) et la capacité. Et on veut trimbaler une certaine quantité de trucs, c’est-à-dire un « flot », de A à B. Le problème peut donc être formulé comme « étant donné un graphe dirigé, dont les arcs ont des capacités, et étant donnés une source et un puits, quelle est la quantité maximum de flot qui peut être transportée de A à B ? ». Les algorithmes permettant de répondre à cette question ne sont pas forcément très compliqués, mais ils sont plus longs que ce que j’ai envie de détailler ici. Il en existe plusieurs, et il peut être intéressant de ne pas utiliser les mêmes en fonction du graphe considéré (on n’utilisera par exemple pas forcément le même algorithme pour un graphe ayant peu ou beaucoup d’arcs).
Considérons maintenant un autre problème. Supposons que j’aie une fuite massive d’eau en B, et que je veuille couper l’eau qui arrive en B en coupant la circulation dans des tuyaux, et ce de la manière la plus « efficace » possible. L’efficacité, dans mon exemple imaginaire, se mesure en débit total des tuyaux que je coupe : je veux le minimiser, pour que la reprise du service soit la plus facile possible. Quels tuyaux dois-je couper ? Il faut impérativement que je coupe le tuyau direct à 4000 entre A et B (sinon j’ai forcément de l’eau qui continue à arriver en B). Je peux couper tout ce qui arrive en B : j’ai deux tuyaux à 1000 et un à 900, ça fait un « coût » total de 2900. Mais en regardant d’un peu plus près mon graphe, plutôt que de couper l’arrivée en B, si je coupe les départs en A (hors la ligne à 4000, qui est coupée quoi qu’il arrive), je peux m’en sortir pour 2300, c’est mieux. Et en regardant d’encore plus près, si au lieu de couper le tuyau à 2000 je coupe celui à 500 et celui à 800, je descends à 1600 (300 + 500 + 800). Coïncidence amusante, si je fais la somme de tous les tuyaux que je coupe (4000+300+500+800), j’obtiens le même nombre que le nombre maximum de litres que je peux faire circuler dans mon réseau entre A et B, c’est à dire 5600.
Il se trouve que ce n’est pas une coïncidence. Ce second problème est connu sous le nom de « min cut » ou, en français, « coupe minimum » : étant donné un graphe avec des coûts ou poids sur les arcs, comment déconnecter deux points donnés A et B en supprimant des arcs de manière à ce que la somme de leurs poids soit minimum ? Et étant donné un graphe dirigé avec des capacités/poids, le théorème dit « min cut/max flow » dit que, pour toutes les paires de sommets A et B du graphe, la quantité maximum de flot qui peut aller de A à B est égale au poids minimum des arcs à supprimer pour déconnecter A et B. Pour donner une idée de la preuve, on peut voir qu’une coupe (un ensemble d’arcs qui, lorsqu’on les supprime, déconnecte A et B) est un goulot d’étranglement : il est impossible de faire passer plus de flot entre A et B que la capacité des arcs qui forment cette coupe. Ça permet de déduire que le flot maximum est forcément inférieur (ou égal) au poids de la coupe minimum. L’autre direction (montrer que la valeur de la coupe minimum est effectivement atteinte) est un peu plus délicate. L’idée est que si on a un flot maximum, alors on a des arcs qui sont saturés, c’est-à-dire que pour que le flot puisse passer de A à B, il faut faire passer une valeur de flot égale à la capacité de l’arc par l’arc en question. Si ce n’était pas le cas, on pourrait augmenter le flot, ce qui ne peut pas arriver (puisqu’on considère un flot maximum). On peut aussi voir que tous les chemins de A à B contiennent au moins un arc saturé – sinon, on pourrait augmenter le flot sur le chemin en question. Maintenant, on explore le graphe en partant de A, en avançant sur tous les chemins possibles, et on marque tous les sommets que l’on peut atteindre sans passer par un arc saturé. Si on retire tous les arcs qui partent de cet ensemble de sommets marqués vers l’ensemble des sommets non-marqués, on obtient une coupe (sinon il existerait un chemin de A à B contenant un arc non saturé). De plus, ces arcs sont saturés, et la somme de leur poids est exactement la valeur du flot maximum (puisqu’il s’agit de l’ensemble des arcs qui sortent de l’ensemble des sommets marqués). Donc la valeur de flot maximum est égale à la valeur d’une coupe, elle-même supérieure ou égale à la valeur de la coupe minimum. Tout ceci nous permet de déduire que la valeur de la coupe minimum est égale à la valeur du flot maximum (puisqu’elle lui est à la fois inférieure ou égale et supérieure ou égale), et donc on est contents. Pour une certaine définition de « contents » – l’idée de la preuve que j’ai donnée ici n’est pas des plus rigoureuse (en espérant qu’elle soit correcte, il a fallu que je m’y reprenne à trois ou quatre fois…), mais j’espère en avoir donné tout de même une idée raisonnable !
Le blog de Balise 