K-Cocomparability ordering

Материал из WikiGrapp
Версия от 19:04, 12 ноября 2013; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[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.