| dbo:abstract
|
- In graph theory, a domatic partition of a graph is a partition of into disjoint sets , ,..., such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices. The domatic number is the maximum size of a domatic partition, that is, the maximum number of disjoint dominating sets. The graph in the figure has domatic number 3. It is easy to see that the domatic number is at least 3 because we have presented a domatic partition of size 3. To see that the domatic number is at most 3, we first review a simple upper bound. (en)
- En théorie des graphes, le nombre domatique d'un graphe est son nombre maximum d'ensembles dominants disjoints deux à deux. Le problème du nombre domatique est de déterminer, en fonction d'un graphe G et d'un entier naturel k, si le nombre domatique de G est supérieur ou égal à k. C'est un problème NP-complet. (fr)
- В теории графов доматическое разбиение графа — это разбиение множества вершин на непересекающиеся множества , ,...,, такие, что каждое множество Vi является доминирующим множеством графа G. Рисунок справа показывает доматическое разбиение графа. На рисунке доминирующее множество состоит из жёлтых вершин, состоит из зелёных вершин, а состоит из синих вершин. Доматическое число — это максимальный размер доматического разбиения, то есть максимальное число непересекающихся доминирующих множеств. Граф на рисунке имеет доматическое число 3. Легко видеть, что доматическое число не меньше 3, поскольку мы представили доматическое разбиение размером 3. Чтобы понять, что доматическое число не превосходит 3, сначала рассмотрим верхние границы. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 6486 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie des graphes, le nombre domatique d'un graphe est son nombre maximum d'ensembles dominants disjoints deux à deux. Le problème du nombre domatique est de déterminer, en fonction d'un graphe G et d'un entier naturel k, si le nombre domatique de G est supérieur ou égal à k. C'est un problème NP-complet. (fr)
- In graph theory, a domatic partition of a graph is a partition of into disjoint sets , ,..., such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices. (en)
- В теории графов доматическое разбиение графа — это разбиение множества вершин на непересекающиеся множества , ,...,, такие, что каждое множество Vi является доминирующим множеством графа G. Рисунок справа показывает доматическое разбиение графа. На рисунке доминирующее множество состоит из жёлтых вершин, состоит из зелёных вершин, а состоит из синих вершин. (ru)
|
| rdfs:label
|
- Domatic number (en)
- Nombre domatique (fr)
- Доматическое число (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
