Problème de couverture de sommets

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes et informatique théorique, le problème de couverture minimum de sommets (ou problème du transversal minimum, Vertex Cover en anglais) est un problème algorithmique classique. Il consiste, étant donné un graphe à trouver un ensemble minimum de sommets pour couvrir toutes les arêtes.

Le problème de décision associé à ce problème d'optimisation est NP-complet, et fait partie des 21 problèmes NP-complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets.

Définition[modifier | modifier le code]

Une couverture des sommets, ou transversale d'un graphe G est un ensemble C de sommets tel que chaque arête de G=(V,E) est incidente à au moins un sommet de C, ie un sous-ensemble de sommets S \subseteq V tel que pour chaque arête (u,v) de G on a u \in S ou v \in S. On dit que l'ensemble C couvre les arêtes de G. La figure suivante montre des exemples de couvertures des sommets de deux graphes (l'ensemble C est formé des sommets rouges).

Vertex-cover.svg

Une couverture minimale des sommets est une couverture des sommets de taille minimale. La figure suivante montre des exemples de couvertures minimales des sommets dans les mêmes graphes que ci-dessus.

Minimum-vertex-cover.svg

Le problème de couverture de sommets (sans poids) est le problème qui consiste à trouver une telle couverture. Dans le cas où les sommets ont des poids, le problème consiste à trouver une couverture dont la somme des poids est minimale.

Propriété de graphes[modifier | modifier le code]

Si un ensemble de sommets S est une transversale, son complément \bar S = V \setminus S est un stable (ou ensemble indépendant). Donc un graphe à n sommets a une transversale de taille k si et seulement s'il a un stable de taille n-k. On en déduit immédiatement le résultat suivant :

Théorème de Gallai (de) (1959) — Dans tout graphe G, α(G) + τ(G) = n.

où α(G) désigne la taille d'un stable maximum, τ(G) désigne la taille d'une transversale minimum et n = |V|.

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