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

Не путать с D-интервальный гиперграф.
Семь интервалов на вещественной прямой и соответствующий семивершинный интервальный граф.

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

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

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

Определение

Граф интервалов - это неориентированный граф г сформированный из семейства интервалов

Sя, я = 0, 1, 2, ...

создав одну вершину vя для каждого интервала Sя, и соединяя две вершины vя и vj ребром, если соответствующие два множества имеют непустое пересечение, то есть множество ребер г является

E(г) = {{vя, vj} | Sя ∩ Sj ≠ ∅}.

Характеристики

Три вершины образуют астероидная тройка (АТ) в графе, если для каждых двух существует путь, содержащий эти два, но не имеющий соседей третьего. Граф является AT-свободным, если в нем нет астероидной тройки. Самая ранняя характеристика интервальных графов выглядит следующим образом:

  • Граф является интервальным графом тогда и только тогда, когда он хордовый и AT-бесплатно.[1]

Другие характеристики:

  • Граф является интервальным графом тогда и только тогда, когда его максимальное клики можно заказать M1, M2, ..., Mk такой, что для любого v ∈ Mя ∩ Mk, где я < k, также верно, что v ∈ Mj для любого Mj, я ≤ j ≤ k.[2]
  • Граф является интервальным графом тогда и только тогда, когда крайнее кликовое покрытие всех его максимальных клик может быть организовано в представление пути клики.[3]
  • Граф является интервальным графом тогда и только тогда, когда он не содержит C4 как индуцированный подграф и его дополнение имеет транзитивную ориентацию.[4]

Были описаны различные другие характеристики интервальных графов и их вариантов.[5][6]

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

Определение того, является ли данный граф г = (V, E) - интервальный граф, который можно построить в О(|V|+|E|) время, ища порядок максимального клики из г последовательное по включению вершины. Многие из известных алгоритмов решения этой проблемы работают таким образом, хотя также возможно распознавать интервальные графы за линейное время без использования их клик (Сюй 1992 ).

Оригинальный алгоритм распознавания линейного времени Бут и Люкер (1976) основан на их комплексе Дерево PQ структура данных, но Habib et al. (2000) показали, как проще решить проблему с помощью лексикографический поиск в ширину, исходя из того, что граф является интервальным графом тогда и только тогда, когда он хордовый и это дополнять это график сопоставимости.[2][7]Аналогичный подход с использованием алгоритма LexBFS с 6 развертками описан в Корнейл, Олариу и Стюарт (2009).

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

По характеристике интервальных графов как хордовых графов без AT,[1] интервальные графики сильно хордовые графы и, следовательно идеальные графики.Их дополняет принадлежат к классу графики сопоставимости,[4] а отношения сопоставимости - это как раз интервальные заказы.[2]

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

Графы интервалов, которые имеют интервальное представление, в котором каждые два интервала либо не пересекаются, либо вложены, являются тривиально совершенные графы.

График имеет коробочка не более одного тогда и только тогда, когда это интервальный граф; коробчатость произвольного графа г - минимальное количество интервальных графов на одном и том же множестве вершин, такое что пересечение множеств ребер интервальных графов равно г.

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

Связанный без треугольников интервальные графики - это в точности гусеницы.[8]

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

Правильные интервальные графики являются интервальными графами, которые имеют интервальное представление, в котором нет интервалов правильно содержит любой другой интервал; графики единичных интервалов - это интервальные графы, которые имеют интервальное представление, в котором каждый интервал имеет единичную длину. Представление единичного интервала без повторяющихся интервалов обязательно является правильным интервальным представлением. Не каждое правильное представление интервала является представлением единичного интервала, но каждый правильный граф интервалов является графом единичного интервала, и наоборот.[9] Каждый собственный интервальный граф является граф без когтей; наоборот, правильные интервальные графы - это в точности интервальные графы без клешней. Однако существуют графы без клешней, которые не являются интервальными графами.[10]

Интервальный граф называется q-собственно, если есть представление, в котором интервал не содержится более чем q другие. Это понятие расширяет идею собственных интервальных графов, так что 0-правильный интервальный граф является правильным интервальным графом.[11]

Неправильные интервальные графики

