12
правок
Dominating set: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) Нет описания правки |
AlexM (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 28: | Строка 28: | ||
A '''dominating set of a digraph''' <math>\vec{G}</math> is a set <math>S</math> of vertices | A '''dominating set of a digraph''' <math>\vec{G}</math> is a set <math>S</math> of vertices | ||
such that for every vertex <math>v \not \in S</math> there exists some <math>u \in S</math> | such that for every vertex <math>v \not \in S</math> there exists some <math>u \in S</math> | ||
with <math>(u,v) \in E(\vec{G})</math>. The '''domination number <math>\gamma(\vec{G})</math> of <math>\vec{G}</math> | with <math>(u,v) \in E(\vec{G})</math>. The '''domination number <math>\gamma(\vec{G})</math> of <math>\vec{G}</math>''' is defined as the cardinality of the smallest dominating set. | ||
The dominating set problem is ''NP''-complete on arbitrary graphs. It is | The dominating set problem is ''NP''-complete on arbitrary graphs. It is | ||
also ''NP'-complete on several classes of graphs, including planar | also ''NP''-complete on several classes of graphs, including planar | ||
graphs, bipartite graphs and ''chordal'' graphs. The problem can be solved | graphs, bipartite graphs and ''chordal'' graphs. The problem can be solved | ||
in polynomial time on, for example, AT-free graphs, ''permutation graphs, interval graphs'', and trees. | in polynomial time on, for example, AT-free graphs, ''permutation graphs, interval graphs'', and trees. | ||
==See also== | ==See also== | ||
*''<math>k</math>-restricted total dominating number''. | *''<math>k</math>-restricted total dominating number''. | ||
