4194
правки
Интервальный граф: различия между версиями
Материал из WEGA
нет описания правки
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] | |||
