Questions d'Entretien sur le Flot Maximal et la Coupe Minimale

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ce qu'une question de flot maximal évalue vraiment

Personne ne vous demande d'implémenter l'algorithme de Dinic de mémoire. Les questions de flot sont des questions de modélisation : le recruteur décrit une situation en langage courant, et tout l'exercice consiste à remarquer qu'il s'agit d'un réseau, à dessiner le bon et à nommer le théorème qui conclut.

C'est pourquoi ces questions ont la réputation d'être injustes. Un candidat qui a appris vingt problèmes d'arbres peut couler sur « affectez ces cinq ingénieurs à ces cinq équipes », parce qu'il ne fait jamais le saut d'une histoire de personnes à un graphe avec une source et un puits. L'algorithme est la moitié facile, et il est disponible dans n'importe quelle bibliothèque.

Quatre formulations couvrent presque tout ce qu'on vous donnera.

Tout ce qui suit est traité sur ce réseau à six nœuds, ou sur une petite variante, et chaque nombre a été calculé puis recalculé par une seconde méthode avant d'être publié.

2. Le modèle, et les deux méthodes qui comptent

Écrivez Dinic une fois et gardez-le. Il tient en une trentaine de lignes, il est assez rapide pour tout ce qu'un entretien produira, et il donne la coupe minimale en prime.

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.to, self.cap, self.adj = [], [], [[] for _ in range(n)]

    def add(self, u, v, c):
        self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
        self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0)

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                if self.cap[e] > 0 and self.level[self.to[e]] < 0:
                    self.level[self.to[e]] = self.level[u] + 1
                    q.append(self.to[e])
        return self.level[t] >= 0

    def dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.adj[u]):
            e = self.adj[u][self.it[u]]
            v = self.to[e]
            if self.cap[e] > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, self.cap[e]))
                if d > 0:
                    self.cap[e] -= d
                    self.cap[e ^ 1] += d
                    return d
            self.it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow

Deux détails méritent de pouvoir être expliqués, car c'est exactement ce qu'un bon recruteur sonde.

Le premier, ce sont les arêtes appariées. Chaque arête directe est stockée à côté de son arête inverse, si bien que e ^ 1 bascule de l'une à l'autre. L'arête inverse commence avec une capacité nulle et grandit à mesure que le flot est poussé. Elle existe pour que l'algorithme puisse annuler une mauvaise décision : envoyer du flot en arrière le long de cette arête annule du flot envoyé en avant. Sans elle, le premier chemin glouton peut vous bloquer sous l'optimum, et c'est la chose qu'un candidat sait le moins souvent expliquer.

Le second est self.it, l'optimisation de l'arc courant. Une fois qu'une arête est épuisée dans cette phase, elle n'est plus jamais examinée, et c'est ce qui fait passer Dinic du quadratique à sa borne annoncée. Supprimer cette seule ligne donne toujours des réponses correctes et détruit la complexité.

Lancez-le sur le réseau de la figure et la réponse est 16. Edmonds-Karp sur le même réseau renvoie aussi 16, ce qui est la vérification de cohérence la moins chère qui soit : deux algorithmes différents, une réponse.

3. Couplage biparti maximal

C'est la question qu'on vous posera le plus probablement, généralement déguisée en planification. « Cinq ingénieurs, cinq équipes, chaque ingénieur peut travailler dans certaines d'entre elles, maximisez le nombre de personnes placées. »

La réduction est mécanique. Ajoutez une source avec une arête de capacité 1 vers chaque ingénieur, un puits avec une arête de capacité 1 depuis chaque équipe, et des arêtes de capacité 1 pour chaque affectation autorisée. Comme les capacités sont entières, le flot maximal renvoie une solution entière, et un flot entier de valeur k est exactement un couplage de taille k : la capacité 1 depuis la source empêche d'utiliser quelqu'un deux fois.

