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

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

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

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

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

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

Литература

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