Commune · Savoirs
Ensemble dominant
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.
Sur Wikipédia
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.
Texte : Wikipédia, CC BY-SA 4.0. · Image : Miym (CC BY-SA 3.0) ·
Cartes voisines
-
★
Dominator (graph theory)
Binary relation over nodes in a control-flow graph
-
★
Théorie des graphes extrémaux
-
★
Problème de la clique
-
★
Disjoint union of graphs
Combining the vertex and edge sets of two graphs
-
C★
Combinatoire extrémale
-
★★
Hamiltonian path problem
Computational problem in graph theory