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

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

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

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

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

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

Определение

Интервальный граф — это неориентированный граф G, образованный семейством интервалов.

${\displaystyle S_{i},\quad i=0,1,2,\dots }$

путем создания одной вершины v _i для каждого интервала S _i и соединения двух вершин v _i и v _j ребром всякий раз, когда соответствующие два множества имеют непустое пересечение. То есть, множество ребер G есть

${\displaystyle E(G)=\{(v_{i},v_{j})\mid S_{i}\cap S_{j}\neq \emptyset \}.}$

Это граф пересечения интервалов.

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

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

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

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

• Граф является интервальным графом тогда и только тогда, когда его максимальные клики можно упорядочить так, что каждая вершина, принадлежащая двум из этих клик, также принадлежит всем кликам между ними в упорядочении. То есть, для каждого с , также верно, что всякий раз, когда . ^[2] ${\displaystyle M_{1},M_{2},\dots ,M_{k}}$ ${\displaystyle v\in M_{i}\cap M_{k}}$ ${\displaystyle i<k}$ ${\displaystyle v\in M_{j}}$ ${\displaystyle i<j<k}$
• Граф является интервальным графом тогда и только тогда, когда он не содержит граф цикла как индуцированный подграф и является дополнением графа сравнимости . ^[3] ${\displaystyle C_{4}}$

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

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

Определение того, является ли заданный граф интервальным графом, может быть выполнено за время путем поиска упорядочения максимальных клик, которые являются последовательными относительно включения вершин. Многие из известных алгоритмов для этой задачи работают таким образом, хотя также возможно распознавать интервальные графы за линейное время без использования их клик. ^[5] ${\displaystyle G=(V,E)}$ ${\displaystyle O(|V|+|E|)}$ ${\displaystyle G}$

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

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

По характеристике интервальных графов как AT-свободных хордовых графов, ^[1] интервальные графы являются сильно хордовыми графами и, следовательно, совершенными графами . Их дополнения принадлежат классу графов сравнимости , ^[3] и отношения сравнимости являются в точности интервальными порядками . ^[7]

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

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

Граф имеет коробчатость не более единицы тогда и только тогда, когда он является интервальным графом; коробчатость произвольного графа — это минимальное число интервальных графов на одном и том же множестве вершин, такое, что пересечение множеств ребер интервальных графов равно . ${\displaystyle G}$ ${\displaystyle G}$

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

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

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

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

Граф интервалов называется -правильным, если существует представление, в котором ни один интервал не содержит больше, чем другие. Это понятие расширяет идею правильных графов интервалов таким образом, что 0-правильный граф интервалов является правильным графом интервалов. ^[11] Граф интервалов называется -несобственным, если существует представление, в котором ни один интервал не содержит больше, чем другие. Это понятие расширяет идею правильных графов интервалов таким образом, что 0-несобственный граф интервалов является правильным графом интервалов. ^[12] Граф интервалов является -вложенным, если нет цепочки длины интервалов, вложенных друг в друга. Это обобщение правильных графов интервалов, поскольку 1-вложенные графы интервалов являются в точности правильными графами интервалов. ^[13] ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle k+1}$

Приложения

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

Интервальные графики используются для представления задач распределения ресурсов в исследовании операций и теории планирования . В этих приложениях каждый интервал представляет собой запрос на ресурс (например, процессорное устройство распределенной вычислительной системы или комнату для класса) на определенный период времени. Задача о максимальном весе независимого множества для графа представляет собой задачу поиска наилучшего подмножества запросов, которые могут быть удовлетворены без конфликтов. ^[16] Для получения дополнительной информации см. интервальное планирование .

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

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

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

Если — произвольный граф, то завершение интервала — это граф интервалов на том же множестве вершин, который содержит в качестве подграфа. Параметризованная версия завершения интервала (найти надграф интервала с k дополнительными ребрами) является фиксированным параметром, поддающимся обработке , и, более того, разрешима за параметризованное субэкспоненциальное время. ^{[20] [21]} ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Ширина пути интервального графа на единицу меньше размера его максимальной клики (или, что эквивалентно, на единицу меньше его хроматического числа), а ширина пути любого графа равна наименьшей ширине пути интервального графа, который содержит в качестве подграфа. ^[22] ${\displaystyle G}$ ${\displaystyle G}$

Комбинаторное перечисление

Число связанных интервальных графов на непомеченных вершинах для равно: ^[23] ${\displaystyle n}$ ${\displaystyle n=1,2,3,\dots }$

1, 1, 2, 5, 15, 56, 250, 1328, 8069, 54962, 410330, 3317302, ... (последовательность A005976 в OEIS )

Без предположения о связности числа больше. Количество интервальных графов на немаркированных вершинах, не обязательно связанных, равно: ^[24] ${\displaystyle n}$