def max_matching(left, right, can):
    n = len(left) + len(right) + 2
    s, t = 0, n - 1
    g = Dinic(n)
    for i in range(len(left)):
        g.add(s, 1 + i, 1)
    for j in range(len(right)):
        g.add(1 + len(left) + j, t, 1)
    for i, l in enumerate(left):
        for r in can[l]:
            g.add(1 + i, 1 + len(left) + right.index(r), 1)
    return g.max_flow(s, t)

Sur l'instance de la figure, la réponse est 4, et non 5. Ada, Ben, Cleo et Dan n'atteignent à eux quatre que backend, data et infra, donc trois postes doivent absorber quatre personnes et l'une d'elles reste sans poste. C'est la condition de Hall qui échoue, et la nommer vaut plus que le code : un couplage qui place chaque sommet de gauche existe si et seulement si chaque sous-ensemble du côté gauche a au moins autant de voisins que de membres. Le témoin le plus serré est ici encore plus petit : Ada, Cleo et Dan n'atteignent à eux trois que backend et data, trois personnes pour deux postes. La condition de Hall porte sur la saturation d'un côté, et elle ne coïncide avec un couplage parfait que lorsque les deux côtés ont la même taille, comme c'est le cas ici.

Si le recruteur cherche la réponse la plus rapide possible plutôt que la plus réutilisable, Hopcroft-Karp tourne en O(E√V) en augmentant le long de nombreux plus courts chemins à la fois. Dites qu'il existe, puis utilisez Dinic, qui atteint de toute façon la même borne sur les graphes à capacités unitaires.

4. La couverture cachée dans le couplage

Une bonne relance, qui piège la plupart des candidats : « donnez-moi maintenant le plus petit ensemble de personnes et d'équipes qui touche toutes les affectations possibles ».

C'est une couverture minimale par sommets, NP-difficile dans les graphes généraux. Dans un graphe biparti, elle ne l'est pas, et le théorème de König dit qu'elle a exactement la taille du couplage maximal. Pas besoin d'un second algorithme : vous lisez la couverture sur la coupe que vous avez déjà. Lancez une recherche depuis la source dans le graphe résiduel, puis prenez les sommets de gauche qu'elle n'atteint pas, plus les sommets de droite qu'elle atteint.

Sur cette instance, cela donne Ben, Eve, backend et data, quatre sommets, et une vérification à la main confirme que les neuf arêtes sont touchées. Le complémentaire d'une couverture par sommets est un stable, donc le plus grand stable vaut 10 − 4 = 6. Trois questions distinctes, un seul appel de flot maximal.

5. La coupe minimale : les arêtes, pas seulement le nombre

« Quel est l'ensemble de liens le moins cher à couper pour qu'aucun trafic n'atteigne le centre de données ? » La valeur est le flot maximal, par le théorème. Mais les recruteurs demandent quels liens, et c'est une étape différente et plus facile que beaucoup de candidats n'ont jamais apprise.

Une fois le flot maximal, lancez une recherche depuis la source sur les arêtes qui ont encore une capacité résiduelle. Soit R l'ensemble atteint. La coupe minimale est formée de chaque arête d'origine allant de R vers son complémentaire.

def min_cut(self, s):
    seen = [False] * self.n
    seen[s] = True
    q = deque([s])
    while q:
        u = q.popleft()
        for e in self.adj[u]:
            if self.cap[e] > 0 and not seen[self.to[e]]:
                seen[self.to[e]] = True
                q.append(self.to[e])
    return [(self.to[e ^ 1], self.to[e])
            for e in range(0, len(self.to), 2)
            if seen[self.to[e ^ 1]] and not seen[self.to[e]]]

Sur le réseau d'exemple, l'ensemble atteignable est {S, A, B} et la coupe est A→C à 7 plus B→D à 9, soit 16, la valeur du flot. La force brute sur les seize sous-ensembles possibles côté source confirme qu'aucune coupe moins chère n'existe.

