Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Ensemble dominant
Résumé
En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donné G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.
Un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête commune avec un sommet de D.
Le problème de l'ensemble dominant est de déterminer si étant donné G et un entier naturel k, G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.
L'ensemble S de tous les sommets est dominant.
Un code identifiant d'un graphe est un sous-ensemble C de sommets de G qui est à la fois un code couvrant et un code séparateur. Ce sous-ensemble C est appelé un code identifiant de G. Tous les sommets du graphe G sont donc couverts et séparés. On appelle pour chaque sommet v ensemble identifiant l’ensemble . On notera cet ensemble
ou .
On a donc C qui est un code identifiant de G si et seulement si l’application :
est une injection dont l’image ne contient pas l’ensemble vide.
Le problème de décision de l'ensemble dominant a été prouvé NP-complet par réduction avec le problème de couverture par sommets. Les deux problèmes sont similaires, la différence étant que le premier concerne des arcs alors que le second concerne les sommets.
Le problème de l'ensemble dominant est utilisé lui-même pour montrer la difficulté d'autres problèmes, comme le problème k-centre métrique.
Soit une instance du problème de couverture de sommets. On construit (cf figure ci-contre) un nouveau graphe G' , en ajoutant à G de nouveaux sommets, pour représenter les arcs du graphe initial G. Précisément, pour tout arc de G, ajoutons un sommet vw et les arcs et .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.