Algorithme de Stoer-Wagner

Pour les articles homonymes, voir Wagner.

En théorie des graphes, l'algorithme de Stoer-Wagner est un algorithme récursif déterministe pour trouver la coupe minimale dans des graphes non orientés pondérés, avec des poids positifs. Autrement dit, il s'agit de séparer le graphe en deux morceaux non vides, de telle sorte que la somme des poids attribués aux arêtes reliant un sommet d'un des morceaux à un sommet de l'autre soit la plus petite possible. L'algorithme a été proposé en 1994 par Mechthild Stoer et Frank Wagner lors d'un symposium européen à Utrecht^[2],[3]. L'idée essentielle est de réduire progressivement la taille du graphe à considérer, en fusionnant des sommets par paire, jusqu'à ce que le graphe ne contienne que deux ensembles de sommets combinés^[4]. À chaque étape, l'algorithme choisit deux sommets ${\displaystyle s}$ et ${\displaystyle t}$, calcule la coupe minimale qui les sépare, puis (récursivement) la coupe minimale du graphe obtenu en les fusionnant, et renvoie le minimum des deux.