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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

• Граф является графом интервалов тогда и только тогда, когда он хордальный и свободный от 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, vol. 191, стр. 117–128, arXiv : 1109.6675 , MR  2489816.
• Близнец Иван; Фомин Федор Владимирович; Пилипчук, Марцин; Пилипчук, Михал (2014), «Субэкспоненциальный параметризованный алгоритм для правильного завершения интервала», у Шульца, Андреас С.; Вагнер, Доротея (ред.), Труды 22-го ежегодного европейского симпозиума по алгоритмам (ESA 2014), Вроцлав, Польша, 8–10 сентября 2014 г. , Конспекты лекций по информатике, том. 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 -дендрарий графов с ограниченной шириной дерева», Theoretical Computer Science , 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-дерева», Journal of Computer and System Sciences , 13 (3): 335–379, doi : 10.1016/S0022- 0000(76)80045-1
• Брандштедт, А.; Ле, В.Б.; Спинрад, JP (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 978-0-89871-432-6
• Коэн, Джоэл Э. (1978), Пищевые сети и пространство ниш , Монографии по популяционной биологии, том. 11, Принстон, Нью-Джерси: Издательство Принстонского университета, стр. 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), «Экстремальные интервальные графики», Journal of Graph Theory , 17 (1): 117–127, doi : 10.1002/jgt.3190170112
• Фаудри, Ральф ; Фландрин, Эвелин; Рыячек, Зденек (1997), «Графы без клешней — обзор», Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR  1432221
• Фишберн, Питер К. (1985), Интервальные порядки и интервальные графики: исследование частично упорядоченных множеств , Серия Wiley-Interscience по дискретной математике, Нью-Йорк: John Wiley & Sons
• Фулкерсон, Др . ; Гросс, О.А. (1965), «Матрицы заболеваемости и интервальные графики», Pacific Journal of Mathematics , 15 (3): 835–855, doi : 10.2140/pjm.1965.15.835
• Гарди, Фредерик (2007), «Характеристика Робертса собственных графов и графов единичных интервалов», Discrete Mathematics , 307 (22): 2906–2908, doi : 10.1016/j.disc.2006.04.043
• Гилмор, ПК; Хоффман, AJ (1964), «Характеристика графиков сопоставимости и интервальных графиков», Canadian Journal of Mathematics , 16 : 539–548, doi : 10.4153/CJM-1964-055-5
• Голумбик, Мартин Чарльз (1980), алгоритмическая теория графов и совершенные графы , Academic Press, ISBN 978-0-12-289260-8
• Голумбик, Мартин Чарльз ; Шамир, Рон (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 и уточнение разделов с приложениями к транзитивной ориентации, распознаванию интервальных графов и тестированию последовательных», Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016/ С0304-3975(97)00241-7
• Хэнлон, Фил (1982), «Подсчет интервальных графиков», Transactions of the American Mathematical Society , 272 (2): 383–426, doi : 10.2307/1998705 , JSTOR  1998705, MR  0662044
• Сюй, Вэнь-Лянь (1992), «Простой тест для интервальных графов», Майр, Эрнст В. (редактор), Теоретико-графовые концепции в информатике, 18-й международный семинар, WG '92, Висбаден-Наурод, Германия , 19–20 июня 1992 г., Труды , Конспекты лекций по информатике, вып. 657, Спрингер, стр. 11–16, номер документа : 10.1007/3-540-56402-0_31.
• Клавик, Павел; Отачи, Йота; Шейноха, Иржи (2019), «О классах интервальных графов ограниченной вложенности и подсчета длин», Algorithmica , 81 (4): 1490–1511, arXiv : 1510.03998 , doi : 10.1007/s00453-018-0481-y, МР  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), «Классы графов с моделями с ограниченными интервалами», Discrete Mathematics & Theoretical Computer Science , 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), «Алгоритм, основанный на теории графов, для сборки контигов при физическом картировании ДНК», Bioinformatics , 10 (3): 309–317, doi : 10.1093/bioinformatics/10.3.309, PMID  7922688

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

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