Calculateur de Coupe Minimale

Pseudocode

La coupe minimale ne se calcule pas directement. On calcule un flot maximal, puis on lit la coupe dans le graphe résiduel en un seul parcours.

CoupeMinimale(graphe, s, t):
    executer un algorithme de flot maximal jusqu a saturation

    // S = tout ce qui reste atteignable depuis s
    // dans le graphe RESIDUEL
    S = BFS/DFS depuis s en n empruntant que les aretes
        de capacite residuelle > 0
    T = tous les sommets restants

    coupe = { (u,v) parmi les aretes originales :
              u dans S et v dans T }
    renvoyer coupe et la somme de ses capacites originales

Deux faits font fonctionner cela. Toute arête traversant de S vers T doit être saturée, sinon sa capacité résiduelle serait positive et son extrémité aurait été atteignable, la plaçant dans S. Et toute arête de T revenant vers S ne transporte aucun flot. Le flot traversant la coupe égale donc exactement la capacité de la coupe, et puisqu'aucun flot ne peut dépasser une coupe quelconque, les deux doivent être optimaux.

Exemple détaillé, étape par étape

Trouve la coupe minimale sur le réseau déjà utilisé pour le flot maximal, en lisant le graphe résiduel une fois le flot saturé.

Graphe d'exemple: Capacités orientées S vers A (10), S vers B (10), A vers B (2), A vers T (4), B vers T (9).

1. Calculer le flot maximal. Augmenter le long de S vers A vers T pousse 4, et le long de S vers B vers T pousse 9. Le flot total vaut 13 et il ne reste aucun chemin augmentant.
2. Regarder le graphe résiduel. S-A dispose de 10 - 4 = 6 de marge. S-B dispose de 10 - 9 = 1. A-B est intacte, ses 2 subsistent donc. A-T et B-T sont toutes deux entièrement saturées, avec 0 de marge.
3. Trouver S par un parcours. Pars de S. L'arête S-A possède de la marge, donc A rejoint S. Depuis A, l'arête A-B possède de la marge, donc B rejoint S. Depuis B, l'unique arête sortante B-T est saturée. Rien d'autre n'est atteignable, S est donc l'ensemble {S, A, B}.
4. Lire la coupe. T est l'ensemble de sommets restant, à savoir simplement {T}. Les arêtes originales allant de S vers T sont A-T de capacité 4 et B-T de capacité 9.
5. Vérifier. La capacité de la coupe vaut 4 + 9 = 13, exactement le flot maximal. Retirer ces deux arêtes rend T inatteignable depuis S, ce qui confirme qu'il s'agit d'une véritable coupe.

La coupe minimale est la paire d'arêtes A-T et B-T de capacité totale 13, égale au flot maximal de 13. Note que S-A et S-B totalisent une capacité de 20 et forment également une coupe, mais plus coûteuse. Le goulot d'étranglement se situe du côté du puits, et le parcours du résiduel le trouve sans avoir à explorer des coupes candidates.

Complexité et son origine

Temps: identique à l'algorithme de flot maximal utilisé · Espace: O(V + E)

L'extraction de la coupe elle-même est un unique parcours de graphe en O(V + E), donc négligeable. Tout le coût réside dans le calcul de flot maximal qui la précède: O(V fois E au carré) avec Edmonds-Karp, ou O(V au carré fois E) avec Dinic. Cela mérite d'être dit clairement, car cela explique pourquoi la coupe minimale n'est pas traitée comme un problème distinct. On ne connaît aucun moyen de trouver la coupe minimale s-t asymptotiquement plus vite que de calculer le flot maximal, puisque d'après le théorème flot-max coupe-min les deux sont le même calcul vu de deux côtés opposés.

Quand utiliser Coupe Minimum, et quand l'éviter

Le mot coupe recouvre plusieurs problèmes réellement distincts. Choisir le mauvais est ici l'erreur la plus fréquente.

Pièges fréquents

• Parcourir le graphe original au lieu du résiduel. La coupe se définit par ce qui est atteignable via la capacité restante, pas par les arêtes originales. Lancer le parcours sur le graphe original atteint généralement le puits et ne produit aucune coupe. C'est l'erreur d'implémentation la plus courante.
• Confondre coupe minimale s-t et coupe minimale globale. La coupe s-t sépare deux sommets choisis. La coupe minimale globale partage le graphe en deux parties non vides quelconques et nécessite Stoer-Wagner ou Karger. Résoudre le mauvais problème donne une réponse valide à une question que personne n'a posée.
• Supposer que la coupe minimale est unique. Sa capacité est unique; l'ensemble d'arêtes souvent non. Plusieurs coupes distinctes peuvent partager la capacité minimale, et celle que tu obtiens dépend du flot trouvé. Les tests doivent vérifier la capacité, pas une liste d'arêtes précise.
• Compter les arêtes allant de T vers S. Seules les arêtes allant du côté S vers le côté T comptent dans la capacité de la coupe. Les arêtes inverses ne transportent aucun flot à travers la coupe et n'apportent rien. Les inclure gonfle la réponse au-delà du flot maximal et casse le théorème.
• Oublier que les capacités doivent être positives ou nulles. La correspondance flot-max coupe-min suppose des capacités positives ou nulles. Une capacité négative n'est pas une notion de débit sensée, et le raisonnement sur le résiduel s'effondre sans elle.

Questions fréquentes

Qu'est-ce qu'une coupe minimale dans un graphe?

Une coupe est une partition des sommets en deux ensembles, l'un contenant la source et l'autre le puits, et sa capacité est la capacité totale des arêtes traversant du côté source vers le côté puits. La coupe minimale est la partition la moins chère, ce qui identifie le goulot d'étranglement: l'ensemble d'arêtes le moins coûteux à retirer pour déconnecter la source du puits.

Comment trouve-t-on la coupe minimale?

Calcule le flot maximal, puis lance un BFS ou un DFS depuis la source dans le graphe résiduel, en ne suivant que les arêtes disposant encore de marge. Les sommets atteints forment un côté de la coupe, les autres forment l'autre, et les arêtes originales qui les traversent constituent la coupe minimale.

Que dit le théorème flot-max coupe-min?

Il énonce que le flot maximal de la source au puits égale toujours la capacité de la coupe minimale qui les sépare. Aucun flot ne peut dépasser une coupe puisque tout doit la traverser, et lorsqu'il ne reste aucun chemin augmentant, l'ensemble atteignable dans le résiduel définit une coupe dont le flot atteint exactement la capacité, si bien que les deux valeurs coïncident.

Quelle est la différence entre coupe minimale et coupe minimale globale?

Une coupe minimale s-t sépare deux sommets spécifiés et se trouve via le flot maximal. Une coupe minimale globale partage le graphe en deux parties non vides quelconques sans désigner de sommets à l'avance, et se trouve avec Stoer-Wagner ou Karger. Une coupe globale peut être bien moins chère que n'importe quelle coupe s-t particulière.

À quoi sert la coupe minimale?

À identifier les vulnérabilités de réseau et les points uniques de défaillance, à la segmentation d'images où les pixels sont des sommets et la coupe sépare le premier plan du fond, au regroupement et à la détection de communautés, aux problèmes de sélection de projets, et à l'analyse de fiabilité des infrastructures de communication ou de transport.