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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Dominating set''' --- доминирующее множество. A set <math>S \subseteq V</math> is a '''dominating set''' of <math>G</math> if for all <math…»)
 
Нет описания правки
Строка 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 </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
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 </math>G<math> that contains </math>v<math>. The '''average domination
number''' of </math>G<math> is
</math>\gamma_{av}(G)  = \frac{1}{|V|}\sum_{v \in V} \gamma_{v}(G).<math>


The '''independent domination number </math>i_{v'''(G)<math> of </math>G<math> relative to
<math>\gamma_{av}(G) = \frac{1}{|V|}\sum_{v \in V} \gamma_{v}(G).</math>
</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}$ is a set <math>S</math> of vertices
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 \emph{NP'''-complete on arbitrary graphs. It is
The dominating set problem is ''NP''-complete on arbitrary graphs. It is
also ''NP''complete on several classes of graphs, including planar
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, pe\-rmuta\-tion
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.