Введение

График пересечения интервалов на вещественной прямой

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

Эффективный алгоритм распознавания

Определение того, является ли данный граф интервальным, можно выполнить за определенное время, находя упорядочение максимальных клик, которое является последовательным относительно включения вершин. Многие известные алгоритмы для этой задачи работают именно так, хотя распознавание интервальных графов возможно и за линейное время без использования их клик. Оригинальный алгоритм линейного времени распознавания интервальных графов основан на сложной структуре данных PQ-дерева, но было показано, как решить эту задачу проще, используя лексикографический поиск в ширину, основанный на факте, что граф является интервальным тогда и только тогда, когда он является хордальным, а его дополнение – графом сопоставимости. Аналогичный подход с использованием алгоритма LexBFS с 6 проходами описан в .

Связанные семейства графиков

По характеристике интервальных графов как AT-свободных хордальных графов, интервальные графы являются сильно хордальными графами и, следовательно, совершенными графами. Их дополнения принадлежат классу графов сопоставимости, а отношения сопоставимости – это как раз интервальные порядки. Из того факта, что граф является интервальным графом тогда и только тогда, когда он хордальный и его дополнение является графом сопоставимости, следует, что граф и его дополнение оба являются интервальными графами тогда и только тогда, когда граф является одновременно разбиваемым и пермутационным графом. Интервальные графы, имеющие интервальное представление, в котором любые два интервала либо не пересекаются, либо вложены друг в друга, являются тривиально совершенными графами. Граф имеет боксичность не более единицы тогда и только тогда, когда это интервальный граф; боксичность произвольного графа – это минимальное число интервальных графов на одном и том же множестве вершин, таких что пересечение множеств ребер этих интервальных графов является… Графы пересечений дуг окружности образуют графы дуг окружности, класс графов, содержащий интервальные графы. Графы трапецоидов, являющиеся пересечениями трапеций, параллельные стороны которых лежат на одних и тех же двух параллельных прямых, также являются обобщением интервальных графов. Связные интервальные графы, не содержащие треугольников, являются как раз гусеничными деревьями.

Графики интервалов

Графы правильных интервалов — это графы интервалов, которые имеют интервальное представление, в котором ни один интервал строго не содержит другой интервал; графы единичных интервалов — это графы интервалов, которые имеют интервальное представление, в котором каждый интервал имеет единичную длину. Интервальное представление единичных интервалов без повторяющихся интервалов обязательно является правильным интервальным представлением. Не каждое правильное интервальное представление является представлением единичных интервалов, но каждый граф правильных интервалов является графом единичных интервалов, и наоборот. Каждый граф правильных интервалов является графом без когтей; и наоборот, графы правильных интервалов — это именно графы без когтей. Однако существуют графы без когтей, которые не являются интервальными графами. Интервальный граф называется правильным, если существует представление, в котором ни один интервал не содержится более чем в других. Это понятие расширяет идею графов правильных интервалов таким образом, что 0-правильный интервальный граф является графом правильных интервалов. Интервальный граф называется неправильным, если существует представление, в котором ни один интервал не содержит более чем других. Это понятие расширяет идею графов правильных интервалов таким образом, что 0-неправильный интервальный граф является графом правильных интервалов. Интервальный граф называется вложенным, если не существует цепочки длины интервалов, вложенных друг в друга. Это обобщение графов правильных интервалов, поскольку 1-вложенный интервальный граф является точно графом правильных интервалов.

Приложения

Математическая теория интервальных графов была разработана с прицелом на практическое применение исследователями математического отдела корпорации RAND, в которую входили молодые ученые, такие как Питер С. Фишберн и студенты, такие как Алан С. Такер и Джоэл Э. Коэн, наряду с ведущими специалистами, такими как Делберт Фулкерсон и (постоянный посетитель) Виктор Кли. Коэн применил интервальные графы к математическим моделям популяционной биологии, в частности к пищевым цепям. Интервальные графы используются для представления задач распределения ресурсов в исследовании операций и теории расписаний. В этих задачах каждый интервал представляет запрос на ресурс (например, вычислительный узел распределенной системы или аудиторию для занятий) на определенный период времени. Задача о максимальном независимом множестве с наибольшим весом для графа представляет собой поиск оптимального подмножества запросов, которые могут быть удовлетворены без конфликтов. Дополнительную информацию можно найти в разделе "Планирование интервалов". Оптимальная раскраска интервального графа представляет собой назначение ресурсов, покрывающее все запросы с использованием минимально возможного количества ресурсов; ее можно найти за полиномиальное время с помощью жадного алгоритма раскраски, который раскрашивает интервалы в порядке возрастания их левых конечных точек. Другие области применения включают генетику, биоинформатику и компьютерные науки. Поиск набора интервалов, представляющих интервальный граф, также может использоваться для сборки непрерывных подпоследовательностей при построении карт ДНК. Интервальные графы также играют важную роль в темпоральных рассуждениях.

Интервалы завершения и ширина пути

Если G – произвольный граф, то интервальным завершением G является интервальный граф на том же наборе вершин, содержащий G в качестве подграфа. Параметризованная версия задачи об интервальном завершении (нахождение интервального суперграфа с k дополнительными ребрами) является фиксированно-параметрически разрешимой и, более того, может быть решена за параметризованное субекспоненциальное время. Ширина пути интервального графа на единицу меньше размера его максимальной клики (или, что эквивалентно, на единицу меньше его хроматического числа), а ширина пути любого графа G равна минимальной ширине пути интервального графа, содержащего G в качестве подграфа.