Русская Википедия:Интервальный граф
Интервальный граф — граф пересечений мультимножества интервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются.
Определение
Пусть <math>\{I_1, I_2, ..., I_n\} \subset P(R)</math> — множество интервалов.
Соответствующий интервальный граф — это <math>G = (V, E)</math>, где
- <math>V = \{I_1, I_2,..., I_n\}</math> и
- <math>\{I_\alpha, I_\beta\} \in E</math>, тогда и только тогда, когда <math>I_\alpha \cap I_\beta \ne \emptyset</math>.
Из этого построения можно получить общие свойства интервальных графов. Так, граф G является интервальным тогда и только тогда, когда наибольшие клики графа G могут быть упорядочены <math>M_1, M_2,..., M_k</math> так, что для любой <math>v \in M_i \cap M_k</math>, где <math>i < k</math>, выполняется также <math>v \in M_j</math> для любого <math>M_j, i \le j \le k</math>Шаблон:Sfn.
Эффективные алгоритмы распознавания
Определить, является ли граф <math>G = (V, E)</math> интервальным можно за время <math>O(|V|+|E|)</math> путём упорядочения наибольших клик графа G.
Первоначальный алгоритм распознавания за линейное время Бута и ЛюкераШаблон:Harv основывается на сложной структуре PQ-деревьев, но Хабиб, МакКонел, Пауль и ВьенноШаблон:Harv показали как решить задачу проще, используя лексикографический поиск в ширину и основываясь на факте, что граф является интервальным тогда и только тогда, когда он хордален и его дополнение — граф сравнимостиШаблон:SfnШаблон:Sfn.
Связанные семейства графов
Интервальные графы являются хордальными и, следовательно, совершеннымиШаблон:SfnШаблон:Sfn. Их дополнения принадлежат к классу графов сравнимостиШаблон:Sfn, и отношение сравнения — в точности Шаблон:Не переведено 5Шаблон:Sfn.
Интервальные графы имеющее интервальное представление, в котором любые два интервала либо не пересекаются, либо вложены, являются тривиальными совершенными графами.
Правильные интервальные графы — это интервальные графы, имеющее интервальное представление, в котором никакой интервал не является собственным подмножеством никакого другого интервала. Единичные интервальные графы — это интервальные графы, имеющее интервальное представление, в котором каждый интервал имеет единичную длину. Любой правильный интервальный граф не имеет клешней. Однако обратное неверно — граф без клешней не обязательно является правильным интервальным графом[1]. Если набор сегментов является множеством, то есть повторение сегментов не разрешено, то граф является единичным интервальным графом тогда и только тогда, когда он является правильным интервальным графомШаблон:Sfn.
Графы пересечений дуг окружности образуют графы дуг окружности — класс графов, содержащий интервальные графы. Трапецеидальные графы, пересечение трапеций, все параллельные стороны которых лежат на двух параллельных прямых, являются обобщением интервальных графов.
Путевая ширина интервального графа на единицу меньше размера максимальной клики (или, что эквивалентно, на единицу меньше его хроматического числа), a путевая ширина любого графа G равна наименьшей путевой ширине интервального графа, содержащего G в качестве подграфаШаблон:Sfn.
Родственные интервальные графы без треугольников — это в точности деревья-гусеницыШаблон:Sfn.
Случайный интервальный граф — интеревальный граф построенный по случайному семейству отрезков, например отрезки вершины отрезков могут быть выбраны например по естественному распределению на единичном отрезке.
Приложения
Математическая теория интервальных графов разработана с оглядкой на приложения исследователей из математического подразделения корпорации RAND, в которую входили молодые исследователи, такие как Шаблон:Не переведено 5 и студенты, такие как Алан Такер и Шаблон:Не переведено 5, не считая лидеров, таких как Делберт Рей Фалкерсон и (частый гость) Виктор Кли[2]. Коэн применил интервальные графы в математических моделях популяций, особенно пищевых цепочек[3].
Другие приложения включают генетику, биоинформатику и информатику. Поиск множества отрезков, представляющих интервальный граф, может быть использован в качестве методики сборки непрерывных последовательностей в ДНКШаблон:Sfn. Интервальные графы используются в постановке задач Шаблон:Не переведено 5 в исследовании операций и планировании выполнения задач. Каждый промежуток представляет запрос на ресурс на определённый период времени. Задача нахождения независимого множества максимального веса графа представляет задачу поиска лучшего подмножества запросов, которые можно выполнить без конфликтовШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья.
- Шаблон:Статья
- Шаблон:Статья.
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
Ссылки
