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

## Propriétés combinatoires
### 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.

### Dénombrement

Il y a au plus ${\binom {n}{2}}={\frac {n(n-1)}{2}}$ coupes minimums dans un graphe de n sommets.
Le nombre de coupes qui sont au plus $\alpha$ plus grandes que la coupe min est dans $O\left((2n)^{2\alpha }\right)$.

## 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 $s$ et $t$ 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, 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

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.

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

### Imagerie

Un exemple est la restauration d'image définie par Greig et al. 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).
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$^,$.

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