Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 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.


[Евстигнеев/98],  
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. — С.5—27.


[J. Graph Theory]
* Миркин Б.Г., Родин С.Н. Графы и гены. — М.: Наука, 1977.
 
* [J. Graph Theory]