Flots et couplages

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• modéliser un problème d'acheminement par un réseau de flot — capacités, source, puits —, vérifier qu'une affectation de valeurs aux arcs est un flot et calculer sa valeur;
• construire le graphe résiduel d'un flot, y chercher un chemin augmentant, et expliquer pourquoi les arcs inverses sont indispensables là où un glouton naïf reste bloqué;
• énoncer et démontrer le théorème flot maximum – coupe minimum, et lire dans le dernier graphe résiduel la coupe qui certifie l'optimalité d'un flot;
• dérouler l'algorithme d'Edmonds–Karp à la main, et démontrer sa borne de $O(n{m}^2)$ opérations par la monotonie des distances résiduelles;
• ramener le couplage maximum dans un graphe biparti à un flot maximum, énoncer les théorèmes de Hall et de König, et dire pourquoi la couverture par sommets, difficile en général, devient facile dans un graphe biparti;
• reconnaître derrière un problème d'affectation, de chemins disjoints ou de fiabilité d'un réseau le flot maximum qui s'y cache.

Un problème nouveau sur un objet connu

Acheminer plutôt que parcourir

Les cinq chapitres de graphes qui précèdent posaient tous la même sorte de question: par où passer? Le parcours en largeur cherche le chemin le plus court en arêtes, Dijkstra le plus léger, Kruskal le réseau le moins cher qui relie tout. Dans chaque cas la réponse est un chemin ou un arbre, c'est-à-dire un choix d'arêtes.

Ce chapitre pose une question d'une autre nature: combien peut-on faire passer? Un réseau de conduites relie une station de pompage à un réservoir, chaque conduite ayant un débit maximal. Un réseau informatique relie un serveur à un client, chaque liaison ayant une bande passante. Un réseau ferroviaire relie une région de production à une région de consommation, chaque ligne pouvant porter un nombre limité de convois par jour. Dans les trois cas on veut le débit total maximal entre deux points, et la réponse n'est plus un chemin: c'est une répartition de la marchandise sur tout le réseau, qui emprunte en général plusieurs chemins à la fois et les fait se rejoindre et se séparer.

C'est précisément ce dernier exemple qui a lancé la théorie. Au milieu des années 1950, une étude militaire américaine du réseau ferroviaire d'Europe de l'Est cherchait à la fois le débit maximal de ce réseau et le plus petit ensemble de lignes dont la coupure l'interromprait. Lester Ford et Delbert Fulkerson ont montré en 1956 que ces deux questions, l'une de maximisation et l'autre de minimisation, ont la même réponse. C'est le théorème central de ce chapitre, et il fait partie de ces résultats dont la démonstration tient en une page et dont les applications n'ont pas fini d'apparaître.

Il y a une seconde raison de lire ce chapitre, et elle concerne le suivant. Le problème de l'affectation — répartir des étudiants entre des projets, des tâches entre des machines, des candidats entre des postes — se ramène exactement à un flot maximum, et se résout donc en temps polynomial. Le chapitre 12 montrera qu'un problème très voisin en apparence, la couverture par sommets, est $NP$-difficile en général; nous verrons ici qu'il devient facile dès que le graphe est biparti, et c'est le flot qui le dit.

Le réseau du chapitre

Tout le chapitre travaille sur un même petit réseau, que nous appelons $N$. Ce n'est pas le graphe témoin du cours: il est orienté, ses six sommets portent des noms en minuscules, $s$, $a$, $b$, $c$, $d$, $t$, et les nombres portés par ses arcs sont des capacités, non des poids. Les données sont fictives, choisies pour que chaque phénomène du chapitre s'y produise.

Il a $n=6$ sommets et $m=9$ arcs. On lira sur la figure 11.1 sa disposition: $s$ à gauche, $t$ à droite, $a$ et $b$ en haut, $c$ et $d$ en bas, une seule diagonale $a\to d$, et deux arcs verticaux et qui montent.

Réseaux et flots

L'hypothèse sur les arcs antiparallèles est une commodité d'écriture et non une restriction: si un réseau contient à la fois $u\to v$ et $v\to u$, on remplace le second par deux arcs $v\to w$ et $w\to u$ de même capacité, à travers un sommet nouveau $w$, et rien ne change aux débits possibles. Nous verrons d'ailleurs que le programme Python de ce chapitre n'en a pas besoin.

