Remove ads
En théorie des graphes et en informatique théorique, une coupe minimum (« coupe min », en anglais : minimum cut ou Min Cut) d'un graphe est une coupe contenant un nombre minimal d'arêtes. C'est un objet qui apparaît notamment dans le théorème flot-max/coupe-min et qui peut être utilisé dans différents contextes, notamment en vision artificielle.
Le problème algorithmique qui consiste à trouver une telle coupe est considéré comme facile, puisqu'il peut être résolu en temps polynomial, contrairement au problème de la coupe maximum par exemple.
Remove ads
Cas non pondéré
Étant donné un graphe, une coupe est la séparation de l'ensemble de tous les sommets en deux parties. En ce sens, une coupe est une partition de l'ensemble des sommets en deux sous-ensembles. Le cardinal de la coupe est alors le nombre d'arêtes allant d'une partie à l'autre. Une coupe est minimum si son cardinal est minimum. L'image ci-contre montre une coupe minimum. L'ensemble des sommets est séparé en deux parties : les sommets noirs et les sommets blancs. Sur l'exemple la coupe est de cardinal 2. Remarquons qu'a priori, il peut y avoir plusieurs coupes minimums, c'est-à-dire plusieurs coupes différentes mais de même cardinal : le cardinal minimum.
Plus formellement, on peut décrire une coupe comme un sous-ensemble de sommets (sur l'exemple, le sous-ensemble des sommets noirs), et le cardinal de la coupe est alors le nombre d'arêtes ayant une extrémité à l'intérieur de ce sous-ensemble et l'autre à l'extérieur.
Selon les cas, il peut ou non y avoir deux sommets s et t de spécifiés, avec la condition qu'ils doivent être de part et d'autre de la coupe ; on parle alors de s,t-coupe.
Cas pondéré
On considère souvent le cas où les arêtes ont des poids, la coupe min est alors celle qui minimise la somme des poids des arêtes de la coupe. Ces poids sont positifs : en effet, autoriser des poids négatifs rend le problème plus difficile, précisément NP-difficile car équivalent au problème de la coupe maximum[1].
Remove ads
Le théorème max-flot/coupe-min
Le théorème max-flot/coupe min stipule que le cardinal de la coupe minimum entre deux sommets est égal au flot maximum pouvant passer d'un sommet à l'autre[2].
Dénombrement
Il y a au plus coupes minimums dans un graphe de n sommets[3].
Le nombre de coupes qui sont au plus plus grandes que la coupe min est dans [4].
Remove ads
Problème algorithmique
On considère le problème d'optimisation combinatoire suivant :
- Étant donné un graphe G, trouver une coupe minimum.
que l'on transforme en le problème de décision :
- Étant donné un graphe G et un entier k, existe-t-il une coupe de cardinal au plus k ?
Algorithmes
Si deux sommets et sont précisés et qu'on recherche une coupe minimale les séparant, le problème peut se résoudre en résolvant le problème de flot maximum associé, et on peut utiliser par exemple l'algorithme d'Edmonds-Karp qui donne une complexité polynomiale. Il existe aussi des algorithmes probabilistes comme l'algorithme de Karger[1], qui sont plus simples et, pour certaines variantes, plus efficaces.
Si on cherche une coupe minimale quelconque, on peut utiliser l'algorithme de Stoer-Wagner.
Remove ads
Les coupes minimum trouvent naturellement des applications dans l'étude des réseaux réels, mais elles sont aussi des objets utiles en vision artificielle[5].
Réseaux
Les coupes minimums peuvent être interprétées comme les faiblesses d'un réseau : l'ensemble minimum de pannes pouvant déconnecter le réseau. Ainsi une coupe minimum de grande taille est signe d'une plus grande robustesse[4].
Imagerie
Un exemple est la restauration d'image définie par Greig et al[6]. On considère une image bruitée que l'on veut débruiter en utilisant seulement des pixels noirs et blancs. On définit un graphe de la manière suivante : on crée deux nœuds, s et t, puis un nœud pour chaque pixel de l'image, chacun étant lié à s, t et à un certain nombre d'autres pixels de son voisinage dans l'image. Les nœuds s et t correspondent au noir et au blanc. Les arêtes ont un poids choisi pour être cohérent avec l'image de départ et les propriétés recherchées sur la reconstruction (continuité par exemple). Une coupe minimum correspond alors à séparer les nœuds-pixels en deux classes (les noirs et les blancs) de façon optimale selon un certain critère (lié au choix du poids des arêtes)[7].
Un autre exemple est la texturisation d’images qui consiste à créer une grande image à partir d'une petite, en faisant des répétitions intelligentes[8],[9].
Autres
Les coupes minimums sont aussi utilisées pour l'analyse automatique de documents, pour les langages de programmation parallèle et en optimisation combinatoire comme sous-tâche de problème plus difficile, par exemple dans la méthode des plans sécants pour le problème du voyageur de commerce[4].
Remove ads
- (en) Yuri Boykov et Olga Veksler, « Graph cuts in vision and graphics: Theories and applications », dans Handbook of mathematical models in computer vision, Springer, (lire en ligne), p. 79-96
Remove ads
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
Remove ads