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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Интервальный граф''' (''Interval graph'') - граф пересечений множества замкнутых ин...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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''), если ни один интервал
'''Интервальный граф''' называется [[собственный интервальный граф|''собственным'' интервальным графом]] (''[[proper interval graph]]''), если ни один [[интервал]] в интервальном представлении не содержит полностью другой, и ''[[единичный интервальный граф|единичным]]'' (''[[unit interval graph]]''), если все интервалы единичной длины.  
в интервальном представлении не содержит полностью другой, и ''единичным''
(''unit interval graph''), если все интервалы единичной длины.  
==Литература==
==Литература==
[Миркин-Родин],


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


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

Текущая версия от 17:09, 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.
  • Миркин Б.Г., Родин С.Н. Графы и гены. — М.: Наука, 1977.
  • [J. Graph Theory]