K-Cocomparability ordering: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Cocomparability ordering''' --- <math>k</math>-косравнимое упорядочение. Let <math>G = (V,E)</math> be a graph and <math>k<…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Cocomparability ordering''' - | '''<math>\,k</math>-Cocomparability ordering''' — ''[[k-Косравнимое упорядочение|<math>\,k</math>-косравнимое упорядочение]].'' | ||
Let <math>G = (V,E)</math> be a graph and <math>k</math> a positive number. A | Let <math>\,G = (V,E)</math> be a [[graph, undirected graph, nonoriented graph|graph]] and <math>\,k</math> a positive number. A '''<math>\,k</math>-cocomparability ordering''' (or '''<math>k</math>-CCPO''') of <math>\,G</math> is an ordering of its [[vertex|vertices]] such that for every choice of vertices <math>\,u, v, w</math> we have the following: | ||
'''<math>k</math>-cocomparability ordering''' (or '''<math>k</math>-CCPO''') of <math>G</math> is an ordering of | |||
its vertices such that for every choice of vertices <math>u, v, w</math> we have the following: | |||
<math>u < v < w \wedge d(u,w) \leq k \Rightarrow d(u,v) \leq k \vee d(v,w) | :::::<math>u < v < w \wedge d(u,w) \leq k \Rightarrow d(u,v) \leq k \vee d(v,w) \leq k.</math> | ||
\leq k.</math> | |||
A graph <math>G</math> is called a '''<math>k</math>-cocomparability graph''' if it admits a | A graph <math>\,G</math> is called a '''<math>k</math>-cocomparability graph''' if it admits a | ||
<math>k</math>-CCPO. | <math>\,k</math>-CCPO. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 19:04, 12 ноября 2013
[math]\displaystyle{ \,k }[/math]-Cocomparability ordering — [math]\displaystyle{ \,k }[/math]-косравнимое упорядочение.
Let [math]\displaystyle{ \,G = (V,E) }[/math] be a graph and [math]\displaystyle{ \,k }[/math] a positive number. A [math]\displaystyle{ \,k }[/math]-cocomparability ordering (or [math]\displaystyle{ k }[/math]-CCPO) of [math]\displaystyle{ \,G }[/math] is an ordering of its vertices such that for every choice of vertices [math]\displaystyle{ \,u, v, w }[/math] we have the following:
- [math]\displaystyle{ u \lt v \lt w \wedge d(u,w) \leq k \Rightarrow d(u,v) \leq k \vee d(v,w) \leq k. }[/math]
A graph [math]\displaystyle{ \,G }[/math] is called a [math]\displaystyle{ k }[/math]-cocomparability graph if it admits a [math]\displaystyle{ \,k }[/math]-CCPO.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.