Coupe (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir coupe.

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 des poids, le poids de la coupe est la somme des poids 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 dans de 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[1].

Problèmes algorithmiques associés[modifier | modifier le code]

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

Problème de la coupe minimum[modifier | modifier le code]

Article détaillé : Coupe minimum.
Une coupe minimum

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.

Problème de la coupe maximum[modifier | modifier le code]

Article détaillé : Coupe maximum.

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

Bibliographie[modifier | modifier le code]

  • (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, Plenum,‎ 1972 (lire en ligne), p. 85-103

Notes et références[modifier | modifier le code]

  1. (Cormen et al. 2002), notes introductives du chapitre 26.
  2. (Karp 1972)