Интервальный граф: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 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]]''), если ни один [[интервал]] в интервальном представлении не содержит полностью другой, и ''[[единичный интервальный граф|единичным]]'' (''[[unit interval graph]]''), если все интервалы единичной длины. | '''Интервальный граф''' называется [[собственный интервальный граф|''собственным'' интервальным графом]] (''[[proper interval graph]]''), если ни один [[интервал]] в интервальном представлении не содержит полностью другой, и ''[[единичный интервальный граф|единичным]]'' (''[[unit interval graph]]''), если все интервалы единичной длины. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. | |||
* Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c. | |||
* Миркин Б.Г., Родин С.Н. Графы и гены. — М.: Наука, 1977. | |||
* [J. Graph Theory] | |||
[ | [[Категория:Обыкновенные графы]] | ||
[[Категория:Неориентированные графы]] | |||
[[Категория:Основные термины]] | |||
[[Категория:Хордальные графы]] | |||
Текущая версия от 09:16, 13 декабря 2024
Интервальный граф (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.
- Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
- Миркин Б.Г., Родин С.Н. Графы и гены. — М.: Наука, 1977.
- [J. Graph Theory]