Deux pièges se cachent ici. Ne comptez que les arêtes allant de l'ensemble atteignable vers l'ensemble non atteignable ; les arêtes qui reviennent ne font pas partie de la coupe. Et la coupe minimale n'est souvent pas unique : si on vous demande « la » coupe, dites que vous en renvoyez une parmi peut-être plusieurs, et qu'elles ont toutes la même valeur.

6. Chemins disjoints et théorème de Menger

« Combien de routes indépendantes y a-t-il du bureau au centre de données ? » est une question de flot où toutes les capacités valent 1.

Mettez chaque capacité à 1 et le flot maximal compte les chemins arête-disjoints, car une unité de flot ne peut pas partager une arête avec une autre. Le théorème de Menger dit alors que ce nombre est égal au nombre minimal d'arêtes dont la suppression sépare les deux sommets. Max-flow min-cut est la généralisation pondérée précisément de cet énoncé.

Sur le réseau d'exemple avec capacités unitaires, la réponse est 2, et une coupe minimale est formée des deux arêtes qui quittent la source, même si six paires d'arêtes différentes y parviennent. Mieux vaut le souligner que le cacher : avec des capacités unitaires, la réponse n'est souvent qu'une borne de degré, et le dire montre que vous comprenez ce que signifie le nombre et pas seulement comment le calculer.

Si la question parle plutôt de chemins disjoints par sommets, les capacités sur les arêtes ne peuvent pas l'exprimer, et il vous faut la première astuce de modélisation ci-dessous. Ici, cela donne aussi 2, et retirer C et D rend effectivement T inaccessible. Une hypothèse mérite d'être dite à voix haute : la forme par sommets du théorème de Menger exige que les deux extrémités ne soient pas adjacentes, ce qui est le cas ici puisqu'il n'y a pas d'arête directe de S à T.

7. Trois astuces de modélisation qui transforment une histoire en réseau

Presque toute question de flot en entretien est l'une de ces transformations autour du même solveur.

Un sommet a une capacité. « Ce routeur supporte 3 unités. » Les capacités vivent sur les arêtes, alors dédoublez le sommet : remplacez v par v_ent et v_sor, reliés par une arête de capacité 3, envoyez chaque arc qui arrivait en v vers v_ent, et faites partir chaque arc qui quittait v de v_sor. Fixer la capacité interne à 1 permet de compter les chemins disjoints par sommets.

Plusieurs sources, plusieurs puits. « Trois entrepôts approvisionnent deux magasins. » Ajoutez une super-source avec des arêtes de capacité infinie vers chaque vraie source, et un super-puits alimenté par chaque vrai puits. Un seul appel au solveur remplace l'énumération qu'un candidat pourrait sinon commencer à écrire.

L'arête est non orientée. Ajoutez les deux sens à pleine capacité. On pourrait croire que cela autorise le double du trafic, et ce n'est pas le cas, car la comptabilité résiduelle annule le flot envoyé en sens opposés. Soyez prêt à le dire, car c'est une objection naturelle et la réponse est courte.

Le quatrième cas est celui qui piège les candidats : une borne inférieure. « Chaque chauffeur doit assurer au moins deux services » n'est pas une capacité, et le solveur standard ne peut pas l'exprimer. Il faut une construction de circulation réalisable, et le bon réflexe en entretien est de relever le mot « doit » à voix haute plutôt que de tout coder.

8. Sélection de projets, ou pourquoi une coupe peut choisir un sous-ensemble

Celle-ci a l'air de relever de la programmation dynamique et ce n'est pas le cas, ce qui en fait une favorite.

« Chaque projet rapporte un profit connu. Chaque projet a besoin de certaines machines. Chaque machine coûte un montant fixe et est partagée par tout ce qui en a besoin. Choisissez le sous-ensemble le plus rentable. »

Le piège, c'est la gloutonnerie : prendre chaque projet à profit positif, ou trier par profit par machine. Aucune des deux n'est correcte, car les machines sont partagées, si bien que le vrai coût d'un projet dépend des autres projets que vous prenez.