La notation $|f|$ est consacrée et trompeuse: ce n'est ni une valeur absolue ni un cardinal. Le second terme de (11.2) est nul dans tous nos exemples, puisqu'aucun arc n'entre dans $s$; on le garde dans la définition parce qu'il ne coûte rien et qu'il rend les démonstrations plus propres.

Un flot de valeur nulle existe toujours — $f\equiv 0$ satisfait les deux contraintes —, et un flot maximum existe aussi: l'ensemble des flots est un fermé borné de ${\mathbb{R}}^m$, sur lequel la fonction linéaire $|f|$ atteint son maximum. Cet argument d'existence ne dit rien de la façon de le trouver; tout le chapitre est là pour cela.

Le graphe résiduel et les chemins augmentants

Pourquoi le glouton échoue

L'idée la plus naturelle est gloutonne: tant qu'il existe un chemin de $s$ à $t$ dont tous les arcs ont encore de la capacité libre, on y pousse autant que le permet son arc le plus étroit. Le flot ne fait que croître, et l'on s'arrête quand plus aucun chemin n'est libre.

La leçon de l'exemple n'est pas qu'il fallait choisir un meilleur premier chemin — sur ce réseau-ci, on aurait pu; sur un réseau plus grand, personne ne sait d'avance lequel choisir. La leçon est qu'un algorithme correct doit pouvoir annuler une partie de ce qu'il a déjà poussé. Le graphe résiduel est l'outil qui rend cette annulation aussi naturelle qu'une poussée.

Le graphe résiduel

Les deux premiers cas ne se recouvrent jamais, grâce à l'hypothèse sur les arcs antiparallèles. Chaque arc de $G$ donne au plus deux arcs de $G_f$, un dans chaque sens: le graphe résiduel a donc au plus $2m$ arcs, et sa construction coûte $\Theta (n+m)$.

Démonstration. Notons $\beta =c_f(p)$ et $f^{\prime }=f\uparrow p$.

Capacités. Sur un arc direct $(u,v)$ de $p$, on a $\beta \le c_f(u,v)=c(u,v)-f(u,v)$, donc , et . Sur un arc inverse de , qui correspond à l'arc de , on a , donc , et . Comme est simple, chaque arc de est modifié au plus une fois; tous les autres gardent leur valeur. La contrainte de capacité est donc satisfaite partout.

Conservation. Soit $x\ne s,t$ un sommet. S'il n'est pas sur $p$, rien ne change autour de lui. S'il est sur $p$, le chemin y arrive par un arc résiduel $(w,x)$ et en repart par un arc résiduel $(x,y)$. Examinons les quatre combinaisons. Si les deux arcs sont directs, $x$ reçoit $\beta$ de plus par et en émet de plus par : le bilan est nul. Si les deux sont inverses, émet de moins vers et reçoit de moins de : nul encore. Si l'arc d'arrivée est direct et celui de départ inverse, reçoit de plus de et de moins de : ce qui entre est inchangé, ce qui sort aussi. Le dernier cas est symétrique. Dans les quatre cas, (11.1) reste vraie en .

Valeur. Le chemin quitte $s$ par un seul arc résiduel et n'y revient jamais, puisqu'il est simple. Si cet arc est direct, $f(s,\cdot )$ augmente de $\beta$; s'il est inverse, il annule $\beta$ d'un flot entrant en $s$, et le second terme de (11.2) diminue de $\beta$. Dans les deux cas $|f^{\prime }|=|f|+\beta$, et par définition du goulot.

La méthode de Ford–Fulkerson

Le lemme d'augmentation donne l'algorithme presque tout seul: partir du flot nul, et tant qu'un chemin augmentant existe, augmenter. On l'appelle une méthode plutôt qu'un algorithme, parce que la règle de choix du chemin n'y est pas fixée — et nous verrons que cette règle décide de tout pour le coût.

En Python, le plus simple est de ne garder que les capacités résiduelles, dans un dictionnaire de dictionnaires res[u][v]. Le flot nul a pour résiduel les capacités elles-mêmes dans le sens des arcs, et 0 dans le sens inverse:

