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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Convex dominating set''' --- выпуклое доминирующее множество. A set <math>X \subseteq V(G)</math> is '''convex''' in <math>G</math>…»)
 
Нет описания правки
 
Строка 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.