4625
правок
K-Cocomparability ordering: различия между версиями
Материал из WikiGrapp
K-Cocomparability ordering (посмотреть исходный код)
Версия от 19:04, 12 ноября 2013
, 12 ноября 2013нет описания правки
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. | |||
