Convex dominating set: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Convex dominating set''' --- выпуклое доминирующее множество. A set <math>X \subseteq V(G)</math> is '''convex''' in <math>G</math>…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Convex dominating set''' | '''Convex dominating set''' — ''[[выпуклое доминирующее множество]].'' | ||
A set <math>X \subseteq V(G)</math> is '''convex''' in <math>G</math> if vertices from all | A set <math>\,X \subseteq V(G)</math> is '''convex''' in <math>\,G</math> if [[vertex|vertices]] from all <math>\,(a-b)</math>-geodesics belong to <math>\,X</math> for any two vertices <math>\,a,b \in X</math>. A set <math>\,X</math> is a '''convex dominating set''' if it is convex and | ||
<math>(a-b)</math>-geodesics belong to <math>X</math> for any two vertices <math>a,b \in X</math>. A | dominating. The '''convex domination number''' <math>\,\gamma_{con}(G)</math> of a | ||
set <math>X</math> is a '''convex dominating set''' if it is convex and | [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is the minimum cardinality of a convex dominating set in <math>\,G</math>. | ||
dominating. The '''convex domination number''' <math>\gamma_{con}(G)</math> of a | |||
graph <math>G</math> is the minimum cardinality of a convex dominating set in <math>G</math>. | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 12:24, 25 января 2017
Convex dominating set — выпуклое доминирующее множество.
A set [math]\displaystyle{ \,X \subseteq V(G) }[/math] is convex in [math]\displaystyle{ \,G }[/math] if vertices from all [math]\displaystyle{ \,(a-b) }[/math]-geodesics belong to [math]\displaystyle{ \,X }[/math] for any two vertices [math]\displaystyle{ \,a,b \in X }[/math]. A set [math]\displaystyle{ \,X }[/math] is a convex dominating set if it is convex and dominating. The convex domination number [math]\displaystyle{ \,\gamma_{con}(G) }[/math] of a graph [math]\displaystyle{ \,G }[/math] is the minimum cardinality of a convex dominating set in [math]\displaystyle{ \,G }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.