Интервальный граф

Материал из WEGA
Версия от 17:09, 22 февраля 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Интервальный граф (Interval graph) — граф пересечений множества замкнутых интервалов на вещественной прямой. Комбинаторную характеризацию интервальных графов дает следующая теорема.

Справедлива теорема (Gilmore and Hofman, 1964) об эквивалентности следующих свойств неориентированного графа [math]\displaystyle{ \,G }[/math]:

1. [math]\displaystyle{ G }[/math] — интервальный граф.
2. Максимальные клики в [math]\displaystyle{ \,G }[/math] могут быть линейно упорядочены так, что для каждой вершины [math]\displaystyle{ \,x }[/math] в [math]\displaystyle{ \,G }[/math] максимальные клики, содержащие [math]\displaystyle{ \,x }[/math], встречаются последовательно.
3. [math]\displaystyle{ \,G }[/math] не содержит безхордового [math]\displaystyle{ \,4 }[/math]-цикла и его дополнение [math]\displaystyle{ \bar{G} }[/math] есть граф сравнимости.

Интервальный граф называется собственным интервальным графом (proper interval graph), если ни один интервал в интервальном представлении не содержит полностью другой, и единичным (unit interval graph), если все интервалы единичной длины.

Литература

  • Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998.
  • Миркин Б.Г., Родин С.Н. Графы и гены. — М.: Наука, 1977.
  • [J. Graph Theory]