La construction est courte. Source vers chaque projet avec une capacité égale à son profit ; chaque machine vers le puits avec une capacité égale à son coût ; projet vers machine avec une capacité infinie pour que cette arête ne puisse jamais être coupée. La réponse est alors

profit maximal = (somme de tous les profits) − (coupe minimale)

et les projets à prendre sont ceux du côté source de la coupe. Ce sont les arêtes infinies qui imposent la cohérence : si vous gardez un projet côté source, ses machines doivent y être aussi, sinon la coupe serait infinie. C'est la définition d'un ensemble fermé, et c'est le problème de la fermeture maximale.

Sur l'instance de la figure, les profits totalisent 235, la coupe minimale vaut 195 et le meilleur résultat possible est 40, en prenant alpha, beta et gamma et en laissant delta. Delta rapporte 30 mais est le seul projet à avoir besoin de fab, qui coûte 50, donc l'ajouter aux trois autres coûte 20 de plus que ce qu'il rapporte. La force brute sur les seize sous-ensembles le confirme.

9. Élimination au baseball

Un classique, et inhabituel en ce que la réponse naïve n'est pas seulement lente, elle est fausse.

Étant donné le classement et les matchs restants, une équipe peut-elle encore finir première ? La vérification évidente consiste à voir si son meilleur total possible dépasse encore le total actuel de chaque rival. Elle attrape les cas faciles et rate les cas intéressants, car les rivaux doivent s'affronter et quelqu'un doit gagner ces matchs.

Voici un tableau où la vérification naïve ne voit rien d'anormal :

Les Ducks peuvent atteindre 79, et aucun rival n'a encore 79 victoires, donc aucune comparaison individuelle ne les élimine. Mais parmi les matchs restants, les Aces jouent deux fois contre les Bolts, les Aces une fois contre les Comets et les Bolts trois fois contre les Comets. Six matchs entre les trois rivaux, et chacun offre une victoire à quelqu'un.

Construisez un réseau : une source vers un nœud par paire restante, portant le nombre de matchs qu'elles doivent encore jouer ; chaque nœud de paire vers ses deux équipes avec une capacité infinie ; chaque équipe vers le puits avec une capacité égale au nombre de victoires supplémentaires qu'elle peut se permettre avant de dépasser le meilleur cas des Ducks, 79. Les Ducks survivent seulement si les six matchs peuvent être absorbés, c'est-à-dire seulement si le flot maximal sature la source.

Ce n'est pas le cas. Le flot vaut 5 contre 6 matchs, donc un match n'a nulle part où aller, et les Ducks sont éliminés. L'énumération des 2⁹ issues possibles de tous les matchs restants de la ligue le confirme : il n'existe aucun scénario où les Ducks finissent premiers, et il en existe un pour chacune des trois autres équipes.

Le déficit vous dit aussi pourquoi : les arêtes d'équipe saturées désignent le groupe de rivaux qui, à eux tous, doivent gagner plus de matchs qu'ils ne peuvent se le permettre. Les recruteurs qui connaissent ce problème demandent toujours cette explication.

10. Couverture minimale par chemins dans un DAG

« Quel est le nombre minimal d'ouvriers nécessaires pour effectuer toutes ces tâches, si un ouvrier ne peut passer qu'entre des tâches qui se suivent ? »

C'est une couverture minimale par chemins : le plus petit nombre de chemins disjoints par sommets couvrant tous les sommets d'un graphe orienté acyclique. Elle se ramène au couplage par une astuce à retenir. Dédoublez chaque sommet en une copie de sortie à gauche et une copie d'entrée à droite, placez une arête dans le graphe biparti pour chaque arête du DAG, et cherchez un couplage maximal. Alors

couverture minimale par chemins = nombre de sommets − couplage maximal

, car chaque arête couplée relie deux fragments de chemin et retire donc un chemin du décompte. Sur un DAG à six sommets et sept arêtes, le couplage maximal vaut 4, donc la couverture minimale par chemins vaut 6 − 4 = 2, et une recherche exhaustive sur tous les sous-ensembles d'arêtes le confirme.