1, 2, 4, 10, 27, 92, 369, 1807, 10344, 67659, 491347, 3894446, ... (последовательность A005975 в OEIS )

Эти числа демонстрируют рост быстрее, чем экспоненциальный : число интервальных графов на непомеченных вершинах составляет по крайней мере . ^[25] Из-за такой высокой скорости роста интервальные графы не имеют ограниченной ширины близнецов . ^[26] ${\displaystyle 3n}$ ${\displaystyle n!/3^{3n}}$

Примечания

1. Леккеркеркер и Боланд (1962).
2. Фулкерсон и Гросс (1965); Фишберн (1985)
3. Гилмор и Хоффман (1964).
4. Макки и Макморрис (1999); Брандштедт, Ле и Спинрад (1999)
5. Сюй (1992).
6. Фишберн (1985); Голумбик (1980)
7. Фишберн (1985).
8. Экхофф (1993).
9. Робертс (1969); Гарди (2007)
10. Фаудри, Фландрин и Рыячек (1997), стр. 89.
11. Проскуровски и Телле (1999).
12. Бейерл и Джеймисон (2008).
13. Клавик, Отачи и Шейноха (2019).
14. Коэн (1978), стр. ix–10.
15. Коэн (1978), стр. 12–33.
16. Бар-Ной и др. (2001).
17. Кормен и др. (2001), с. 379.
18. Чжан и др. (1994).
19. Голумбик и Шамир (1993).
20. Вилланджер и др. (2009).
21. Близнец и др. (2014).
22. Бодлендер (1998).
23. Хэнлон (1982), Таблица VIII, стр. 422.
24. Хэнлон (1982), Таблица VII, стр. 421.
25. Янг и Пиппенджер (2017).
26. Боннет и др. (2022).

Ссылки

