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

'''Интервальный граф''' (''[[Interval graph]]'') - [[граф]] пересечений множества замкнутых интервалов на вещественной прямой.

Справедлива теорема (Gilmore and Hofman, 1964) об ''эквивалентности следующих свойств [[неориентированный граф|неориентированного графа]] <math>G</math>:''

''2. Максимальные [[клика|клики]] в <math>G</math> могут быть линейно упорядочены так, что для каждой [[вершина|вершины]] <math>x</math> в <math>G</math> максимальные клики, содержащие <math>x</math>, встречаются последовательно.''

''3. <math>G</math>  не  содержит  [[хорда|безхордового]] 4-[[цикл|цикла]] и его дополнение <math>\bar{G}</math> есть [[граф сравнимости]].''

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