M-Convex set in G

Материал из WikiGrapp

[math]\displaystyle{ \,m }[/math]-Convex set in [math]\displaystyle{ \,G }[/math][math]\displaystyle{ \,m }[/math]-выпуклое множество в графе [math]\displaystyle{ \,G }[/math].

A path [math]\displaystyle{ \,P }[/math] in [math]\displaystyle{ \,G }[/math] is called [math]\displaystyle{ \,m }[/math]-path if the graph induced by the vertex set [math]\displaystyle{ \,V(P) }[/math] of [math]\displaystyle{ \,P }[/math] is [math]\displaystyle{ \,P }[/math]. A subset [math]\displaystyle{ \,C }[/math] of [math]\displaystyle{ \,V(G) }[/math] is said to be [math]\displaystyle{ m }[/math]-convex set if, for every pair of vertices [math]\displaystyle{ \,x, y \in C }[/math], the vertex set of every [math]\displaystyle{ \,x - y }[/math] [math]\displaystyle{ \,m }[/math]-path is contained in [math]\displaystyle{ \,C }[/math]. The cardinality of a maximal proper [math]\displaystyle{ \,m }[/math]-convex set in [math]\displaystyle{ \,G }[/math] is the [math]\displaystyle{ \,m }[/math]-convexity number of [math]\displaystyle{ \,G }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.