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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Интервальный граф''' (''Interval graph'') - граф пересечений множества замкнутых ин...)
 
Нет описания правки
Строка 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>  не  содержит  [[хорда|безхордового]] 4-[[цикл|цикла]] и его дополнение <math>\bar{G}</math> есть [[граф сравнимости]].''


'''И.г.''' называется ''собственным'' интервальным графом (''proper interval graph''), если ни один интервал
'''Интервальный граф''' называется [[собственный интервальный граф|''собственным'' интервальным графом]] (''[[proper interval graph]]''), если ни один [[интервал]] в интервальном представлении не содержит полностью другой, и ''[[единичный интервальный граф|единичным]]'' (''[[unit interval graph]]''), если все интервалы единичной длины.  
в интервальном представлении не содержит полностью другой, и ''единичным''
(''unit interval graph''), если все интервалы единичной длины.  
==Литература==
==Литература==
[Миркин-Родин],  
[Миркин-Родин],  

Версия от 13:28, 28 октября 2009

Интервальный граф (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] не содержит безхордового 4-цикла и его дополнение [math]\displaystyle{ \bar{G} }[/math] есть граф сравнимости.

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

Литература

[Миркин-Родин],

[Евстигнеев/98],

[J. Graph Theory]