def residuel_initial(capacites):
    """Capacites residuelles du flot nul: c(u, v) dans le sens de l'arc, 0 dans l'autre."""
    res = {}
    for u in capacites:
        for v, c in capacites[u].items():
            res.setdefault(u, {})
            res.setdefault(v, {})
            res[u][v] = res[u].get(v, 0) + c
            res[v].setdefault(u, 0)
    return res

Augmenter de $\beta$ le long d'un arc résiduel $(u,v)$ revient alors à deux affectations, quel que soit le sens de l'arc: res[u][v] -= beta, parce qu'on consomme la capacité résiduelle, et res[v][u] += beta, parce qu'on autorise l'annulation de ce qu'on vient de pousser. Les deux cas de la définition 11.3 sont traités par la même ligne: c'est tout l'intérêt de cette représentation. Elle traite aussi, sans rien changer, un réseau qui aurait des arcs antiparallèles — les capacités s'additionnent simplement dans res, d'où le res[u].get(v, 0) + c. Le flot porté par un arc $(u,v)$ de $G$ se relit à la fin comme $c(u,v)-$ res[u][v].

Ce que coûte la méthode dépend du nombre d'augmentations. Chaque recherche de chemin est un parcours du graphe résiduel, en $O(n+m)$, et nous supposerons désormais le réseau connexe au sens où chaque sommet est sur un chemin de $s$ à $t$, de sorte que $n\le m+1$ et que $O(n+m)=O(m)$.

Démonstration. Par récurrence sur le nombre d'augmentations, tous les flots construits sont entiers. Le flot nul l'est. Si $f$ est entier, toutes les capacités résiduelles (11.3) sont des différences d'entiers ou des entiers, donc des entiers; le goulot d'un chemin augmentant est le minimum d'entiers strictement positifs, donc un entier au moins égal à 1; et $f\uparrow p$ s'obtient en ajoutant ou retranchant cet entier: il est entier.

Chaque augmentation fait donc croître la valeur d'au moins 1 (lemme 11.1), et la valeur ne peut dépasser $|f^{\ast }|$. Il y a donc au plus $|f^{\ast }|$ augmentations, chacune coûtant un parcours en $O(m)$ et une mise à jour du chemin en $O(n)$. $\square$

Que le dernier flot soit maximum n'est pas encore démontré — la méthode pourrait s'arrêter sur un flot dont aucun chemin augmentant ne part, mais qui ne serait pas le meilleur. C'est l'objet de la section suivante, et c'est exactement ce qui distingue cette méthode du glouton de l'exemple 11.2: lui s'arrêtait faute de chemin libre dans $G$, elle s'arrête faute de chemin dans $G_f$, et la différence est l'ensemble des arcs inverses.

Le théorème flot maximum – coupe minimum

Les coupes

L'asymétrie entre (11.5) et (11.6) est voulue, et c'est la source de la plupart des erreurs de calcul: la capacité ne compte que les arcs de $S$ vers $T$, alors que le flot net retranche aussi les arcs de $T$ vers $S$. Un arc qui revient de $T$ vers $S$ ne coûte rien à la coupe, mais il peut rapatrier du flot.

Une coupe, c'est un ensemble d'arcs dont la suppression déconnecte $t$ de $s$ — l'ensemble de lignes qu'il faudrait interrompre, dans l'étude des années 1950 —, et sa capacité est le prix de cette déconnexion. Il y a autant de coupes que de façons de répartir les $n-2$ autres sommets, soit $2^{n-2}$: 16 pour le réseau $N$.

Démonstration. L'égalité. Pour un sommet $u$, notons $\varphi (u)={\sum }_{v}f(u,v)-{\sum }_{v}f(v,u)$ ce qui sort net de . Par (11.1), pour tout différent de , et par (11.2), . Donc

Séparons chaque somme intérieure selon que $v$ est dans $S$ ou dans $T$. Les deux sommes sur $u\in S$, $v\in S$ sont égales — ce sont les mêmes termes $f(u,v)$, $u$ et $v$ parcourant tous deux — et s'annulent. Il reste exactement .

L'inégalité. Dans (11.6), le premier terme est majoré par ${\sum }_{u\in S,v\in T}c(u,v)=c(S,T)$ grâce à la contrainte de capacité, et le second, une somme de valeurs positives ou nulles, est retranché. Donc $f(S,T)\le c(S,T)$.

