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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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
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, ''permutation graphs, interval graphs'', and trees.
in polynomial time on, for example, AT-free graphs, ''permutation graphs, interval graphs'', and trees.
==See also==
==See also==
*''<math>k</math>-restricted total dominating number''.
*''<math>k</math>-restricted total dominating number''.

Текущая версия от 13:22, 25 марта 2012

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.