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

Dominating set (посмотреть исходный код)

1 байт убрано , 25 марта 2012

нет описания правки

12

правок

@@ Строка 28: / Строка 28: @@
 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>
-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