Circular-arc graph

Материал из WEGA
Перейти к навигации Перейти к поиску

Circular-arc graphграф дуг окружности.

A circular-arc graph is the intersection graph of a family of arcs on a circle; that is, for each vertex [math]\displaystyle{ \,v_{i} }[/math] there is a (closed) arc [math]\displaystyle{ \,a_{i} }[/math] of the circle such that [math]\displaystyle{ \,v_{i} }[/math] and [math]\displaystyle{ \,v_{j} }[/math] are adjacent if and only if [math]\displaystyle{ a_{i} \cap a_{j} \neq \emptyset }[/math].

Литература

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