• Бар-Ной, Амоц; Бар-Йехуда, Реувен; Фройнд, Ари; Наор, Джозеф (Сеффи) ; Шибер, Барух (2001), «Единый подход к аппроксимации распределения ресурсов и планирования», Журнал ACM , 48 (5): 1069–1090, CiteSeerX  10.1.1.124.9886 , doi :10.1145/502102.502107, S2CID  12329294
• Бейерл, Джеффри Дж.; Джеймисон, Роберт Э. (2008), «Интервальные графы с ограничениями на включение», Труды Тридцать девятой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям , Congressus Numerantium, т. 191, стр. 117–128, arXiv : 1109.6675 , MR  2489816
• Близнец, Иван; Фомин, Федор В.; Пилипчук, Марчин; Пилипчук, Михал (2014), «Субэкспоненциальный параметризованный алгоритм для надлежащего завершения интервала», в Шульц, Андреас С.; Вагнер, Доротея (ред.), Труды 22-го ежегодного Европейского симпозиума по алгоритмам (ESA 2014), Вроцлав, Польша, 8–10 сентября 2014 г. , Lecture Notes in Computer Science, т. 8737, Springer-Verlag, стр. 173–184, arXiv : 1402.3473 , doi : 10.1007/978-3-662-44777-2_15, ISBN 978-3-662-44776-5, S2CID  12385294
• Бодлендер, Ханс Л. (1998), «Частичный k -дендрарий графов с ограниченной древовидной шириной», Теоретическая информатика , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4, hdl : 1874/18312
• Бонне, Эдуард; Ким, Ын Чжун ; Томассе, Стефан; Ватриган, Реми (2022), «Двойная ширина I: проверка модели управляемого FO», Журнал ACM , 69 (1): A3:1–A3:46, arXiv : 2004.14789 , doi :10.1145/3486655, MR  4402362
• Бут, К. С.; Люкер, Г. С. (1976), «Тестирование свойства последовательных единиц, интервальных графов и планарности графа с использованием алгоритмов PQ-дерева», Журнал компьютерных и системных наук , 13 (3): 335–379, doi : 10.1016/S0022-0000(76)80045-1
• Брандштедт, А.; Ле, В.Б.; Спинрад, Дж.П. (1999), Классы графов: Обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 978-0-89871-432-6
• Коэн, Джоэл Э. (1978), Пищевые сети и пространство ниши , Монографии по популяционной биологии, т. 11, Принстон, Нью-Джерси: Princeton University Press, стр. 1–189, ISBN 978-0-691-08202-8, PMID  683203
• Кормен, Томас Х.; Лейзерсон , Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, ISBN 0-262-03293-7
• Корнейл, Дерек ; Олариу, Стефан; Стюарт, Лорна (2009), «Структура LBFS и распознавание интервальных графов», SIAM Journal on Discrete Mathematics , 23 (4): 1905–1953, doi :10.1137/S0895480100373455
• Экхофф, Юрген (1993), «Экстремальные интервальные графы», Журнал теории графов , 17 (1): 117–127, doi :10.1002/jgt.3190170112
• Faudree, Ralph ; Flandrin, Evelyne ; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR  1432221
• Фишберн, Питер К. (1985), Интервальные порядки и интервальные графы: исследование частично упорядоченных множеств , Wiley-Interscience Series in Discrete Mathematics, Нью-Йорк: John Wiley & Sons
• Фулкерсон, DR ; Гросс, OA (1965), «Матрицы инцидентности и интервальные графики», Pacific Journal of Mathematics , 15 (3): 835–855, doi : 10.2140/pjm.1965.15.835
• Гарди, Фредерик (2007), «Характеристика Робертса собственных и единичных интервальных графов», Дискретная математика , 307 (22): 2906–2908, doi :10.1016/j.disc.2006.04.043
• Гилмор, ПК; Хоффман, А.Дж. (1964), «Характеристика графов сравнимости и графов интервалов», Канадский журнал математики , 16 : 539–548, doi : 10.4153/CJM-1964-055-5
• Golumbic, Martin Charles (1980), Алгоритмическая теория графов и совершенные графы , Academic Press, ISBN 978-0-12-289260-8
• Golumbic, Martin Charles ; Shamir, Ron (1993), «Сложность и алгоритмы рассуждений о времени: подход на основе теории графов», Journal of the ACM , 40 (5): 1108–1133, CiteSeerX  10.1.1.35.528 , doi :10.1145/174147.169675, S2CID  15708027
• Хабиб, Мишель; Макконнелл, Росс; Пол, Кристоф; Вьенно, Лоран (2000), «Lex-BFS и уточнение разбиения с приложениями к транзитивной ориентации, распознаванию интервальных графов и последовательному тестированию единиц», Теоретическая информатика , 234 (1–2): 59–84, doi : 10.1016/S0304-3975(97)00241-7
• Хэнлон, Фил (1982), «Подсчет интервальных графиков», Труды Американского математического общества , 272 (2): 383–426, doi : 10.2307/1998705 , JSTOR  1998705, MR  0662044
• Hsu, Wen-Lian (1992), "Простой тест для интервальных графов", в Mayr, Ernst W. (ред.), Graph-Theoretic Concepts in Computer Science, 18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, 19–20 июня 1992 г., Proceedings , Lecture Notes in Computer Science, т. 657, Springer, стр. 11–16, doi :10.1007/3-540-56402-0_31, ISBN 978-3-540-56402-7
• Клавик, Павел; Отачи, Йота; Шейноха, Йиржи (2019), «О классах интервальных графов ограниченной вложенности и количества длин», Algorithmica , 81 (4): 1490–1511, arXiv : 1510.03998 , doi : 10.1007/s00453-018-0481-y, MR  3936165, S2CID  254028486
• Леккеркеркер, К. Г.; Боланд, Дж. К. (1962), «Представление конечного графа набором интервалов на действительной прямой», Fundamenta Mathematicae , 51 : 45–64, doi : 10.4064/fm-51-1-45-64
• Макки, Терри А.; Макморрис, Ф. Р. (1999), Темы в теории графов пересечений , Монографии SIAM по дискретной математике и приложениям, ISBN 978-0-89871-430-2
• Проскуровски, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями ограниченного интервала», Дискретная математика и теоретическая информатика , 3 (4): 167–176, CiteSeerX  10.1.1.39.9532
• Робертс, Ф. С. (1969), «Графы безразличия», в книге Харари, Фрэнк (ред.), Методы доказательства в теории графов , Нью-Йорк, Нью-Йорк : Academic Press , стр. 139–146, ISBN 978-0123242600, OCLC  30287853
• Вилланжер, Ингве; Heggernes, Пинар ; Пол, Кристоф; Телле, Ян Арне (2009), «Завершение интервала регулируется с фиксированными параметрами», SIAM Journal on Computing , 38 (5): 2007–2020, CiteSeerX  10.1.1.73.8999 , doi : 10.1137/070710913, S2CID  8521105
• Янг, Джойс К.; Пиппенджер, Николас (2017), «О перечислении интервальных графов», Труды Американского математического общества , Серия B, 4 : 1–3, arXiv : 1609.02479 , doi : 10.1090/bproc/27, MR  3613306, S2CID  38225412
• Чжан, Пейзен; Шон, Эрик А.; Фишер, Стюарт Г.; Кайанис, Эфтихия; Вайс, Джени; Кистлер, Сьюзан; Борн, Филип Э. (1994), «Алгоритм, основанный на теории графов, для сборки контигов при физическом картировании ДНК», Биоинформатика , 10 (3): 309–317, doi :10.1093/bioinformatics/10.3.309, PMID  7922688

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

• «Интервальный граф», Информационная система по классам графов и их включениям
• Вайсштейн, Эрик В. , «Интервальный график», MathWorld