Algorithme de Stoer-Wagner — Wikipédia
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Stoer_wagner-example-min-cut.gif/220px-Stoer_wagner-example-min-cut.gif)
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 et , 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.
Principe de l'algorithme de Stoer – Wagner
[modifier | modifier le code]On considère un graphe non orienté pondéré : est l'ensemble des sommets, celui des arêtes entre les sommets et 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 et . Le poids de cette coupe est alors la somme des poids des arêtes qui relient un sommet de à un sommet de . Une coupe minimale est une coupe de poids minimum ; elle n'est pas unique en général.
Considérons alors deux sommets quelconques, et , de . L'algorithme repose sur l'alternative suivante : soit une coupe minimale sépare et (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 et sont dans la même partie, alors on peut construire un graphe dans lequel on a fusionné les sommets et en un seul sommet . S'il y avait une arête entre et dans le graphe initial, elle est retirée ; pour tout autre sommet , on crée une arête du nouveau graphe, , entre le sommet et le nouveau sommet ; on attribue à cette arête un poids qui est la somme des poids des arêtes et de entre les sommets et , ou et , du graphe initial (on utilise 0 lorsqu'il n'existait pas d'arête entre ces sommets). La coupe minimale de a alors exactement le même poids que la coupe minimale du graphe initial , et on peut repasser de l'une à l'autre (en remplaçant le sommet par les deux sommets et )[4].
On note également que, dans le cas général, la coupe minimale de a le même poids qu'une certaine coupe de ; ce poids est donc supérieur ou égal au poids d'une coupe minimale de . Le graphe possède un sommet de moins que le graphe . Par ailleurs, si 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 et et une coupe minimale séparant et , et à stocker le minimum entre cette coupe et la coupe minimale de , calculée récursivement[4].
Détermination de s et t
[modifier | modifier le code]Comme cette méthode fonctionne pour tout couple , l'algorithme de Stoer-Wagner choisit un couple tel que la coupe minimale séparant et soit rapide à déterminer.
Stoer et Wagner proposent d'initialiser le processus avec un ensemble composé d'un seul sommet quelconque , par exemple de plus grand poids total, puis d'ajouter à le sommet le plus relié à (autrement dit, tel que la somme des poids des arêtes de ce sommet à soit maximale), puis le sommet le plus relié aux sommets déjà dans , et ainsi de suite. Ils montrent que si on appelle les deux derniers sommets ajoutés et , alors une coupe minimale séparant et est celle formée de tous les sommets sauf d'un côté et de de l'autre[4].
Pseudo-code
[modifier | modifier le code]On peut présenter le procédé ainsi[4] :
CoupeMinEtape Tant que Ajouter à le sommet le plus connecté à 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 par obtenu en fusionnant les deux sommets (s, t). Coupe minimale Tant que Calculer CoupeMinEtape 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é
[modifier | modifier le code]Si est le nombre de sommets du graphe et le nombre d'arêtes, le temps de calcul[3] est de l'ordre de .
Références
[modifier | modifier le code]- Daniel Trebbien, « Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1 », www.boost.org, (consulté le ).
- (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 » (no 855), , p. 141-147.
- (en) Kurt Melhorn et Christian Uhrig, « The minimum cut algorithm of Stoer and Wagner », .
- (en) Mechthild Stoer et Frank Wagner, « A simple min-cut algorithm », Journal of the ACM, vol. 44, no 4, , p. 585–591 (lire en ligne).
Liens externes
[modifier | modifier le code]- Daniel Trebbien, « Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1 », www.boost.org, (consulté le ).
- StoerWagnerMinCut.java : Implémentation en Java de l'algorithme de Stoer–Wagner.