Flots et couplages · Théorie des graphes

Deux questions restent, et elles se ressemblent plus qu'il n'y paraît. Combien peut-on faire passer dans un réseau dont chaque conduite a une capacité ? Et : peut-on apparier tous les candidats à un poste, chacun n'acceptant que certains postes ? La première est un problème de flot, la seconde un problème de couplage, et le même algorithme résout les deux. C'est aussi l'occasion de voir un théorème qui relie un maximum à un minimum, forme de résultat rare et puissante.

Le réseau de transport

Définitions

Un réseau de transport est un graphe orienté où chaque arc porte une capacité positive, avec deux sommets distingués : une source $s$ et un puits $t$ .

Un flot associe à chaque arc une valeur comprise entre 0 et sa capacité, telle qu'en tout sommet autre que $s$ et $t$ , ce qui entre égale ce qui sort.

La valeur du flot est ce qui sort de la source.

Les deux contraintes, en une phrase chacune

Capacité : on ne fait pas passer plus qu'une conduite ne peut porter.
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.

Graphe orienté et pondéré6 sommets, 8 arêtes

Le réseau du chapitre. Chaque arc porte sa capacité ; S est la source, T le puits.

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.

Graphe résiduel

Le graphe résiduel contient, pour chaque arc $u \to v$ de capacité $c$ portant un flot $f$  :

un arc direct $u \to v$ de capacité résiduelle $c - f$ , ce qu'on peut encore ajouter ;

un arc inverse $v \to u$ de capacité $f$ , ce qu'on peut annuler.

Pourquoi l'arc inverse est indispensable

Sans lui, un premier chemin mal choisi bloque définitivement une partie du réseau, et l'algorithme s'arrête sur un flot qui n'est pas maximal.
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.

Le plus petit réseau où l'on voit le problème

Cinq arcs, tous de capacité 1. Le flot maximal vaut 2 : une unité par $s \to a \to t$ , une autre par $s \to b \to t$ . Voici pourtant ce que fait l'idée naïve si elle tombe d'abord sur le chemin du milieu.

Graphe orienté et pondéré4 sommets, 5 arêteschemin mis en évidence

Premier chemin trouvé, et il pousse 1 unité. Trois arcs sont maintenant saturés, et plus aucun chemin de s à t ne subsiste : sans arc inverse, l'algorithme s'arrête ici, sur un flot de valeur 1.

Le graphe résiduel, lui, ne s'arrête pas là. Chaque arc saturé y laisse un arc inverse de capacité 1, celle du flot qu'il porte.

Graphe orienté et pondéré4 sommets, 5 arêteschemin mis en évidence

Le graphe résiduel après ce premier envoi. Les arcs directs saturés ont disparu, remplacés par leurs inverses. Un chemin de s à t existe de nouveau, et il emprunte b vers a, c'est-à-dire une conduite à contresens.

Ce que veut dire « emprunter un arc à l'envers »

Pousser une unité le long de

s \to b \to a \to t

se traduit ainsi sur le vrai réseau : une unité de plus part par

s \to b

, une unité de moins passe par

a \to b

, et une unité de plus arrive par

a \to t

.
Le flot final est donc 1 sur

s \to a

, 1 sur

s \to b

, 0 sur

a \to b

, 1 sur

a \to t

et 1 sur

b \to t

 : valeur 2. L'algorithme n'a pas « ajouté du flot dans le mauvais sens », il a réorienté celui qu'il avait mal placé.

L'arc inverse n'existe pas dans le réseau

Il n'apparaît que dans le graphe résiduel, qui est une structure de calcul et non une description du réseau physique. Écrire un arc

b \to a

dans le réseau de départ signifierait qu'une conduite existe dans ce sens ; l'arc inverse résiduel dit seulement « il y a une unité déjà envoyée par là, et on peut la reprendre ».

Ford-Fulkerson

Tant qu'il existe un chemin de $s$ à $t$ 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 $O(n \times m^2)$ , indépendamment des capacités.

main.py

Sortie

>_ Prêt à exécuter…

Vérification rapideon peut se reprendre

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

Coupe

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 $s$ à $t$ 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.

Théorème flot-max coupe-min

\max_{\text{flots}} |f| = \min_{\text{coupes}} c(S, T)

Ce que ce genre de théorème apporte

