12
правок
Dominating set: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
AlexM (обсуждение | вклад) Нет описания правки |
AlexM (обсуждение | вклад) Нет описания правки |
||
| Строка 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>} is defined as the cardinality of the smallest dominating set. | 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 | ||