Flots et couplages

Le réseau de transport

Dans les réseaux de ce chapitre, la source n'a aucun arc entrant et le puits aucun arc sortant : ce sont une source et un puits au sens du chapitre sur les représentations, une colonne vide et une ligne vide dans la matrice d'adjacence.

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.

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, $s \to a \to b \to t$. La figure s'ouvre après ce premier envoi, arcs inverses désactivés.

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, et l'un d'eux rouvre un chemin.

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.

Le programme ci-dessous range les capacités dans un dictionnaire indexé par les arcs : la clé ("S", "A") désigne l'arc $S \to A$. C'est plus commode ici que la liste d'adjacence du chapitre 2, parce que chaque arc inverse doit porter sa propre valeur. Le BFS examine les voisins dans l'ordre alphabétique : quand deux chemins ont la même longueur, c'est cet ordre qui décide lequel est retenu.

Le théorème flot-max coupe-min

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.

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 qu'au chapitre 7, où une clique minore et une coloration majore, 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 une répartition qui l'atteint, celle que trouve le programme ci-dessus en trois chemins, chaque arc portant flot / capacité. Il en existe d'autres (7 sur $S \to A$, 2 sur $A \to B$, 6 sur $S \to B$, le reste inchangé, vaut aussi 13), mais toutes saturent les deux arcs de la coupe.

C'est l'égalité qui certifie, et non le seul fait de s'arrêter. La petite figure du début s'arrêtait elle aussi faute de chemin, arcs inverses désactivés ; mais la coupe qu'elle affichait valait 2 pour un flot de 1, et le flot n'était pas maximal.

Couplages

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. La figure s'ouvre sur une affectation faite au fil de l'eau : Ana sur Base, puis Chloe sur Web.

Un couplage de taille 3 existe donc : Ana-Reseau, Bruno-Base, Chloe-Web.

Un quatrième candidat, David, ne vise lui aussi que Base, et un quatrième poste, Support, s'ouvre, qu'Ana accepterait. Quatre candidats pour quatre postes : le compte global ne dit rien, et pourtant le couplage maximum ne dépasse pas 3. On peut le prouver.

Ici $X = \{Bruno, David\}$ donne $|X| = 2$ et un seul poste visé, Base. La condition est violée, donc aucun couplage ne place les quatre. Le sens facile du théorème se comprend tout de suite : si un groupe vise moins de postes qu'il ne compte de personnes, quelqu'un restera sans poste. Le théorème dit que c'est le seul obstacle possible.

Le programme ci-dessous n'est pas un algorithme de plus : c'est Ford-Fulkerson, écrit directement sur les candidatures. Chercher un poste pour un candidat, quitte à déplacer l'occupant vers un autre poste qu'il accepte, c'est chercher un chemin augmentant dans le réseau à capacités 1 ; déplacer l'occupant, c'est emprunter un arc inverse. On lui donne parfois, à tort, le nom d'algorithme hongrois : la méthode hongroise (Kuhn, 1955) résout une autre question, l'affectation où chaque paire candidat-poste a un coût, et où l'on cherche le couplage parfait le moins cher.

Comme la coupe à la fin du flot, le témoin de Hall sort de l'algorithme sans rien énumérer. Depuis un candidat resté sans poste, on regarde les postes qu'il vise, puis les candidats qui les occupent, puis les postes que visent ces derniers, et ainsi de suite. Tous ces postes sont occupés : un poste libre atteint de cette façon donnerait un chemin augmentant, et le couplage, qui est maximum, aurait pu grandir. Chacun l'est par un candidat du groupe : le groupe compte donc un candidat de plus que de postes visés.

Mettre en pratique