4189
правок
Dominating set: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Dominating set''' --- доминирующее множество. A set <math>S \subseteq V</math> is a '''dominating set''' of <math>G</math> if for all <math…») |
Glk (обсуждение | вклад) Нет описания правки |
||
| Строка 13: | Строка 13: | ||
called the '''independent''' ('''total'''/'''connected''') domination | called the '''independent''' ('''total'''/'''connected''') domination | ||
number of <math>G</math> and is denoted by <math>\gamma_{i}</math> | number of <math>G</math> and is denoted by <math>\gamma_{i}</math> | ||
(<math>\gamma_{t}</math>/<math>\gamma_{c} | (<math>\gamma_{t}</math>/<math>\gamma_{c}/</math>). | ||
For a vertex < | For a vertex <math>v</math> of a graph <math>G = (V,E)</math>, the '''domination number''' <math>\gamma_{v}(G)</math> '''of <math>G</math> relative to''' <math>v</math> is the minimum cardinality of a dominating set in <math>G</math> that contains <math>v</math>. The '''average domination number''' of <math>G</math> is | ||
dominating set in < | |||
number''' of < | |||
<math>\gamma_{av}(G) = \frac{1}{|V|}\sum_{v \in V} \gamma_{v}(G).</math> | |||
A '''dominating set of a digraph''' < | The '''independent domination number''' <math>i_{v}(G)</math> '''of <math>G</math> relative to''' | ||
<math>v</math> is the minimum cardinality of a maximal independent set in | |||
<math>G</math> that contains <math>v</math>. The '''average independent domination number''' | |||
of <math>G</math> is | |||
<math>i_{av}(G) = \frac{1}{|V|} \sum_{v \in V} i_{v}(G).</math> | |||
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 | 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. | ||
<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 | The dominating set problem is ''NP''-complete on arbitrary graphs. It is | ||
also ''NP' | 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, | in polynomial time on, for example, AT-free graphs, ''permutation graphs, interval graphs'', and trees. | ||
graphs, interval graphs, and trees. | |||
==See also== | ==See also== | ||
*''<math>k</math>-restricted total dominating number''. | *''<math>k</math>-restricted total dominating number''. | ||