Une précision compte et est souvent omise : cela compte des chemins disjoints par sommets. Si les chemins peuvent partager des sommets, calculez d'abord la fermeture transitive du DAG, puis appliquez la même réduction.

11. Quand c'est un flot de coût minimal et non un flot maximal

La relance la plus fréquente de tout le sujet : « maintenant chaque affectation a un coût, et je veux la façon la moins chère de placer tout le monde ».

Le flot maximal ne peut pas répondre à cela. Il maximise la quantité et est indifférent entre deux solutions de même taille, il renverra donc volontiers le couplage parfait le plus cher. Ce qu'il vous faut, c'est le flot maximal de coût minimal : parmi tous les flots de valeur maximale, trouver celui de coût total minimal.

Le changement de modèle est minime. Chaque arête reçoit un coût par unité en plus de sa capacité, et l'algorithme augmente à répétition le long du chemin le moins cher du graphe résiduel plutôt que du plus court ou d'un chemin quelconque. Comme les arêtes résiduelles portent un coût négatif, Dijkstra ne s'applique pas directement : les implémentations standard utilisent soit Bellman-Ford, ce qui donne l'algorithme des plus courts chemins successifs, soit des potentiels à la Johnson pour que Dijkstra reste utilisable.

Trois choses méritent de pouvoir être dites à ce sujet.

Le cas particulier a un nom. Un graphe biparti complet avec un coût sur chaque affectation et l'exigence que tout le monde soit affecté, c'est le problème d'affectation, et la méthode hongroise le résout en O(n³). Si le problème du recruteur est exactement « n ouvriers, n tâches, minimisez le coût total », nommer la méthode hongroise est la réponse attendue.

L'intégralité tient toujours. Avec des capacités entières, le flot maximal de coût minimal peut toujours être pris entier, ce qui maintient l'interprétation en couplage une fois les coûts ajoutés.

Le piège, c'est de maximiser autre chose. « Maximiser la valeur totale » et « maximiser le nombre d'affectations » ne sont pas le même objectif, et une solution peut être optimale pour l'un et médiocre pour l'autre. Demandez lequel est voulu avant d'écrire quoi que ce soit, car le recruteur est souvent volontairement ambigu pour voir si vous le remarquez.

Une frontière utile à énoncer : sans coûts, utilisez le flot maximal ; avec des coûts mais où chaque unité doit circuler, c'est un flot de coût minimal ; si les coûts sont sur les sommets plutôt que sur les affectations, vous êtes probablement revenu sur le terrain de la fermeture de la section 8.

12. Les réponses sur la complexité

Ayez-les prêtes, et soyez prêt à dire laquelle vous utiliseriez vraiment.

L'avertissement mérite d'être énoncé précisément, car c'est une relance fréquente. Ford-Fulkerson est le seul dont le temps d'exécution dépend des valeurs de capacité plutôt que de la taille du graphe. Chaque chemin augmentant ajoute au moins 1 au flot, donc la boucle tourne au plus maxflow fois, et si les capacités valent un milliard, cette borne représente un milliard d'itérations sur un graphe à quatre sommets. Comme une capacité d'un milliard tient en dix chiffres d'entrée, le temps d'exécution est exponentiel en la taille de l'entrée. Edmonds-Karp corrige cela en choisissant toujours un plus court chemin augmentant, ce qui supprime entièrement la dépendance aux capacités.

Deux autres faits rapportent des points. Intégralité : si toutes les capacités sont entières, il existe un flot maximal entier, ce qui justifie les réductions au couplage et aux chemins disjoints. Et le coût de la réduction : quand vous construisez un réseau à partir d'une histoire, exprimez la complexité en fonction du réseau construit, et non de l'entrée d'origine. Un couplage biparti sur n personnes et m postes construit un graphe à n + m + 2 sommets, et le dire montre que vous comprenez la transformation.

