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 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[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èmes de la coupe minimum et de la coupe maximum[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.

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

Autre problème[modifier | modifier le code]

Un autre problème classique est celui de la coupe la moins dense (sparsest cut)[3]. 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[4]. Le problème consiste à trouver une coupe de plus petite densité.

Bibliographie[modifier | modifier le code]

  • (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, Plenum,‎ (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)
  3. Voir (en) Vijay Vazirani, Approximation algorithms, Springer Verlag,‎ 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 21 (« Sparsest Cut »)
  4. Yury Makarychev, « Sparsest Cut: Computational and Metric Geometry », sur Université de Chicago.