Algorithme de Stoer-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.

Une coupe minimale (de poids 4) d'un graphe pondéré^[1]

Principe de l'algorithme de Stoer – Wagner

On considère un graphe non orienté pondéré ${\displaystyle G=(V,E,w)}$ : ${\displaystyle V}$ est l'ensemble des sommets, ${\displaystyle E}$ celui des arêtes entre les sommets et ${\displaystyle w}$ la fonction de valuation qui associe des nombres (les « poids ») aux arêtes. Une coupe est une partition des sommets du graphe en deux parties, deux sous-ensembles non-vides ${\displaystyle A}$ et ${\displaystyle B}$. Le poids de cette coupe est alors la somme des poids des arêtes qui relient un sommet de ${\displaystyle A}$ à un sommet de ${\displaystyle B}$. Une coupe minimale est une coupe de poids minimum ; elle n'est pas unique en général.

Considérons alors deux sommets quelconques, ${\displaystyle s}$ et ${\displaystyle t}$, de ${\displaystyle V}$. L'algorithme repose sur l'alternative suivante : soit une coupe minimale sépare ${\displaystyle s}$ et ${\displaystyle t}$ (c'est-à-dire que les deux sommets ne sont pas dans la même partie de la coupe), soit on peut l'obtenir à partir d'une coupe minimale d'un graphe ayant moins de sommets que le graphe initial.

Si en effet ${\displaystyle s}$ et ${\displaystyle t}$ sont dans la même partie, alors on peut construire un graphe ${\displaystyle {\tilde {G}}(V\backslash \{s,t\}\cup st,{\tilde {E}},{\tilde {w}})}$ dans lequel on a fusionné les sommets ${\displaystyle s}$ et ${\displaystyle t}$ en un seul sommet ${\displaystyle st}$. S'il y avait une arête ${\displaystyle (s,t)}$ entre ${\displaystyle s}$ et ${\displaystyle t}$ dans le graphe initial, elle est retirée ; pour tout autre sommet ${\displaystyle u}$, on crée une arête du nouveau graphe, ${\displaystyle (u,st)}$, entre le sommet ${\displaystyle u}$ et le nouveau sommet ${\displaystyle st}$ ; on attribue à cette arête un poids qui est la somme des poids des arêtes ${\displaystyle (u,s)}$ et de ${\displaystyle (u,t)}$ entre les sommets ${\displaystyle u}$ et ${\displaystyle s}$, ou ${\displaystyle u}$ et ${\displaystyle t}$, du graphe initial (on utilise 0 lorsqu'il n'existait pas d'arête entre ces sommets). La coupe minimale de ${\displaystyle {\tilde {G}}}$ a alors exactement le même poids que la coupe minimale du graphe initial ${\displaystyle G}$, et on peut repasser de l'une à l'autre (en remplaçant le sommet ${\displaystyle st}$ par les deux sommets ${\displaystyle s}$ et ${\displaystyle t}$)^[4].

On note également que, dans le cas général, la coupe minimale de ${\displaystyle {\tilde {G}}}$ a le même poids qu'une certaine coupe de ${\displaystyle G}$ ; ce poids est donc supérieur ou égal au poids d'une coupe minimale de ${\displaystyle G}$. Le graphe ${\displaystyle {\tilde {G}}}$ possède un sommet de moins que le graphe ${\displaystyle G}$. Par ailleurs, si ${\displaystyle {\tilde {G}}}$ ne possède que deux sommets, alors sa coupe minimale est obtenue trivialement en séparant ces deux sommets.

L'algorithme consiste alors à déterminer deux sommets ${\displaystyle s}$ et ${\displaystyle t}$ et une coupe minimale séparant ${\displaystyle s}$ et ${\displaystyle t}$, et à stocker le minimum entre cette coupe et la coupe minimale de ${\displaystyle {\tilde {G}}}$, calculée récursivement^[4].

Détermination de s et t

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

Stoer et Wagner proposent d'initialiser le processus avec un ensemble ${\displaystyle A}$ composé d'un seul sommet quelconque ${\displaystyle a}$, par exemple de plus grand poids total, puis d'ajouter à ${\displaystyle A}$ le sommet le plus relié à ${\displaystyle a}$ (autrement dit, tel que la somme des poids des arêtes de ce sommet à ${\displaystyle a}$ soit maximale), puis le sommet le plus relié aux sommets déjà dans ${\displaystyle A}$, et ainsi de suite. Ils montrent que si on appelle les deux derniers sommets ajoutés ${\displaystyle s}$ et ${\displaystyle t}$, alors une coupe minimale séparant ${\displaystyle s}$ et ${\displaystyle t}$ est celle formée de tous les sommets sauf ${\displaystyle t}$ d'un côté et de ${\displaystyle t}$ de l'autre^[4].

Pseudo-code

On peut présenter le procédé ainsi^[4] :

CoupeMinEtape${\displaystyle (G,w,a)}$
  ${\displaystyle A\gets \left\{a\right\}}$
  Tant que ${\displaystyle \ A\neq V}$
    Ajouter à ${\displaystyle A}$ le sommet le plus connecté à ${\displaystyle A}$
  Fin
  Stocker les deux derniers sommets s et t ajoutés à A.
  Stocker le poids de la coupe obtenue en plaçant tous les sommets sauf t dans un ensemble de la partition, et t tout seul dans l'autre. Ce poids est la valeur d'une coupe minimale séparant s et t. 
  Remplacer ${\displaystyle G}$ par ${\displaystyle {\tilde {G}}}$ obtenu en fusionnant les deux sommets (s, t).

Coupe minimale ${\displaystyle (G,w,a)}$
  Tant que ${\displaystyle |V|>1}$
    Calculer CoupeMinEtape${\displaystyle (G,w,a)}$
    Si le poids obtenu est moindre  que celui de la coupe minimale stockée
      alors remplacer cette coupe minimale stockée par celle de poids moindre.

Complexité

Si ${\displaystyle n}$ est le nombre de sommets du graphe et ${\displaystyle m}$ le nombre d'arêtes, le temps de calcul^[3] est de l'ordre de ${\displaystyle O(nm+n^{2}\log n)}$.

Références

1. Daniel Trebbien, « Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1 », www.boost.org, 2010 (consulté le 7 décembre 2015).
2. (en) Mechthild Stoer et Frank Wagner, « A simple min-cut algorithm », dans Jan Leeuwen (ed.), Algorithms-ESA'94, Springer, coll. « Lecture Notes in Computer Science » (n^o 855), 1994, p. 141-147.
3. (en) Kurt Melhorn et Christian Uhrig, « The minimum cut algorithm of Stoer and Wagner », 27 juillet 1995.
4. (en) Mechthild Stoer et Frank Wagner, « A simple min-cut algorithm », Journal of the ACM, vol. 44, n^o 4,‎ 1997, p. 585–591 (lire en ligne).

Liens externes

• Daniel Trebbien, « Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1 », www.boost.org, 2010 (consulté le 7 décembre 2015).
• StoerWagnerMinCut.java : Implémentation en Java de l'algorithme de Stoer–Wagner.

• Portail des mathématiques
• Portail de l'informatique théorique