Интервальный граф

Интервальный граф — это граф, вершины которого соответствуют отрезкам (интервалам) на вещественной прямой, а ребро между двумя вершинами существует тогда и только тогда, когда соответствующие интервалы пересекаются (имеют непустое пересечение). Интервальные графы являются одним из наиболее изученных классов графов в теории графов и дискретной математике, обладая рядом важных свойств и находя широкое применение в различных областях, включая биоинформатику, планирование задач, генетику и компьютерные науки.

Определение и формальное описание

Пусть задано семейство интервалов \( I = \{I_1, I_2, \dots, I_n\} \) на вещественной прямой, где каждый интервал \( I_i = [a_i, b_i] \) с \( a_i < b_i \). Интервальный граф \( G = (V, E) \) строится следующим образом:

• Множество вершин \( V \) взаимно однозначно соответствует интервалам из \( I \).
• Ребро \( (v_i, v_j) \in E \) существует тогда и только тогда, когда \( I_i \cap I_j \neq \emptyset \).

Граф называется интервальным, если существует такое представление в виде семейства интервалов. Такое представление называется интервальным представлением или интервальной моделью графа. Интервальный граф может иметь несколько различных интервальных представлений.

Свойства

Хордальность и совершенство

Интервальные графы являются подклассом хордальных графов (также называемых триангулированными). Хордальный граф — это граф, в котором каждый цикл длины не менее 4 имеет хорду (ребро, соединяющее две несмежные вершины цикла). Интервальные графы наследуют все свойства хордальных графов, включая существование симплициальной вершины (вершины, соседи которой образуют клику). Более того, интервальные графы являются совершенными графами, то есть хроматическое число любого их порождённого подграфа равно размеру максимальной клики в этом подграфе.

Порядок интервалов и свойство последовательности

Одно из ключевых свойств интервальных графов — существование линейного порядка на вершинах, при котором для любой вершины её соседи образуют последовательный отрезок в этом порядке. Это свойство известно как свойство последовательности или свойство непрерывности. Формально: в интервальном графе существует такая нумерация вершин \( v_1, v_2, \dots, v_n \), что для каждого \( i \) множество соседей вершины \( v_i \) с номерами, меньшими \( i \), образует последовательный отрезок (то есть если \( v_j \) и \( v_k \) — соседи \( v_i \) и \( j < k \), то все вершины между ними также являются соседями \( v_i \)). Это свойство эквивалентно существованию интервального представления.

Максимальные клики

Максимальные клики в интервальном графе соответствуют точкам на прямой, в которых пересекается максимальное количество интервалов. Важным свойством является то, что максимальные клики могут быть упорядочены так, что для любой вершины множество клик, содержащих эту вершину, образует последовательный отрезок в этом порядке. Это свойство лежит в основе многих алгоритмов распознавания и работы с интервальными графами.

Древесная ширина

Интервальные графы имеют ограниченную древесную ширину. Древесная ширина интервального графа равна размеру его максимальной клики минус 1. Это делает их удобными для алгоритмов динамического программирования на графах.

Связь с интервальными порядками

Интервальные графы тесно связаны с интервальными порядками. Если заданы интервалы, то можно определить частичный порядок на их правых концах, который называется интервальным порядком. Обратно, любой интервальный порядок может быть представлен интервалами, и соответствующий граф сравнения является интервальным графом.

Распознавание

Задача распознавания интервальных графов (определение, является ли данный граф интервальным) решается за полиномиальное время. Существует несколько алгоритмов, наиболее известные из которых основаны на:

• Алгоритме Бута и Люкера (1976). Этот алгоритм использует лексикографический поиск в ширину (LexBFS) для построения специальной нумерации вершин и проверки свойства последовательности. Он работает за время \( O(n + m) \), где \( n \) — число вершин, \( m \) — число рёбер.
• Алгоритме на основе PQ-деревьев. PQ-деревья — это структуры данных, представляющие все возможные линейные порядки, в которых заданные множества являются последовательными. Для распознавания интервальных графов строится семейство максимальных клик, и проверяется, существует ли такой порядок вершин, что каждая клика образует последовательный отрезок. Этот алгоритм также работает за линейное время.

