Algorithme de Stoer-Wagner

En théorie des graphes, l'algorithme de Stoer-Wagner est un algorithme récursif pour trouver la coupe minimale dans des graphes pondérés non orientés avec des poids positifs, proposé par Mechthild Stoer et Frank Wagner en 1995. L'idée essentielle de cet algorithme est de réduire progressivement la taille du graphe en fusionnant des sommets par paire, jusqu'à ce que le graphe ne contienne que deux ensembles de sommets combinés. À chaque étape, l'algorithme choisit deux sommets $s$ et $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. Une coupe est une partition des sommets d’un graphe en deux sous-ensembles non-vides et $A$ et $B$. Le poids de cette coupe est alors la somme des poids des arêtes qui relient un sommet de $A$ à un sommet de $B$. Une coupe minimale est une coupe de poids minimum.

Une coupe minimale (de poids 4) d'un graphe pondéré

Algorithme de Stoer – Wagner

Algorithme général

Soit $G=(V,E,w)$ un graphe non orienté pondéré, et soit $s$ et $t$ deux sommets de $V$. Considérons alors une coupe minimale pour le graphe $G$. Dans cette coupe minimale, soit $s$ et $t$ sont dans la même partie, soit ils sont dans deux parties différentes.

Si $s$ et $t$ sont dans la même partie, alors on peut construire un graphe ${\tilde {G}}(V\backslash \{s,t\}\cup st,{\tilde {E}},{\tilde {w}})$ dans lequel on a fusionné les sommets $s$ et $t$ en un sommet $st$. Une éventuelle arête $(s,t)$ est retirée, et pour tout autre sommet $u$, on crée une arête $(u,st)$ dont le poids est la somme des poids de $(u,s)$ et de $(u,t)$ (on utilise 0 lorsqu'une arête n'existe pas). La coupe minimale de ${\tilde {G}}$ a alors exactement le même poids que la coupe minimale de $G$, et on peut repasser de l'une à l'autre (en remplaçant le sommet $st$ par les deux sommets $s$ et $t$).

On note également que dans le cas général, la coupe minimale de ${\tilde {G}}$ a le poids d'une coupe de $G$, et est donc de poids supérieur ou égal au poids d'une coupe minimale de $G$.

L'algorithme consiste alors à déterminer deux sommets $s$ et $t$ et une coupe minimale séparant $s$ et $t$, et à renvoyer le minimum entre cette coupe et la coupe minimale de ${\tilde {G}}$, calculée récursivement (${\tilde {G}}$ possède un sommet de moins que $G$, et si ${\tilde {G}}$ ne possède que deux sommets, alors la coupe minimale est obtenue trivialement en séparant ces deux sommets).

Détermination de s et t

Comme cette méthode fonctionne pour tout couple $(s,t)$, l'algorithme de Stoer-Wagner choisit un couple $(s,t)$ tel que la coupe minimale séparant $s$ et $t$ soit rapide à déterminer.

Dans un graphe $G(V,E,w)$ contenant $n$ sommets, on part d'un ensemble $A$ contenant un seul sommet quelconque, et on ajoute à $A$ successivement le sommet le plus relié à $A$ (somme des poids des arêtes de ce sommet à $A$ maximale). Si on appelle les deux derniers sommets ajoutés $s$ et $t$, alors une coupe minimale séparant $s$ et $t$ est $(V\backslash {}\{t\},\{t\})$.

Pseudo-code

CoupeMinEtape$(G,w,a)$
  $A\gets \left\{a\right\}$
  Tant que $\ A\neq V$
    Ajouter à $A$ le sommet le plus connecté à $A$
  Fin
  Retenir les deux derniers sommets s et t ajoutés à A.
  Retenir le poids de la coupe avec tous les sommets sauf t d'un côté, et t tout seul de l'autre. Cette valeur est la valeur d'une coupe minimale séparant s et t. 
  Remplacer $G$ par ${\tilde {G}}$ en fusionnant les deux sommets (s, t).

Coupe minimale $(G,w,a)$
  Tant que $|V|>1$
    Calculer CoupeMinEtape$(G,w,a)$
    Si le poids retenu est plus léger que la coupure minimale actuelle
      alors remplacer la coupure minimale actuelle par le poids retenu.