Il donne un certificat vérifiable. Pour convaincre quelqu'un qu'un flot est maximal, on n'a pas à raconter le déroulement de l'algorithme : il suffit d'exhiber une coupe de même capacité.
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.

La coupe, sur le réseau du chapitre

Le flot maximal du réseau dessiné plus haut vaut 13. Voici comment il se répartit, chaque arc portant flot / capacité.

Graphe orienté et pondéré6 sommets, 8 arêtes

Le flot maximal, de valeur 13, chaque arc portant flot sur capacité. La première couleur marque les sommets encore atteignables depuis S dans le graphe résiduel, la seconde ceux qui ne le sont plus : ici, T tout seul. Les deux arcs qui les séparent, saturés tous les deux, forment la coupe minimale.

Vérifier le certificat en trois lignes

La coupe. D'un côté

\{S, A, B, C, D\}

, de l'autre

\{T\}

. Les arcs qui la traversent sont

C \to T

D \to T

, de capacités 7 et 6 : la coupe vaut 13.
Le flot. Ce qui sort de

S

vaut

5 + 8 = 13

, et ce qui entre dans

T

vaut

7 + 6 = 13

. La conservation se vérifie sommet par sommet : en

D

, il entre 8 et il sort

6 + 2 = 8

.
La conclusion. Les deux nombres coïncident, donc aucun flot ne peut dépasser 13 et aucune coupe ne peut descendre en dessous. Les deux sont optimaux, et il n'a pas fallu parler de l'algorithme une seule fois.

Où couper, en pratique

Les arcs de la coupe minimale sont exactement les goulots du réseau : ce sont eux, et eux seuls, qu'il faut élargir pour augmenter le débit. Élargir

S \to A

, qui ne porte que 5 sur 10, ne changerait strictement rien.
C'est la lecture qui rend le théorème utile en dehors des mathématiques : il ne dit pas seulement combien on peut faire passer, il dit où se trouve la limite.

Couplages

Définitions

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.

Graphe non orienté6 sommets, 5 arêteschemin mis en évidence

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 couplage biparti est un flot

Ajouter une source reliée à tous les sommets de gauche, un puits relié à tous ceux de droite, et donner la capacité 1 à tous les arcs.
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.

Graphe non orienté7 sommets, 6 arêtes

Bruno et David, en couleur, ne visent que Base. Deux candidats pour un seul poste accessible : au moins l'un des deux restera sans affectation, quoi qu'on fasse ailleurs.

La condition de Hall

Un couplage couvrant tous les candidats existe si et seulement si, pour tout sous-ensemble

X

de candidats, le nombre de postes accessibles depuis

X

vaut au moins

|X|

.
Ici

X = \{Bruno, David\}

donne

|X| = 2

et un seul poste accessible,

\{Base\}

. La condition est violée, donc aucun couplage ne place les quatre.

Un certificat, encore, et de la même famille

Ce sous-ensemble

X

est une preuve d'impossibilité, courte et vérifiable : il n'y a pas à énumérer les affectations, il suffit de compter deux candidats et un poste.
C'est la troisième fois que le module rencontre cette forme d'argument, après « clique et coloration » et « flot et coupe ». À chaque fois, une borne d'un côté, un objet qui l'atteint de l'autre, et la question est close.

main.py

Sortie

>_ Prêt à exécuter…

Théorème de Hall

Dans un graphe biparti $(G, D)$ , il existe un couplage saturant tout $G$ si et seulement si, pour tout sous-ensemble $A \subseteq G$ , le nombre de voisins de $A$ est au moins $|A|$ .

La bonne façon de prouver qu'un couplage parfait n'existe pas

Ne dites pas « j'ai essayé et je n'y arrive pas ». Exhiber un sous-ensemble violant la condition : trois candidats qui ne visent que deux postes, par exemple.
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 $k$ correspond alors exactement à un couplage de $k$ 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 $O(n \times m)$ , 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

Identifier source et puits avant tout, puis les capacités.
Vérifier la conservation en chaque sommet intermédiaire.
Construire toujours les arcs inverses, même à capacité nulle au départ.
Choisir le plus court chemin augmentant par un BFS.
Donner la coupe comme preuve, pas le déroulement de l'algorithme.
Ramener un couplage biparti à un flot plutôt que d'écrire un algorithme dédié.
Chercher le sous-ensemble de Hall pour prouver qu'un couplage parfait n'existe pas.

Synthèse

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.