Coupe minimum
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.
Définition formelle
[modifier | modifier le code]Cas non pondéré
[modifier | modifier le code]É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é
[modifier | modifier le code]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].
Propriétés combinatoires
[modifier | modifier le code]Le théorème max-flot/coupe-min
[modifier | modifier le code]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
[modifier | modifier le code]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].
Aspects algorithmiques
[modifier | modifier le code]Problème algorithmique
[modifier | modifier le code]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
[modifier | modifier le code]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.
Applications
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]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].
Bibliographie
[modifier | modifier le code]- (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
Notes et références
[modifier | modifier le code]- (en) David R. Karger et Clifford Stein, « A new approach to the minimum cut problem », Journal of the ACM, vol. 43, no 4, , p. 601 (DOI 10.1145/234533.234534, lire en ligne)
- Voir par exemple Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition] chap. 26.
- L. Sunil Chandran et L. Shankar Ram, « On the Number of Minimum Cuts in a Graph », dans Computing and Combinatorics (COCOON 2002), , p. 220-229
- (Karger et Stein 1996)
- (Boykov et Veksler 2006)
- (en) D. M. Greig, B. T. Porteous et Allan H. Seheult, « Exact maximum a posteriori estimation for binary images », Journal of the Royal Statistical Society. Series B (Methodological), , p. 271-279 (lire en ligne).
- Pour une explication plus détaillée mais plus synthétique que l'article, voir (Boykov et Veksler 2006) 3.1.
- Mentionner à la fin de : Xavier Caruso et Lionel Fourquaux, « Au feu les pompiers », sur Images des Maths.
- Vivek Kwatra, Arno Schödl, Irfan Essa, Greg Turk et Aaron Bobick, « Graphcut textures: image and video synthesis using graph cuts », dans ACM Transactions on Graphics (ToG), vol. 22, (lire en ligne), chap. 3, p. 277-286.