Coupe (théorie des graphes)
# Coupe (théorie des graphes)

En théorie des graphes, une coupe d'un graphe est une partition des sommets en deux sous-ensembles. On appelle aussi coupe l'ensemble des arêtes ayant une extrémité dans chaque sous-ensemble de la partition.

Si les arêtes ont un poids, le poids de la coupe est la somme des poids respectifs des arêtes de la coupe. Sinon, c'est le nombre d'arêtes dans la coupe.

Cet objet apparaît dans la modélisation de nombreux problèmes concernant les réseaux, où l'on recherche une coupe s-t, c'est-à-dire une coupe séparant deux sommets s et t spécifiés.

## Problèmes algorithmiques associés

Les problèmes naturels sont de trouver une coupe s-t de poids minimum et une coupe s-t de poids maximum.

### Problèmes de la coupe minimum et de la coupe maximum

Le problème de la coupe minimum (MIN-CUT) est équivalent au problème de flot maximum, d'après le théorème flot-max/coupe-min. Il peut être résolu en temps polynomial.

Le problème de la coupe maximum (MAX-CUT) est NP-complet (il fait partie des 21 problèmes NP-complets de Karp).

### Autre problème

Un autre problème classique est celui de la coupe la moins dense (sparsest cut). On définit la densité d'une coupe comme le rapport du nombre d'arêtes de la coupe sur le nombre de nœuds dans la plus petite des deux parties de la coupe. Le problème consiste à trouver une coupe de plus petite densité.

