M-Convex set in G: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>m</math>-Convex set in <math>G</math>''' --- <math>m</math>-выпуклое множество в графе <math>G</math>. A path <math>P</math> in <ma…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>m</math>-Convex set in <math>G</math>''' - | '''<math>\,m</math>-Convex set in <math>\,G</math>''' — ''[[m-выпуклое множество в графе G|<math>\,m</math>-выпуклое множество в графе <math>\,G</math>]].'' | ||
A path <math>P</math> in <math>G</math> is called <math>m</math>-path if the graph induced by the vertex set | A [[path]] <math>\,P</math> in <math>\,G</math> is called [[m-path|<math>\,m</math>-path]] if the [[graph, undirected graph, nonoriented graph|graph]] induced by the [[vertex]] set <math>\,V(P)</math> of <math>\,P</math> is <math>\,P</math>. A subset <math>\,C</math> of <math>\,V(G)</math> is said to be '''<math>m</math>-convex set''' if, for every pair of vertices <math>\,x, y \in C</math>, the vertex set of every <math>\,x - y</math> <math>\,m</math>-path is contained in <math>\,C</math>. The cardinality of a maximal proper <math>\,m</math>-convex set in <math>\,G</math> is the '''[[m-Convexity number|<math>\,m</math>-convexity number]]''' of <math>\,G</math>. | ||
<math>V(P)</math> of <math>P</math> is <math>P</math>. A subset <math>C</math> of <math>V(G)</math> is said to be '''<math>m</math>-convex set''' | |||
if, for every pair of vertices <math>x, y \in C</math>, the vertex set of every | ==Литература== | ||
<math>x - y</math> <math>m</math>-path is contained in <math>C</math>. The cardinality of a maximal | |||
proper <math>m</math>-convex set in <math>G</math> is the '''<math>m</math>-convexity number''' of <math>G</math>. | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
Текущая версия от 12:46, 25 января 2017
[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.