Couverture dans les graphes | NP COMPLETUDE
Correction NP COMPLÉTUDE
- Soit G un graphe G = (V, E). Nous allons construire un graphe G′ = (V ′, E′) `a partir de G tel que
— V ′ = V ∪ E ;
— E′ = E ∪ {(v, a)|v ∈ V, a ∈ E, v est extremite de l’arête a dans G
Figure 01 : Graphe G′ (les arêtes dans E ne sont pas dessinées) - Soit S une couverture de sommets du graphe G. Il faut prouver que tous les sommets du graphe sont soit voisins de S, soit dans S. Toutes les arêtes de G ont au moins un de ses extrémités dans S. Par conséquent, tous les sommets de G sont soit dans S, soit voisins de S. Comme toutes les arêtes de G ont au moins un de ses extrémités dans S, tous les sommets correspondant à une arête de G sont des voisins de S. Donc S est un ensemble dominant de G′.
- Si S′ ⊆ V, alors tous les sommets du graphe G sont soit voisins de S, soit dans S. Donc toutes les arêtes ont une de ces extrémités dans S. Donc S′ est une couverture du graphe G. Sinon, il existe un sommet a dans S′ qui n'appartient pas à V mais qui appartient à V′. Cela signifie que le sommet a représente une arête (u, v) dans G et qu'il couvre uniquement les arêtes (a, u) et (a, v) dans G′. Considérons un sous-ensemble S′′ tel que S′′ = (S′ ∩ V) ∪ {u : a = (u, v) ∧ a ∈ S′}. Remarquons que |S′′| = |S′|. Soit a ∈ S′ \ V. Comme le sommet a a les arêtes (a, u) et (a, v) dans G′, alors le sommet u couvre les mêmes arêtes. Donc S′′ est une couverture du graphe G.
- Problème de décision :
- Données : un graphe non-orienté G et un entier k.
- Question : Existe-t-il un ensemble dominant S de G tel que |S| ≤ k ?
- On peut vérifier en temps polynomial si un ensemble de sommets est un ensemble dominant et s'il est de cardinalité inférieure à k.
Supposons que nous ayons le graphe non-orienté suivant :
Dans ce graphe, les sommets sont {J, O, E, L, U}. Supposons que k = 2.
Si nous choisissons l'ensemble de sommets S = {J, E}, nous pouvons vérifier rapidement que chaque sommet non inclus dans S (U, D, L) a au moins un voisin dans S. Donc, S est un ensemble dominant. De plus, la cardinalité de S est |S| = 2, ce qui est inférieur ou égal à k = 2. Ainsi, dans cet exemple, l'ensemble de sommets S = {J, E} est à la fois un ensemble dominant et sa cardinalité est inférieure à k, ce qui répond positivement à la question. La vérification a été effectuée en temps polynomial car nous avons simplement parcouru les voisins de chaque sommet non inclus dans S pour vérifier s'ils avaient au moins un voisin dans S. Ce processus a une complexité linéaire par rapport au nombre de sommets et d'arêtes du graphe.
Ajouter un commentaire