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

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

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

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

Определение [ править ]

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

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

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

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

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

Характеристики [ править ]

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

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

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

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

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

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

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

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

Родственные семейства графов [ править ]

Характеризуя интервальные графы как хордальные графы без AT, ^[1] Графы интервалов являются сильно хордальными графами и, следовательно, совершенными графами . Их дополнения относятся к классу графов сравнимости , ^[3] а отношения сравнимости — это именно интервальные порядки . ^[7]

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

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

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

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

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

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

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

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

Приложения [ править ]

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

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

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

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

Завершение интервалов и ширина пути [ править ]

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

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

Комбинаторное перечисление [ править ]

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

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

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

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

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

Примечания [ править ]

^ Jump up to: ^а ^б Леккеркеркер и Боланд (1962) .
^ Фулкерсон и Гросс (1965) ; Фишберн (1985)
^ Jump up to: ^а ^б Гилмор и Хоффман (1964) .
^ Макки и МакМоррис (1999) ; Брандштедт, Ле и Спинрад (1999)
^ Сюй (1992) .
^ Фишберн (1985) ; Голуббик (1980)
^ Фишберн (1985) .
^ Экхофф (1993) .
^ Робертс (1969) ; Вкусно (2007)
^ Фаудри, Фландрин и Рыячек (1997) , с. 89.
^ Проскуровски и Телле (1999) .
^ Байерл и Джеймисон (2008) .
^ Клавик, Отачи и Шейноха (2019) .
^ Коэн (1978) , стр. ix–10 .
^ Коэн (1978) , стр. 12–33 .
^ Bar-Noy et al. (2001) .
^ Кормен и др. (2001) , с. 379.
^ Чжан и др. (1994) .
^ Голумбик и Шамир (1993) .
^ Вилланджер и др. (2009) .
^ Bliznets et al. (2014) .
^ Бодлендер (1998) .
^ Хэнлон (1982) , Таблица VIII, стр. 422.
^ Хэнлон (1982) , Таблица VII, стр. 421.
^ Ян и Пиппенджер (2017) .
^ Боннет и др. (2022) .

Ссылки [ править ]

Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; Наор, Джозеф (Сеффи) ; Шибер, Барух (2001), «Единый подход к аппроксимации распределения ресурсов и планирования», Journal of the 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, Springer, стр. 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

[FOOTNOTELekkerkerkerBoland1962-1] Jump up to: ^а ^б Леккеркеркер и Боланд (1962) .

[2] Фулкерсон и Гросс (1965) ; Фишберн (1985)

[FOOTNOTEGilmoreHoffman1964-3] Jump up to: ^а ^б Гилмор и Хоффман (1964) .

[4] Макки и МакМоррис (1999) ; Брандштедт, Ле и Спинрад (1999)

[FOOTNOTEHsu1992-5] Сюй (1992) .

[6] Фишберн (1985) ; Голуббик (1980)

[FOOTNOTEFishburn1985-7] Фишберн (1985) .

[FOOTNOTEEckhoff1993-8] Экхофф (1993) .

[9] Робертс (1969) ; Вкусно (2007)

[FOOTNOTEFaudreeFlandrinRyjáček199789-10] Фаудри, Фландрин и Рыячек (1997) , с. 89.

[FOOTNOTEProskurowskiTelle1999-11] Проскуровски и Телле (1999) .

[FOOTNOTEBeyerlJamison2008-12] Байерл и Джеймисон (2008) .

[FOOTNOTEKlavíkOtachiŠejnoha2019-13] Клавик, Отачи и Шейноха (2019) .

[FOOTNOTECohen1978[httpsbooksgooglecombooksprincetonhlenqintervalgraphvidISBN9780691082028redir_escyvsnippetq22interval20graph22ffalse_ix–10]-14] Коэн (1978) , стр. ix–10 .

[FOOTNOTECohen1978[httpsbooksgooglecombooksprincetonhlenqintervalgraphvidISBN9780691082028redir_escyvsnippetq22interval20graph22ffalse_12–33]-15] Коэн (1978) , стр. 12–33 .

[FOOTNOTEBar-NoyBar-YehudaFreundNaor2001-16] Bar-Noy et al. (2001) .

[FOOTNOTECormenLeisersonRivestStein2001379-17] Кормен и др. (2001) , с. 379.

[FOOTNOTEZhangSchonFischerCayanis1994-18] Чжан и др. (1994) .

[FOOTNOTEGolumbicShamir1993-19] Голумбик и Шамир (1993) .

[FOOTNOTEVillangerHeggernesPaulTelle2009-20] Вилланджер и др. (2009) .

[FOOTNOTEBliznetsFominPilipczukPilipczuk2014-21] Bliznets et al. (2014) .

[FOOTNOTEBodlaender1998-22] Бодлендер (1998) .

[FOOTNOTEHanlon1982Table_VIII,_p._422-23] Хэнлон (1982) , Таблица VIII, стр. 422.

[FOOTNOTEHanlon1982Table_VII,_p._421-24] Хэнлон (1982) , Таблица VII, стр. 421.

[FOOTNOTEYangPippenger2017-25] Ян и Пиппенджер (2017) .

[FOOTNOTEBonnetKimThomasséWatrigant2022-26] Боннет и др. (2022) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]