Dominating set: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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
12

правок

Навигация