Cocomparability ordering

Материал из WikiGrapp
Перейти к:навигация, поиск

Cocomparability orderingкосравнимое упорядочение.

A graph \,G has a cocomparability ordering if there exists a linear order \,< on the set of its vertices such that for every choice of vertices \,u, v, w the following property holds

u < v < w \wedge (u,w) \in E \Rightarrow (u,v) \in E \vee (v,w) \in
E.

A graph is a cocomparability graph if it admits a cocomparability ordering.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.