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^[1].

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

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

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

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (trad. de l'anglais), Introduction à l’algorithmique, Paris, Dunod, 2002, 2^e éd., 1 146 p. [détail de l’édition] (ISBN 2-10-003922-9)

• (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103

Notes et références

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.