Интервальный граф называется п-неправильно, если есть представление, в котором ни один интервал не содержит более п другие. Это понятие расширяет идею правильных интервальных графов, так что 0-несобственный интервальный граф является правильным интервальным графом.[12]

k-Вложенные интервальные графики

График интервалов k-вложен, если нет цепочки длины k + 1 интервалов, вложенных друг в друга. Это обобщение правильных интервальных графов, поскольку 1-вложенные интервальные графы являются в точности правильными интервальными графами.[13]

Приложения

Математическая теория интервальных графов была разработана с учетом применения исследователями из RAND Corporation математический факультет, в который входили молодые исследователи, такие как Питер С. Фишберн и студентам нравится Алан К. Такер и Джоэл Э. Коэн - помимо лидеров - таких как Делберт Фулкерсон и (постоянный посетитель) Виктор Клее.[14] Коэн применил интервальные графики к математические модели из популяционная биология в частности пищевые сети.[15]

Графики интервалов используются для представления распределение ресурсов проблемы в исследование операций и теория расписания. В этих приложениях каждый интервал представляет собой запрос ресурса (например, блока обработки распределенной вычислительной системы или помещения для класса) на определенный период времени. Максимальный вес проблема независимого множества для графа представляет собой проблему поиска наилучшего подмножества запросов, которые могут быть удовлетворены без конфликтов.[16]Оптимальный раскраска графика графа интервалов представляет собой назначение ресурсов, которое покрывает все запросы с минимальным количеством ресурсов; это можно найти в полиномиальное время по жадная окраска алгоритм, который окрашивает интервалы в отсортированном порядке по их левым конечным точкам.[17]

Другие приложения включают генетику, биоинформатика и информатика. Нахождение набора интервалов, которые представляют граф интервалов, также можно использовать как способ сборки смежных подпоследовательностей в ДНК отображение.[18] Графики интервалов также играют важную роль во временных рассуждениях.[19]

Завершение интервала и ширина пути

Если г - произвольный граф, завершение интервала из г - интервальный граф на том же множестве вершин, содержащий г как подграф. Параметризованная версия завершения интервала (найти суперграф интервала с k дополнительные ребра) фиксированный параметр управляемый, и, более того, разрешима за параметризованное субэкспоненциальное время.[20][21]

В ширина пути графа интервалов на единицу меньше, чем размер его максимальной клики (или, что то же самое, на единицу меньше, чем его хроматическое число), а ширина пути любого графа г совпадает с наименьшей шириной пути интервального графа, содержащего г как подграф.[22]

Заметки

  1. ^ а б Леккеркеркер и Боланд (1962)
  2. ^ а б c (Фишберн 1985 )
  3. ^ Фулкерсон и Гросс (1965)
  4. ^ а б Гилмор и Хоффман (1964)
  5. ^ Макки и МакМоррис (1999)
  6. ^ Brandstädt, Le & Spinrad (1999)
  7. ^ Голумбик (1980).
  8. ^ Экхофф (1993).
  9. ^ Робертс (1969); Гарди (2007)
  10. ^ Фодри, Фландрин и Рячек (1997), п. 89.
  11. ^ Проскуровский, Анджей; Телле, Ян Арне (1999). «Классы графов с ограниченными интервальными моделями». Дискретная математика и теоретическая информатика. 3 (4): 167–176. CiteSeerX  10.1.1.39.9532.
  12. ^ Бейерл, Джеффри; Джеймисон, Роберт (2008). «Интервальные графики с ограничениями содержания». Congressus Numerantium. 191 (2008): 117–128. arXiv:1109.6675. Bibcode:2011arXiv1109.6675B.
  13. ^ Клавик, Павел; Отачи, Йота; Шейноха, Иржи (2015-10-14). «О классах интервальных графов ограниченной вложенности и подсчета длин». arXiv:1510.03998 [cs.DM ].
  14. ^ Коэн (1978, стр.ix – 10 )
  15. ^ Коэн (1978, стр.12–33 )
  16. ^ Bar-Noy et al. (2001).
  17. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03293-7.
  18. ^ Zhang et al. (1994).
  19. ^ Голумбик и Шамир (1993).
  20. ^ Villanger et al. (2009).
  21. ^ Близнец и др. (2014).
  22. ^ Бодлендер (1998).

использованная литература

внешние ссылки