- Problème de couverture de sommets
-
En théorie des graphes, le problème de couverture minimum de sommets (ou problème du transversal minimum) est un problème NP-complet faisant 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
Un transversal (ou couverture de sommets) d'un graphe G = (V,E) est un sous-ensemble de sommets
contenant au moins une extrémité de chaque arête (c'est-à-dire, plus formellement, que pour chaque arête (u,v) de G on a 
ou 
).Le problème du transversal (Vertex Cover Problem en anglais) est un problème de décision qui consiste à savoir s'il existe une couverture de sommets qui comporte au plus k sommets. Le problème du transversal minimum est le problème d'optimisation associé, consistant donc à déterminer un transversal de cardinalité minimale.
Si un ensemble de sommets S est un transversal, son complément
est un stable (ou ensemble indépendant). Donc un graphe à n sommets a un transversal 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 (1959) — Dans tout graphe G, α(G) + τ(G) = n.
où α(G) désigne la taille d'un stable maximum, τ(G) désigne la taille d'un transversal minimum et n = | V | .
Voir aussi
Wikimedia Foundation. 2010.
