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