Le cas $S=V\setminus \{t\}$ donne au passage ce que l'exemple 11.1 avait constaté: ce qui arrive en $t$ est égal à ce qui part de $s$.

Ce théorème est une dualité faible: toute coupe majore tout flot. Exhiber un flot et une coupe de même valeur prouve donc les deux optimalités à la fois — le flot ne peut pas être amélioré, puisqu'il touche une borne supérieure, et la coupe ne peut pas être diminuée, puisqu'elle touche une borne inférieure. Il reste à savoir si un tel couple existe toujours.

Le théorème

Démonstration. (1) entraîne (2). Si $G_f$ contenait un chemin augmentant $p$, le lemme 11.1 fournirait le flot $f\uparrow p$, de valeur strictement plus grande: $f$ ne serait pas maximum.

(2) entraîne (3). Supposons qu'aucun chemin de $s$ à $t$ n'existe dans $G_f$, et posons

On a $s\in S$ par le chemin vide et $t\notin S$ par hypothèse: $(S,T)$ est une coupe. Prenons $u\in S$ et $v\in T$. Alors : sinon l'arc résiduel prolongerait un chemin de à en un chemin de à , et serait dans . Lisons cette nullité dans (11.3).

• Si $(u,v)\in E$, $c_f(u,v)=c(u,v)-f(u,v)=0$: l'arc est , .

Reportons dans (11.6): le premier terme vaut ${\sum }_{u\in S,v\in T}c(u,v)=c(S,T)$ et le second vaut 0. Le théorème 11.3 donne alors $|f|=f(S,T)=c(S,T)$.

(3) entraîne (1). Par le théorème 11.3, tout flot $g$ vérifie $|g|\le c(S,T)=|f|$. Donc $f$ est maximum.

Pour la dernière phrase: un flot maximum existe, il vérifie (3) pour une certaine coupe $(S,T)$, et cette coupe est minimum, puisque toute coupe $(S^{\prime },T^{\prime })$ majore $|f|=c(S,T)$. $\square$

La démonstration de (2) entraîne (3) est constructive, et c'est ce qui la rend précieuse: la coupe minimum se lit dans le dernier graphe résiduel. Ce sont les sommets que le dernier parcours, celui qui n'a pas trouvé $t$, a quand même atteints. Le même parcours qui constate l'échec fournit donc le certificat d'optimalité, sans aucun calcul supplémentaire.

Ce théorème achève aussi la correction de Ford–Fulkerson: la méthode s'arrête quand $G_f$ n'a plus de chemin augmentant, c'est-à-dire, par (2) entraîne (1), sur un flot maximum. Avec des capacités entières, le théorème 11.2 ajoute qu'il existe un flot maximum à valeurs entières — celui que la méthode trouve. Ce corollaire anodin est ce qui permettra de traiter les couplages.

L'algorithme d'Edmonds–Karp

Le plus court chemin augmentant

Jack Edmonds et Richard Karp (1972), et indépendamment Yefim Dinic (1970), ont fixé la règle qui manquait: choisir à chaque étape un chemin augmentant ayant le moins d'arcs possible, c'est-à-dire celui que trouve un parcours en largeur de $G_f$. Le chapitre 6 nous a donné cet outil, et son théorème 6.4 garantit que le chemin trouvé est bien le plus court en arcs.

from collections import deque


def chemin_augmentant(res, s, t):
    """Plus court chemin de s a t dans le graphe residuel (en arcs), ou None."""
    pere = {s: None}
    file = deque([s])
    while file:
        u = file.popleft()
        for v in sorted(res[u]):
            if v not in pere and res[u][v] > 0:
                pere[v] =

Le seul changement par rapport au parcours en largeur du chapitre 6 est le test res[u][v] > 0: on ne suit que les arcs de capacité résiduelle positive, c'est-à-dire les arcs de $G_f$. Le tri des voisins rend la trace reproductible; il ne joue aucun rôle dans la correction.

