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''. | ||
Версия от 16:26, 5 апреля 2011
Dominating set --- доминирующее множество.
A set [math]\displaystyle{ S \subseteq V }[/math] is a dominating set of [math]\displaystyle{ G }[/math] if for all [math]\displaystyle{ v \in V \setminus S }[/math] there is a vertex [math]\displaystyle{ u \in S }[/math] such that [math]\displaystyle{ (u,v) \in E(G) }[/math]. The minimum cardinality of a dominating set of [math]\displaystyle{ G }[/math] is called the domination number of [math]\displaystyle{ G }[/math]. It is well-known that determining the domination number of a graph is NPhard.
A dominating set [math]\displaystyle{ S }[/math] is called independent if the induced subgraph [math]\displaystyle{ \langle S \rangle }[/math] is empty; total if [math]\displaystyle{ \langle S \rangle }[/math] has no isolated vertex and connected if [math]\displaystyle{ \langle S \rangle }[/math] is connected. The minimum cardinality taken over all minimal independent (total/connected) dominating sets in [math]\displaystyle{ G }[/math] is called the independent (total/connected) domination number of [math]\displaystyle{ G }[/math] and is denoted by [math]\displaystyle{ \gamma_{i} }[/math] ([math]\displaystyle{ \gamma_{t} }[/math]/[math]\displaystyle{ \gamma_{c}/ }[/math]).
For a vertex [math]\displaystyle{ v }[/math] of a graph [math]\displaystyle{ G = (V,E) }[/math], the domination number [math]\displaystyle{ \gamma_{v}(G) }[/math] of [math]\displaystyle{ G }[/math] relative to [math]\displaystyle{ v }[/math] is the minimum cardinality of a dominating set in [math]\displaystyle{ G }[/math] that contains [math]\displaystyle{ v }[/math]. The average domination number of [math]\displaystyle{ G }[/math] is
[math]\displaystyle{ \gamma_{av}(G) = \frac{1}{|V|}\sum_{v \in V} \gamma_{v}(G). }[/math]
The independent domination number [math]\displaystyle{ i_{v}(G) }[/math] of [math]\displaystyle{ G }[/math] relative to [math]\displaystyle{ v }[/math] is the minimum cardinality of a maximal independent set in [math]\displaystyle{ G }[/math] that contains [math]\displaystyle{ v }[/math]. The average independent domination number of [math]\displaystyle{ G }[/math] is
[math]\displaystyle{ i_{av}(G) = \frac{1}{|V|} \sum_{v \in V} i_{v}(G). }[/math]
A dominating set of a digraph [math]\displaystyle{ \vec{G} }[/math] is a set [math]\displaystyle{ S }[/math] of vertices such that for every vertex [math]\displaystyle{ v \not \in S }[/math] there exists some [math]\displaystyle{ u \in S }[/math] with [math]\displaystyle{ (u,v) \in E(\vec{G}) }[/math]. The domination number [math]\displaystyle{ \gamma(\vec{G}) }[/math] of [math]\displaystyle{ \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 also NP'-complete on several classes of graphs, including planar 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.
See also
- [math]\displaystyle{ k }[/math]-restricted total dominating number.