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 classique, 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 formelleModifier

 
Une coupe minimum.

Une coupe peut être décrite comme un ensemble de sommets, et le cardinal de la coupe est alors le nombre d'arêtes ayant une extrémité à l'intérieur de cet ensemble et l'autre à l'extérieur. Une coupe est minimum si son cardinal est minimum. 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.

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.

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 combinatoiresModifier

Le théorème max-flot/coupe-minModifier

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énombrementModifier

Il y a au plus   coupes minimums dans un graphe[3].

Le nombre de coupes qui sont au plus   plus grandes que la coupe min est dans  [4].

Aspects algorithmiquesModifier

Problème algorithmiqueModifier

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 ?

AlgorithmesModifier

Grâce au théorème flot-max/coupe-min, le problème peut se résoudre en résolvant le problème de flot maximum associé. On obtient donc une complexité polynomiale, grâce à l'algorithme d'Edmonds-Karp par exemple. Il existe aussi des algorithmes probabilistes comme l'algorithme de Karger[1], qui sont plus simples et, pour certaines variantes, plus efficaces.

ApplicationsModifier

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éseauxModifier

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].

ImagerieModifier

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].

AutresModifier

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].

BibliographieModifier

  • (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érencesModifier

  1. a et b (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)
  2. 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.
  3. 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
  4. a b et c (Karger et Stein 1996)
  5. (Boykov et Veksler 2006)
  6. (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).
  7. Pour une explication plus détaillée mais plus synthétique que l'article, voir (Boykov et Veksler 2006) 3.1.
  8. Mentionner à la fin de : Xavier Caruso et Lionel Fourquaux, « Au feu les pompiers », sur Images des Maths.
  9. 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.