13. Les erreurs qui font échouer l'entretien

Oublier les arêtes inverses. Le bogue fatal le plus courant, et il ne fait pas planter le programme : il renvoie simplement un nombre trop petit. Si vous ne savez pas expliquer pourquoi un algorithme doit pouvoir annuler ses propres décisions antérieures, vous n'avez pas compris l'algorithme.

Réutiliser l'objet solveur. Appeler max_flow une seconde fois sur la même instance renvoie 0, car le graphe résiduel est déjà saturé. Cela piège ceux qui calculent un flot, veulent de nouveau la valeur pour l'afficher et concluent que leur code est cassé. Créez un nouvel objet, ou mettez le résultat en cache.

Donner la valeur quand on demande l'ensemble. « Quels liens couperiez-vous ? » ne se répond pas par « 16 ». Retrouvez l'ensemble atteignable et listez les arêtes.

Lire une borne inférieure comme une capacité. « Au plus trois services » est une capacité. « Au moins deux services » n'en est pas une, et exige une autre construction. Guettez « doit » et « au moins ».

Modéliser des limites de sommet comme des limites d'arête. Si la contrainte porte sur une machine plutôt que sur un lien, dédoublez le sommet. Les candidats qui sautent cette étape obtiennent une réponse silencieusement trop grande.

Citer Ford-Fulkerson comme complexité. C'est la seule borne qui peut être exponentielle en la taille de l'entrée. Nommez Dinic et expliquez la différence.

Recourir au flot quand le problème n'est pas un problème de flot. Le flot maximal est le mauvais outil pour les plus courts chemins, les arbres couvrants, et tout ce dont la réponse est une seule route plutôt qu'une quantité partagée. Si rien n'est réparti ni partagé, regardez d'abord BFS, Dijkstra ou union-find. Un candidat qui saisit le marteau le plus lourd de la boîte en dit long au recruteur.

Modéliser en silence. La réduction, c'est la réponse. Dessinez le réseau au tableau, dites « la source vers chaque ingénieur avec une capacité de un, parce que personne ne peut prendre deux postes », et laissez le recruteur corriger le modèle avant d'avoir écrit trente lignes sur le mauvais.

15. Références

Les résultats derrière ces questions, par ordre chronologique.

1. Menger, K. (1927). “Zur allgemeinen Kurventheorie.” Fundamenta Mathematicae, 10, 96–115.
2. König, D. (1931). “Gráfok és mátrixok.” Matematikai és Fizikai Lapok, 38, 116–119.
3. Hall, P. (1935). “On representatives of subsets.” Journal of the London Mathematical Society, 10(1), 26–30.
4. Ford, L. R. et Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
5. Ford, L. R. et Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
6. Schwartz, B. L. (1966). “Possible winners in partially completed tournaments.” SIAM Review, 8(3), 302–308.
7. Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in networks with power estimation.” Soviet Mathematics Doklady, 11, 1277–1280.
8. Edmonds, J. et Karp, R. M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems.” Journal of the ACM, 19(2), 248–264.
9. Hopcroft, J. E. et Karp, R. M. (1973). “An n^5/2 algorithm for maximum matchings in bipartite graphs.” SIAM Journal on Computing, 2(4), 225–231.
10. Picard, J.-C. (1976). “Maximal closure of a graph and applications to combinatorial problems.” Management Science, 22(11), 1268–1272.
11. Goldberg, A. V. et Tarjan, R. E. (1988). “A new approach to the maximum-flow problem.” Journal of the ACM, 35(4), 921–940.
12. Ahuja, R. K., Magnanti, T. L. et Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
13. Wayne, K. D. (2001). “A new property and a faster algorithm for baseball elimination.” SIAM Journal on Discrete Mathematics, 14(2), 223–229.
14. Kleinberg, J. et Tardos, É. (2005). Algorithm Design, chapitre 7. Addison-Wesley.
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition, chapitre 26. MIT Press.