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