This HTML5 document contains 65 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n35http://commons.dbpedia.org/resource/Category:
dbpedia-eshttp://es.dbpedia.org/resource/
n13http://g.co/kg/m/
dbpedia-hehttp://he.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-srhttp://sr.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-cshttp://cs.dbpedia.org/resource/
n4http://fr.dbpedia.org/resource/Modèle:
n23http://fr.dbpedia.org/resource/Fichier:
wikipedia-frhttp://fr.wikipedia.org/wiki/
n26http://commons.wikimedia.org/wiki/Special:FilePath/
n32http://fr.dbpedia.org/resource/Modèle:Traduction/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n27http://www.nada.kth.se/~viggo/wwwcompendium/
owlhttp://www.w3.org/2002/07/owl#
n21http://ma-graph.org/entity/
n17https://commons.wikimedia.org/wiki/Category:
n34https://id.loc.gov/authorities/names/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
dbpedia-nlhttp://nl.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Ensemble_dominant
rdfs:label
Zbiór dominujący Ensemble dominant Conjunto dominante Домінівна множина Dominating set
rdfs:comment
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és G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.
rdfs:seeAlso
n17:Dominating_set_(graph_theory)
owl:sameAs
dbpedia-he:קבוצה_שולטת wikidata:Q2915204 n13:05sv8d dbpedia-sr:Доминантни_скуп dbpedia-ja:支配集合問題 dbpedia-cs:Dominance_(graf) dbpedia-es:Conjunto_dominante dbpedia-uk:Домінівна_множина n21:146661039 dbpedia-pt:Conjunto_dominante dbr:Dominating_set dbpedia-pl:Zbiór_dominujący dbpedia-nl:Dominerende_verzameling dbpedia-ru:Доминирующее_множество dbpedia-de:Dominierende_Menge dbpedia-fa:مجموعه_چیره n34:sh97008149 n35:Dominating_set_(graph_theory)
dbo:wikiPageID
1118533
dbo:wikiPageRevisionID
170507788
dbo:wikiPageWikiLink
category-fr:Concept_en_théorie_des_graphes dbpedia-fr:Inclusion_(mathématiques) dbpedia-fr:Théorie_des_graphes dbpedia-fr:David_S._Johnson dbpedia-fr:Michael_Garey dbpedia-fr:Entier_naturel dbpedia-fr:Mihalis_Yannakakis dbpedia-fr:Réduction_polynomiale dbpedia-fr:Algorithme_d'approximation n23:Dominating-set.svg n23:ReductionVCtoDS.svg dbpedia-fr:Code_identifiant_d'un_graphe dbpedia-fr:Problème_NP-complet dbpedia-fr:Problème_de_décision dbpedia-fr:Problème_de_couverture_par_ensembles dbpedia-fr:Problème_de_couverture_par_sommets dbpedia-fr:Problème_algorithmique dbpedia-fr:K-centre category-fr:Problème_NP-complet
dbo:wikiPageExternalLink
n27:node11.html
dbo:wikiPageLength
5495
dct:subject
category-fr:Concept_en_théorie_des_graphes category-fr:Problème_NP-complet
prop-fr:wikiPageUsesTemplate
n4:Lien n4:Pas_clair n4:Portail n4:ISBN n4:... n32:Référence n4:En
prov:wasDerivedFrom
wikipedia-fr:Ensemble_dominant?oldid=170507788&ns=0
foaf:depiction
n26:ReductionVCtoDS.svg n26:Dominating-set.svg
prop-fr:fr
Computers and Intractability
prop-fr:langue
en
dbo:thumbnail
n26:Dominating-set.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Ensemble_dominant
dbo:abstract
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és G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.