Интервальный граф: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
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{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. | |||
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 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]