Flots et couplages
Ce que ce chapitre apporte
- Définir un réseau de transport, un flot, sa valeur, et une coupe.
- Comprendre le graphe résiduel et la nécessité des arcs inverses.
- Dérouler Ford-Fulkerson sur un petit réseau.
- Énoncer le théorème flot-max coupe-min et s'en servir pour prouver une optimalité.
- Modéliser un couplage biparti maximal comme un problème de flot.
- Appliquer le théorème de Hall pour justifier qu'un couplage parfait n'existe pas.
Le réseau de transport
Un réseau de transport est un graphe orienté où chaque arc porte une capacité positive, avec deux sommets distingués : une source et un puits .
Un flot associe à chaque arc une valeur comprise entre 0 et sa capacité, telle qu'en tout sommet autre que et , ce qui entre égale ce qui sort.
La valeur du flot est ce qui sort de la source.
Conservation : rien ne se perd ni ne se crée en cours de route, sauf à la source et au puits.
Toute la théorie découle de ces deux règles, et toute erreur de modélisation vient d'en avoir oublié une.
Chemins augmentants et graphe résiduel
L'idée naïve consiste à chercher un chemin de la source au puits, à y pousser autant que possible, puis à recommencer. Elle fonctionne presque : il lui manque la possibilité de revenir sur une décision.
Le graphe résiduel contient, pour chaque arc de capacité portant un flot :
un arc direct de capacité résiduelle , ce qu'on peut encore ajouter ;
un arc inverse de capacité , ce qu'on peut annuler.
L'arc inverse permet à un chemin ultérieur d'emprunter la conduite à l'envers, ce qui revient à dire : « ce que j'avais envoyé par là, je le réoriente ». Le flot reste valide à chaque étape, et l'algorithme peut corriger ses propres choix.
C'est le détail qui fait passer d'une heuristique à un algorithme exact.
Tant qu'il existe un chemin de à dans le graphe résiduel, y pousser le minimum des capacités résiduelles rencontrées, puis mettre à jour.
Quand il n'en existe plus, le flot est maximal.
Quand on choisit systématiquement le chemin le plus court, en nombre d'arcs, par un BFS, l'algorithme s'appelle Edmonds-Karp et sa complexité est bornée par , indépendamment des capacités.
1.À quoi sert l'arc inverse du graphe résiduel ?
2.Comment prouver qu'un flot est maximal ?
3.Quatre candidats ne visent que deux postes. Que conclure ?
Le théorème flot-max coupe-min
Une coupe est une partition des sommets en deux parties, l'une contenant la source, l'autre le puits. Sa capacité est la somme des capacités des arcs allant du côté source vers le côté puits.
Toute quantité qui va de à doit traverser chaque coupe. Donc la valeur de tout flot est inférieure ou égale à la capacité de toute coupe. Le théorème dit que les deux valeurs se rejoignent.
L'interlocuteur vérifie deux choses simples, que le flot est valide et que la coupe a bien cette capacité, et la conclusion s'impose. C'est la même structure de preuve que « clique + coloration » au chapitre 7, et c'est une forme d'argument qu'il faut savoir reconnaître.
La coupe minimale s'obtient gratuitement à la fin de l'algorithme : ce sont les arcs saturés qui séparent les sommets encore atteignables depuis la source, dans le graphe résiduel, de tous les autres.
Couplages
Un couplage est un ensemble d'arêtes deux à deux sans extrémité commune.
Il est maximum s'il contient le plus grand nombre possible d'arêtes, parfait s'il couvre tous les sommets.
Le cas biparti est celui qu'on rencontre : des candidats d'un côté, des postes de l'autre, une arête quand la candidature est recevable.
Ici, Bruno n'accepte que Base, et Ana comme Chloe la convoitent aussi. Un couplage de taille 3 existe pourtant : Ana-Reseau, Bruno-Base, Chloe-Web.
Un flot entier de valeur $k$ correspond alors exactement à un couplage de taille $k$ : la capacité 1 sur les arcs de la source garantit qu'un candidat n'est pris qu'une fois, et celle sur les arcs du puits qu'un poste n'est pourvu qu'une fois.
Le flot maximal donne donc le couplage maximum, sans écrire un algorithme de plus.
Ajoutons maintenant un quatrième candidat, David, qui ne vise lui aussi que Base. Le couplage maximum ne change pas de taille, et l'on peut le prouver.
Dans un graphe biparti , il existe un couplage saturant tout si et seulement si, pour tout sous-ensemble , le nombre de voisins de est au moins .
C'est court, vérifiable, et définitif. C'est encore la même structure d'argument : un certificat plutôt qu'une exploration.
Exercices type
Pourquoi le graphe résiduel contient-il des arcs inverses ?
Pour permettre à l'algorithme de revenir sur une décision antérieure.
Sans arc inverse, un premier chemin augmentant mal choisi peut saturer une conduite dont une autre route aurait eu davantage besoin, et l'algorithme s'arrête sur un flot non maximal.
L'arc inverse, de capacité égale au flot déjà passé, permet à un chemin ultérieur de « rendre » ce flot pour le réorienter. Le flot reste valide à chaque étape, et la correction de l'algorithme en dépend entièrement.
Comment prouver qu'un flot est maximal, sans refaire tourner l'algorithme ?
En exhibant une coupe de capacité égale à la valeur du flot.
Toute quantité allant de la source au puits traverse toute coupe, donc la valeur d'un flot est toujours inférieure ou égale à la capacité de toute coupe. Si les deux nombres coïncident, aucun des deux ne peut être amélioré.
C'est le théorème flot-max coupe-min, et c'est un certificat vérifiable en quelques additions.
Comment ramener un couplage biparti à un problème de flot ?
On ajoute une source reliée à tous les sommets de gauche, un puits relié à tous ceux de droite, on oriente les arêtes existantes de gauche à droite, et l'on met la capacité 1 partout.
Les capacités unitaires sur les arcs de la source empêchent un candidat d'être pris deux fois, celles sur les arcs du puits empêchent un poste d'être pourvu deux fois.
Un flot entier de valeur correspond alors exactement à un couplage de arêtes, et le flot maximal donne le couplage maximum.
Quatre candidats ne visent que deux postes. Que peut-on conclure ?
Qu'aucun couplage ne peut les placer tous les quatre, par le théorème de Hall : un sous-ensemble de 4 candidats n'a que 2 voisins, ce qui viole la condition.
Au mieux, deux d'entre eux obtiendront un poste.
Ce sous-ensemble est le certificat : il prouve l'impossibilité en une phrase, là où énumérer les affectations possibles serait long et peu convaincant.
Pourquoi choisir le plus court chemin augmentant ?
Pour garantir la terminaison et une bonne complexité.
Ford-Fulkerson avec un choix quelconque peut, sur des capacités mal choisies, effectuer un nombre d'itérations proportionnel à la valeur du flot, donc dépendant des nombres et non de la taille du graphe. Avec des capacités irrationnelles, il peut même ne pas terminer.
En prenant systématiquement le plus court chemin par un BFS, variante Edmonds-Karp, le nombre d'itérations est borné par , indépendamment des capacités.
Quel rapport entre ce chapitre et le chapitre sur la coloration ?
La structure de preuve.
Dans les deux cas, on encadre une quantité par deux côtés : une clique minore le nombre chromatique, une coloration le majore ; une coupe majore le flot, un flot la minore.
Quand les deux se rejoignent, l'optimalité est démontrée, et la preuve tient en un objet exhibé plutôt qu'en un raisonnement sur l'algorithme.
C'est une forme d'argument, la dualité, qui dépasse largement la théorie des graphes : on la retrouve en programmation linéaire, dont ces deux théorèmes sont des cas particuliers.
La méthode
- Identifie source et puits avant tout, puis les capacités.
- Vérifie la conservation en chaque sommet intermédiaire.
- Construis toujours les arcs inverses, même à capacité nulle au départ.
- Choisis le plus court chemin augmentant par un BFS.
- Donne la coupe comme preuve, pas le déroulement de l'algorithme.
- Ramène un couplage biparti à un flot plutôt que d'écrire un algorithme dédié.
- Cherche le sous-ensemble de Hall pour prouver qu'un couplage parfait n'existe pas.
En résumé
- Un réseau a des capacités, une source, un puits ; un flot respecte capacité et conservation.
- Le graphe résiduel porte les capacités restantes et les arcs inverses.
- L'arc inverse permet de défaire un choix : sans lui, l'algorithme n'est pas exact.
- Ford-Fulkerson pousse le long de chemins augmentants jusqu'à ce qu'il n'y en ait plus.
- Edmonds-Karp choisit le plus court, ce qui borne le nombre d'itérations.
- Flot-max coupe-min : le maximum d'un côté vaut le minimum de l'autre.
- Une coupe de même capacité que le flot est un certificat d'optimalité.
- Un couplage biparti se ramène à un flot à capacités unitaires.
- Le théorème de Hall donne le certificat d'impossibilité d'un couplage saturant.
Et ensuite ? Le module est terminé. Les graphes ne sont pas un chapitre de plus : c'est un langage, et le réflexe à garder est celui du premier chapitre, écrire les deux phrases « un sommet est … » et « il y a une arête si … ». Le reste est déjà résolu.