Cocomparability ordering: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Cocomparability ordering''' --- косравнимое упорядочение. A graph <math>G</math> has a '''cocomparability ordering''' if there exists a …»)
 
Нет описания правки
 
Строка 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.
ordering.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 10:47, 24 октября 2018

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.