Подклассы и обобщения

Правильные интервальные графы

Правильный интервальный граф (или интервальный граф единичной длины) — это интервальный граф, который может быть представлен интервалами одинаковой длины (например, единичными). Не все интервальные графы являются правильными. Правильные интервальные графы являются подклассом интервальных графов и обладают дополнительными свойствами, например, они являются хордальными графами с дополнительным ограничением на размер максимальной клики.

Интервальные графы с ограничением на длину

Обобщением являются интервальные графы, в которых длины интервалов ограничены некоторым диапазоном. Такие графы используются, например, в задачах планирования, где длительность операций ограничена.

Интервальные графы с весами

Вершинам интервального графа могут быть приписаны веса, соответствующие, например, стоимости или длине интервала. Это позволяет решать задачи оптимизации, такие как поиск максимального взвешенного независимого множества или минимального взвешенного вершинного покрытия.

Применение

Планирование задач (Scheduling)

Одно из классических применений — задачи планирования. Если каждая задача представлена интервалом времени, в течение которого она должна выполняться, то интервальный граф показывает, какие задачи конфликтуют (пересекаются во времени) и не могут выполняться одновременно. Задача раскраски интервального графа (нахождение минимального числа цветов) эквивалентна задаче распределения задач по минимальному числу ресурсов (например, процессоров или аудиторий). Поскольку интервальные графы являются совершенными, хроматическое число равно размеру максимальной клики, что позволяет решать задачу эффективно.

Биоинформатика и генетика

В генетике интервальные графы используются для моделирования перекрытий фрагментов ДНК при сборке генома. Каждый фрагмент (например, после секвенирования) представляется интервалом на хромосоме, и пересечение интервалов указывает на возможное перекрытие фрагментов. Интервальные графы также применяются для анализа структуры хромосом и выявления дупликаций.

Компьютерные науки

• Анализ программ: интервальные графы используются для представления интервалов времени выполнения процедур или операций.
• Базы данных: для оптимизации запросов, связанных с временными интервалами.
• Сети: для анализа пересечения временных слотов в протоколах передачи данных.

Математическая химия

В химии интервальные графы применяются для моделирования молекулярных структур, где атомы или группы атомов представлены интервалами на некоторой оси, а пересечение указывает на химическую связь.

Социология и экономика

Интервальные графы используются для анализа временных рядов, например, для выявления пересечений периодов активности или событий.

Интересные факты

• Интервальные графы являются строго хордальными (или правильно хордальными) графами, то есть они не содержат индуцированных циклов длины больше 3, а также некоторых других запрещённых подграфов, таких как «клешня» (K_{1,3}) и «солнце» (sun graph).
• Класс интервальных графов замкнут относительно операции взятия порождённых подграфов: любой порождённый подграф интервального графа также является интервальным.
• Интервальные графы могут быть охарактеризованы запрещёнными порождёнными подграфами. Полный список запрещённых подграфов включает бесконечное семейство, но известны некоторые минимальные запрещённые подграфы, такие как циклы длины 4 и более без хорд, клешня, а также некоторые более сложные графы.
• Задача поиска максимального независимого множества в интервальном графе решается за линейное время с помощью жадного алгоритма, основанного на сортировке интервалов по правому концу.

Критика и ограничения

Несмотря на широкое применение, интервальные графы имеют ограничения. Не все реальные задачи могут быть адекватно смоделированы с помощью интервалов на прямой. Например, если отношения пересечения между объектами не транзитивны или зависят от нескольких параметров, может потребоваться более общая модель, такая как графы пересечения отрезков на плоскости или графы пересечения выпуклых множеств. Кроме того, интервальные графы не могут моделировать ситуации, в которых пересечение интервалов не является симметричным или зависит от направления.

Источники

• Booth, K. S., & Lueker, G. S. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3), 335–379.
• Golumbic, M. C. (2004). Algorithmic Graph Theory and Perfect Graphs (2nd ed.). Elsevier.
• Brandstädt, A., Le, V. B., & Spinrad, J. P. (1999). Graph Classes: A Survey. SIAM.
• West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall.