Интервальный граф: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Интервальный граф''' (''[[Interval graph]]'') - [[граф]] пересечений множества замкнутых интервалов на вещественной прямой.
'''Интервальный граф''' (''[[Interval graph]]'') [[граф]] пересечений множества замкнутых интервалов на вещественной прямой.
Комбинаторную характеризацию интервальных графов дает следующая теорема.
Комбинаторную характеризацию интервальных графов дает следующая теорема.


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


''1. <math>G</math> --- интервальный граф.''
:''1. <math>G</math> интервальный граф.''


''2. Максимальные [[клика|клики]] в <math>G</math> могут быть линейно упорядочены так, что для каждой [[вершина|вершины]] <math>x</math> в <math>G</math> максимальные клики, содержащие <math>x</math>, встречаются последовательно.''
:''2. Максимальные [[клика|клики]] в <math>\,G</math> могут быть линейно упорядочены так, что для каждой [[вершина|вершины]] <math>\,x</math> в <math>\,G</math> максимальные клики, содержащие <math>\,x</math>, встречаются последовательно.''


''3. <math>G</math>  не  содержит  [[хорда|безхордового]]  4-[[цикл|цикла]] и его дополнение <math>\bar{G}</math> есть [[граф сравнимости]].''
:''3. <math>\,G</math>  не  содержит  [[хорда|безхордового]]  <math>\,4</math>-[[цикл|цикла]] и его дополнение <math>\bar{G}</math> есть [[граф сравнимости]].''


'''Интервальный граф''' называется [[собственный интервальный граф|''собственным'' интервальным графом]] (''[[proper interval graph]]''), если ни один [[интервал]] в интервальном представлении не содержит полностью другой, и ''[[единичный интервальный граф|единичным]]'' (''[[unit interval graph]]''), если все интервалы единичной длины.  
'''Интервальный граф''' называется [[собственный интервальный граф|''собственным'' интервальным графом]] (''[[proper interval graph]]''), если ни один [[интервал]] в интервальном представлении не содержит полностью другой, и ''[[единичный интервальный граф|единичным]]'' (''[[unit interval graph]]''), если все интервалы единичной длины.  
==Литература==
==Литература==
[Миркин-Родин],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.


[Евстигнеев/98],  
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. — С.5—27.


[J. Graph Theory]
* Миркин Б.Г., Родин С.Н. Графы и гены. — М.: Наука, 1977.
 
* [J. Graph Theory]

Версия от 17:07, 22 февраля 2011

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