Voir la source de Coupe minimum

En [[théorie des graphes]] et en [[informatique théorique]], une '''coupe minimum''' (« coupe min », en anglais : ''{{Langue|en|minimum cut}}'' ou ''{{Langue |en|Min Cut}}'') d'un graphe est une [[coupe (théorie des graphes)|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 [[P (complexité)|temps polynomial]], contrairement au problème de la [[coupe maximum]] par exemple.

== Définition formelle ==
[[Image:Min-cut.svg|thumb|Une coupe minimum.]]

=== 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 d'un ensemble|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]]<ref name="KargerStein">
{{article|langue=en|prénom1=David R.|nom1=Karger|prénom2=Clifford|nom2=Stein|titre=A new approach to the minimum cut problem|périodique=Journal of the ACM|lien périodique=Journal of the ACM|volume=43|numéro=4|passage=601|année=1996|doi=10.1145/234533.234534|lire en ligne=http://www.columbia.edu/~cs2035/courses/ieor6614.S09/Contraction.pdf}}</ref>.

== Propriétés combinatoires ==
=== Le théorème max-flot/coupe-min ===
{{article détaillé|Théorème flot-max/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<ref>Voir par exemple {{Cormen2fr}} chap. 26.</ref>.

=== Dénombrement ===

Il y a au plus <math> \binom{n}{2} = \frac{n (n-1)}{2} </math> coupes minimums dans un graphe de n sommets<ref>
{{chapitre
 | titre chapitre = On the Number of Minimum Cuts in a Graph
 | titre ouvrage = Computing and Combinatorics (COCOON 2002)
 | auteur1=L. Sunil Chandran | auteur2= L. Shankar Ram
 |année =2002
 |passage=220-229 }}</ref>.

Le nombre de coupes qui sont au plus <math>\alpha</math> plus grandes que la coupe min est dans <math>O\left((2n)^{2\alpha}\right)</math><ref name=KS96/>.

== Aspects algorithmiques ==
=== 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 <math>s</math> et <math>t</math> 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 [[algorithme probabiliste|algorithmes probabilistes]] comme l'[[algorithme de Karger]]<ref name="KargerStein" />, qui sont plus simples et, pour certaines variantes, plus efficaces.

Si on cherche une coupe minimale quelconque, on peut utiliser [[Algorithme de Stoer-Wagner|l'algorithme de Stoer-Wagner]].

== Applications ==

Les coupes minimum trouvent naturellement des applications dans l'étude des réseaux réels, mais elles sont aussi des objets utiles en [[Vision par ordinateur|vision artificielle]]<ref>{{harv|Boykov|Veksler|2006}}</ref>.

=== 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<ref name=KS96> {{harv|Karger|Stein|1996}}</ref>. 

=== Imagerie ===
Un exemple est la [[Restauration (image)|restauration d'image]] définie par Greig ''et al''<ref>
{{article | langue=en
 | nom1 = Greig | prénom1 = D. M. 
 | nom2 = Porteous | prénom2 = B. T. 
 | nom3 =  Seheult | prénom3 = Allan H.
 | titre=Exact maximum a posteriori estimation for binary images
 | périodique = Journal of the Royal Statistical Society. Series B (Methodological)
 | passage=271-279
 | année=1989
 | lire en ligne = http://www.csd.uoc.gr/~hy576/bibliography/ExactMAP_Binary.pdf
}}.</ref>. On considère une image bruitée que l'on veut débruiter en utilisant seulement des [[pixel|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)<ref> Pour une explication plus détaillée mais plus synthétique que l'article, voir {{harv|Boykov|Veksler|2006}} 3.1.</ref>.

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<ref>Mentionner à la fin de : {{lien web|url=http://images.math.cnrs.fr/Au-feu-les-pompiers.html#1|titre=Au feu les pompiers|site = [[Images des Maths]]|auteur=Xavier Caruso et Lionel Fourquaux}}.</ref>{{,}}<ref>
{{chapitre
 | titre chapitre=Graphcut textures: image and video synthesis using graph cuts
 | auteur1= Vivek Kwatra |auteur2= Arno Schödl |auteur3= Irfan Essa | auteur4= Greg Turk | auteur5= Aaron  Bobick
 | titre ouvrage=ACM Transactions on Graphics (ToG)
 | volume=22 | numéro=3 | passage=277-286
 | année=2003
 | lire en ligne=http://www.cc.gatech.edu/~turk/my_papers/graph_cuts.pdf
}}.</ref>.

=== 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]]<ref name=KS96/>.

== Bibliographie ==
* {{chapitre | langue=en
 | titre chapitre = Graph cuts in vision and graphics: Theories and applications
 | nom1 = Boykov | prénom1 = Yuri 
 | nom2 = Veksler | prénom2 = Olga
 | titre ouvrage = Handbook of mathematical models in computer vision
 | passage = 79-96
 | année = 2006
 | éditeur = Springer
 | lire en ligne = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.1106&rep=rep1&type=pdf
}}

== Notes et références ==
<references />

{{Portail|informatique théorique|mathématiques}}

[[Catégorie:Concept en théorie des graphes]]
[[Catégorie:Réseau de flot]]