Cocomparability ordering: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Cocomparability ordering''' --- косравнимое упорядочение. A graph <math>G</math> has a '''cocomparability ordering''' if there exists a …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Cocomparability ordering''' | '''Cocomparability ordering''' — ''[[косравнимое упорядочение]].'' | ||
A graph <math>G</math> has a '''cocomparability ordering''' if there exists a | A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> has a '''cocomparability ordering''' if there exists a linear order <math>\,<</math> on the set of its [[vertex|vertices]] such that for every choice of vertices <math>\,u, v, w</math> the following property holds | ||
linear order <math><</math> on the set of its vertices such that for every choice | |||
of vertices <math>u, v, w</math> the following property holds | |||
<math>u < v < w \wedge (u,w) \in E \Rightarrow (u,v) \in E \vee (v,w) \in | :::::<math>u < v < w \wedge (u,w) \in E \Rightarrow (u,v) \in E \vee (v,w) \in | ||
E.</math> | E.</math> | ||
A graph is a cocomparability graph if it admits a cocomparability | A graph is a [[cocomparability graph]] if it admits a cocomparability ordering. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 18:59, 12 ноября 2013
Cocomparability ordering — косравнимое упорядочение.
A graph [math]\displaystyle{ \,G }[/math] has a cocomparability ordering if there exists a linear order [math]\displaystyle{ \,\lt }[/math] on the set of its vertices such that for every choice of vertices [math]\displaystyle{ \,u, v, w }[/math] the following property holds
- [math]\displaystyle{ u \lt v \lt w \wedge (u,w) \in E \Rightarrow (u,v) \in E \vee (v,w) \in E. }[/math]
A graph is a cocomparability graph if it admits a cocomparability ordering.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.