def edmonds_karp(capacites, s, t):
    """Valeur d'un flot maximum, et la liste des augmentations effectuees."""
    res = residuel_initial(capacites)
    valeur, trace = 0, []
    while True:
        chemin = chemin_augmentant(res, s, t)
        if chemin is None:
            return valeur, trace, res
        goulot = min(res[u][v] for u, v in zip(chemin, chemin[1:]))
        for u, v in zip(chemin, chemin[

Chaque tour de boucle coûte un parcours en largeur, $O(n+m)=O(m)$ examens d'arcs résiduels, et une mise à jour en $O(n)$ le long du chemin. L'opération que nous compterons est donc l'augmentation, chacune valant $O(m)$.

La borne de Edmonds et Karp

La borne de la méthode générale dépendait de $|f^{\ast }|$. Celle d'Edmonds–Karp n'en dépend plus. La démonstration repose sur une propriété des distances dans le graphe résiduel, que l'exemple a laissé entrevoir. Notons ${\delta }_f(s,v)$ la distance en arcs de $s$ à $v$ dans $G_f$.

Démonstration. Supposons le contraire, et considérons la première augmentation qui fait diminuer une distance: elle transforme le flot $f$ en $f^{\prime }$, et l'ensemble des sommets $v$ tels que ${\delta }_{f^{\prime }}(s,v)<{\delta }_f(s,v)$ n'est pas vide. Choisissons-en un, , dont la distance est minimale. On a , puisque toujours. Soit le sommet qui précède sur un plus court chemin de à dans : l'arc est dans , et

Par le choix de $v$ — sa nouvelle distance est minimale parmi les sommets dont la distance a baissé, et celle de $u$ est plus petite —, la distance de $u$ n'a pas baissé: ${\delta }_{f^{\prime }}(s,u)\ge {\delta }_f(s,u)$.

Premier cas: $(u,v)$ était déjà un arc de $G_f$. Alors, par l'inégalité triangulaire en arcs (le théorème 6.2, qui vaut dans tout graphe orienté),

ce qui contredit ${\delta }_{f^{\prime }}(s,v)<{\delta }_f(s,v)$.

Second cas: $(u,v)$ n'était pas dans $G_f$, mais il est dans $G_{f^{\prime }}$. Un arc résiduel n'apparaît que si l'augmentation a fait passer du flot en sens inverse de lui, c'est-à-dire si le chemin augmentant contenait l'arc $(v,u)$. Or ce chemin est un plus court chemin de : l'arc y relie donc deux sommets de distances consécutives,

D'où ${\delta }_f(s,v)={\delta }_f(s,u)-1\le {\delta }_{f^{\prime }}(s,u)-1={\delta }_{f^{\prime }}(s,v)-2$, et a fortiori : contradiction encore.

Les deux cas sont impossibles; aucune distance ne diminue jamais. $\square$

Démonstration. Un arc résiduel est toujours l'un des deux sens d'un arc de $G$: il n'y a donc que $2m$ arcs résiduels possibles. Chaque augmentation a au moins un arc critique, qui disparaît de $G_f$. Montrons qu'un même arc résiduel $(u,v)$ ne peut être critique qu'au plus $n/2$ fois.

Quand $(u,v)$ est critique pour la première fois, il est sur un plus court chemin, donc ${\delta }_f(s,v)={\delta }_f(s,u)+1$, et il disparaît de $G_f$. Pour qu'il soit de nouveau critique, il faut qu'il réapparaisse, donc qu'une augmentation ultérieure, depuis un flot , emprunte l'arc inverse — sur un plus court chemin, à nouveau: . Par le théorème 11.5, , d'où

Entre deux occasions où $(u,v)$ est critique, la distance de $u$ augmente donc d'au moins 2. Elle part d'au moins 0 et, tant que $u$ est accessible, vaut au plus $n-2$ (un sommet critique n'est pas $t$, et un plus court chemin a au plus $n-1$ arcs); au-delà, $u$ est inaccessible et ne peut plus être sur aucun chemin. L'arc $(u,v)$ est donc critique au plus fois.

Les $2m$ arcs résiduels possibles offrent donc au plus $2m\cdot n/2=nm$ occasions d'être critiques, et chaque augmentation en consomme au moins une: il y a au plus $nm$ augmentations. Chacune coûte $O(m)$, d'où $O(n{m}^2)$. $\square$

On retiendra la forme habituelle: $O(nm)$ augmentations, $O(n{m}^2)$ opérations. Sur le réseau à 1000 du callout précédent, Edmonds–Karp choisit d'emblée les deux chemins de longueur 2 et s'arrête après deux augmentations, au lieu de deux mille. Pour un réseau de $n=1000$ sommets et $m=10000$ arcs, la borne vaut $n{m}^2=10^{11}$ opérations: c'est une majoration de pire cas, presque toujours très pessimiste, mais elle a le mérite d'être indépendante des capacités. Des algorithmes plus fins existent — le de Goldberg et Tarjan en , ou celui d'Orlin en —; nous les citons sans les étudier.

Couplages dans les graphes bipartis

Le problème de l'affectation

Cinq étudiants, que nous appelons $e_1,\dots ,e_5$, doivent chacun recevoir un projet de semestre parmi cinq, $p_1,\dots ,p_5$. Chacun a indiqué les projets qu'il accepte, et chaque projet ne peut être confié qu'à un seul étudiant. Les données, fictives, sont les suivantes:

Combien d'étudiants peut-on satisfaire au mieux? Le graphe qui relie chaque étudiant à ses projets est biparti au sens du chapitre 6 — une arête relie toujours un étudiant à un projet —, et la question porte sur un objet que le chapitre 12 utilisera aussi.

La distinction entre maximum et maximal est la même qu'entre un optimum global et un optimum local, et elle est cruciale. Tout couplage maximum est maximal, mais la réciproque est fausse: affectons gloutonnement chaque étudiant, dans l'ordre, au premier projet libre qu'il accepte. On obtient $e_1\text{–}{p}_1$, $e_2\text{–}{p}_3$, $e_3\text{–}{p}_2$, puis ne trouve plus rien ( et sont pris) et non plus ( est pris). Ce couplage de trois arêtes est — aucune arête n'y entre plus — et nous allons voir qu'il n'est . Le 2-approché de la couverture par sommets du chapitre 12 se contentera d'un couplage maximal, et c'est précisément pour cela qu'il est rapide; ici, on veut le maximum.

Le couplage comme flot

À un graphe biparti de parts $X$ (les étudiants) et $Y$ (les projets), on associe un réseau: une source $s$ reliée à chaque $x\in X$ par un arc de capacité 1, chaque arête $\{x,y\}$ orientée de $X$ vers $Y$ avec la capacité 1, et chaque $y\in Y$ relié à un puits par un arc de capacité 1. Pour nos étudiants, ce réseau a sommets et arcs.

Démonstration. D'un couplage à un flot. Soit $M$ un couplage et $f$ défini comme dans l'énoncé. Les capacités valent 1 et $f$ prend les valeurs 0 et 1: la contrainte de capacité tient. En un sommet $x\in X$ couvert par l'arête $\{x,y\}\in M$, il entre 1 par $s\to x$ et il sort 1 par $x\to y$; il n'y a pas d'autre arête de en , puisque les arêtes d'un couplage sont disjointes. En un sommet non couvert, rien n'entre ni ne sort. Même raisonnement en . La conservation tient, et est le nombre d'arcs chargés, soit .

D'un flot entier à un couplage. Soit $f$ un flot à valeurs entières. Chaque valeur est 0 ou 1, puisque les capacités valent 1. Soit $M$ l'ensemble des arêtes $\{x,y\}$ telles que $f(x,y)=1$. En un sommet $x\in X$, il entre au plus 1 — un seul arc entrant, de capacité 1 —, donc il sort au plus 1 par conservation: $x$ est l'extrémité d'au plus une arête de $M$. De même pour , qui n'a qu'un arc sortant de capacité 1. Donc est un couplage. Par le théorème 11.3 appliqué à la coupe , on a , aucun arc ne revenant de vers .

Conclusion. Par le théorème 11.2, il existe un flot maximum entier; il correspond à un couplage de même taille, donc $\nu (G)\ge |f^{\ast }|$. Inversement, un couplage maximum donne un flot de valeur $\nu (G)$, donc $|f^{\ast }|\ge \nu (G)$. $\square$

L'intégralité est ici indispensable: un flot qui mettrait $1/2$ sur chacune de deux arêtes issues d'un même étudiant ne correspondrait à aucune affectation. C'est le théorème 11.2 qui garantit qu'on peut s'en passer.

Ford–Fulkerson s'applique donc, et son coût est excellent: la valeur du flot est au plus $\min (|X|,|Y|)\le n/2$, donc il y a au plus $n/2$ augmentations, chacune en $O(m)$, soit $O(nm)$ au total, sans même avoir besoin d'Edmonds–Karp. L'algorithme de Hopcroft et Karp (1973), qui augmente le long de plusieurs plus courts chemins disjoints à la fois, descend à $O(m\sqrt{n})$; nous l'admettons.

Les théorèmes de Hall et de König

La figure exhibe un certificat d'impossibilité remarquablement court: trois étudiants qui ne se partagent que deux projets. Le théorème de Hall dit que c'est la seule obstruction possible.

Pour une partie $A$ de $X$, notons $N(A)$ l'ensemble des sommets de $Y$ voisins d'au moins un sommet de $A$.

La condition (11.7) s'appelle la condition de Hall, et sa nécessité est évidente: si un couplage couvre $X$, il envoie les sommets de $A$ sur des sommets distincts de $N(A)$, qui en a donc au moins $|A|$. Toute la force du théorème est dans la réciproque, que nous démontrons après le théorème suivant, dont elle découle.

Pour tout graphe, $\nu (G)\le \tau (G)$: une couverture doit contenir une extrémité de chacune des arêtes d'un couplage, et ces extrémités sont distinctes puisque les arêtes sont disjointes. C'est le point 2 du théorème 12.11, démontré au chapitre 12 pour un couplage quelconque. Sur un triangle, l'inégalité est stricte: $\nu =1$ et $\tau =2$. Dans un graphe biparti, elle ne l'est jamais.

Démonstration. Il reste à montrer $\tau (G)\le \nu (G)$. Modifions légèrement le réseau associé: les arcs du milieu, de $X$ vers $Y$, reçoivent la capacité $+\infty$ au lieu de 1 — en pratique, n'importe quel entier supérieur à $|X|$. Cela ne change pas la valeur du flot maximum: un sommet $x\in X$ ne reçoit au plus qu'une unité, par l'unique arc $s\to x$, donc il n'en émet au plus qu'une, et la capacité de ses arcs sortants n'est jamais atteinte. Le flot maximum vaut donc toujours .

Soit $(S,T)$ une coupe minimum de ce réseau; par le théorème 11.4, $c(S,T)=\nu (G)$, qui est fini. Aucun arc de capacité infinie ne va donc de $S$ vers $T$: si $x\in S\cap X$ et $\{x,y\}\in E$, alors . Les arcs qui sortent de sont donc des arcs avec , et des arcs avec , chacun de capacité 1:

Posons $C=(X\cap T)\cup (Y\cap S)$, de sorte que $|C|=c(S,T)=\nu (G)$. Montrons que $C$ est une couverture. Soit une arête, , . Si , alors . Sinon , et nous venons de voir que aussi, donc . Toute arête a une extrémité dans , et .

Démonstration du théorème de Hall. Supposons la condition (11.7) vraie, et montrons $\nu (G)=|X|$. Par le théorème de König, il suffit de montrer que toute couverture $C$ a au moins $|X|$ sommets. Soit $C$ une couverture, et $A=X\setminus C$ les sommets de $X$ qu'elle ne contient pas. Toute arête issue d'un sommet de $A$ doit être couverte par son autre extrémité: donc . Alors

la seconde inégalité par la condition de Hall appliquée à $A$. Donc $\nu (G)=\tau (G)\ge |X|$, et un couplage maximum couvre $X$. $\square$

Sur l'exemple des étudiants, la coupe minimum que le dernier parcours d'Edmonds–Karp met en évidence a pour côté $S=\{s,e_2,e_4,e_5,p_1,p_3\}$. La couverture de la démonstration est donc , de taille 4, égale à : affecter et , et satisfaire et par ailleurs, «couvre» toutes les préférences. Et l'ensemble est exactement la violation de Hall de la figure.

Deux applications

Chemins disjoints et fiabilité d'un réseau

Combien de chemins de $s$ à $t$ n'ayant aucune arête en commun un graphe contient-il? La question mesure la robustesse d'un réseau: s'il existe $k$ tels chemins, il faut couper au moins $k$ liaisons pour séparer $s$ de $t$.

Démonstration (esquisse). Donnons la capacité 1 à chaque arc. Une coupe $(S,T)$ a alors pour capacité le nombre d'arcs de $S$ vers $T$; les supprimer sépare $s$ de $t$, et réciproquement, l'ensemble $S$ des sommets encore accessibles depuis $s$ après la suppression d'un ensemble d'arcs $F$ séparant définit une coupe dont tous les arcs sortants sont dans $F$. Le minimum cherché est donc la capacité d'une coupe minimum. Par ailleurs, $k$ chemins arc-disjoints donnent un flot de valeur en mettant 1 sur chacun de leurs arcs; et un flot entier de valeur — il en existe un maximum, par le théorème 11.2 — se décompose en chemins arc-disjoints, ce qui est l'objet de l'exercice 11.5. Le théorème 11.4 égale les deux quantités.

Pour un graphe non orienté, on remplace chaque arête $\{u,v\}$ par les deux arcs $u\to v$ et $v\to u$, chacun de capacité 1. Ce sont des arcs antiparallèles, que notre définition excluait; mais nous avons vu que la représentation par capacités résiduelles du programme les traite sans difficulté, et l'on vérifie que des chemins arc-disjoints du graphe orienté donnent des chemins arête-disjoints du graphe non orienté, quitte à supprimer les paires d'arcs opposés portant chacun une unité, qui s'annulent.

Modéliser: plusieurs sources, des capacités sur les sommets

La force du flot maximum tient moins à l'algorithme qu'à la facilité avec laquelle des problèmes très divers se laissent mettre sous sa forme. Deux transformations reviennent sans cesse, et elles ne coûtent qu'un sommet ou un arc par élément du problème.

• Plusieurs sources et plusieurs puits. Des entrepôts $s_1,\dots ,s_k$ approvisionnent des magasins $t_1,\dots ,t_{\ell }$. On ajoute une reliée à chaque par un arc dont la capacité est le stock de l'entrepôt, et un que chaque rejoint par un arc de capacité égale à sa demande. Toute la demande est satisfaisable si et seulement si le flot maximum égale la demande totale.

La seconde transformation, avec la capacité 1 sur chaque sommet intermédiaire, transporte le théorème de Menger aux chemins sommet-disjoints. Le réseau des étudiants était déjà une modélisation de ce type: la capacité 1 des arcs $s\to e_i$ dit qu'un étudiant ne prend qu'un projet, celle des arcs $p_j\to t$ qu'un projet ne va qu'à un étudiant.

Synthèse

• Un réseau de flot est un graphe orienté muni de capacités, d'une source et d'un puits; un flot respecte les capacités et se conserve en chaque sommet intermédiaire, et sa valeur est ce qui quitte la source. Le réseau $N$ du chapitre — six sommets, neuf arcs — a un flot maximum de valeur 13.
• Le graphe résiduel $G_f$ décrit tout ce qu'on peut encore modifier: la capacité inutilisée de chaque arc, et, par les arcs inverses, le flot qu'on peut annuler. Sans eux, un glouton qui commence par $s\to a\to d\to t$ s'arrête à 12; avec eux, tout chemin augmentant fait croître la valeur de son goulot.
• Le théorème flot maximum – coupe minimum: un flot est maximum si et seulement si $G_f$ n'a plus de chemin augmentant, si et seulement si sa valeur égale la capacité d'une coupe. La coupe se lit dans le dernier graphe résiduel: ce sont les sommets encore atteints, ici , de capacité . Toute coupe majore tout flot, et un couple flot–coupe de même valeur certifie les deux optimums.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 24 (flot maximum): réseaux, graphe résiduel, théorème flot maximum – coupe minimum, Edmonds–Karp et couplage biparti; les démonstrations des théorèmes 11.5 et 11.6 suivent la sienne.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française du même chapitre, pour le vocabulaire: réseau de transport, graphe résiduel, chemin améliorant.
• Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 7, la meilleure source pour les applications: affectation, chemins disjoints, circulations avec demandes, segmentation d'images, élimination au baseball.
• Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitre 7, qui présente le flot comme un programme linéaire et la coupe comme son dual.
• Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — section 6.4, pour une implémentation commentée de Ford–Fulkerson par plus courts chemins.
• Polycopiés d'algorithmique de l'EPFL et de l'ETH Zurich, pour les flots et les couplages tels qu'ils sont enseignés en deuxième année.