Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с гиперграфом D-интервалов .
Семь интервалов на вещественной прямой и соответствующий семивершинный интервальный граф.

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

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

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

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

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

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

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

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

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

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

  • Граф является интервальным графом тогда и только тогда, когда его максимальные клики могут быть упорядочены так , что каждая вершина, принадлежащая двум из этих клик, также принадлежит всем кликам между ними в этом порядке. То есть для каждого with , это также тот случай, когда каждый раз . [2]
  • Граф является интервальным графом тогда и только тогда, когда он не содержит граф цикла как индуцированный подграф и является дополнением к графу сопоставимости . [3]

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

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

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

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

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

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

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

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

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

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

Подключенные треугольник свободного интервальные графики в точности гусеница деревья . [8]

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

Основная статья: Правильный интервальный график

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

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

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

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

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

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

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

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

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

Заметки [ править ]

  1. ^ а б Леккеркеркер и Боланд (1962) .
  2. ^ Фулкерсон и Гросс (1965) ; Фишберн (1985)
  3. ^ a b Гилмор и Хоффман (1964) .
  4. ^ Макки и МакМоррис (1999) ; Brandstädt, Le & Spinrad (1999)
  5. ↑ Сюй (1992) .
  6. ^ Фишберн (1985) ; Голумбик (1980)
  7. Перейти ↑ Fishburn (1985) .
  8. ^ Экхофф (1993) .
  9. ^ Робертс (1969) ; Гарди (2007)
  10. ^ Faudree, Flandrin & Ryjáček (1997) , стр. 89.
  11. ^ Proskurowski & Telle (1999) .
  12. ^ Beyerl & Джемисон (2008) .
  13. ^ Klavík, Otachi & Šejnoha (2019) .
  14. ↑ Коэн (1978) , стр.  IX – 10 .
  15. ↑ Коэн (1978) , стр.  12–33 .
  16. ^ Бар-Ной и др. (2001) .
  17. ^ Кормен и др. (2001) .
  18. ^ Zhang et al. (1994) .
  19. ^ Golumbic & Шамир (1993) .
  20. ^ Villanger et al. (2009) .
  21. ^ Близнец и др. (2014) .
  22. ^ Bodlaender (1998) .

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

  • Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; Наор, Джозеф (Сеффи) ; Шибер, Барух (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), «Субэкспоненциальный параметризованный алгоритм для надлежащего завершения интервала», в Schulz, Andreas S .; Вагнер, Доротея (ред.), Материалы 22-го ежегодного европейского симпозиума по алгоритмам (ESA 2014), Вроцлав, Польша, 8–10 сентября 2014 г. , Lecture Notes in Computer Science, 8737 , Springer-Verlag, pp. 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 , ЛВП : 1874/18312
  • Бут, KS; Lueker, GS (1976), "Проверка на последовательных единиц имущества, интервальных графов и графов плоскостности с использованием алгоритмов PQ-дерево", журнал компьютерных и системных наук , 13 (3): 335-379, DOI : 10.1016 / S0022- 0000 (76) 80045-1
  • Brandstädt, A .; Le, VB; Спинрад, JP (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 по дискретной математике , 23 (4): 1905–1953, DOI : 10,1137 / S0895480100373455
  • Экхофф, Юрген (1993), «Графики экстремальных интервалов», Журнал теории графов , 17 (1): 117–127, DOI : 10.1002 / jgt.3190170112
  • Фодри, Ральф ; Фландрин, Эвелин; Ryjáček, Зденек (1997), "лапка свободной графики - опрос А", дискретной математики , 164 (1-3): 87-147, DOI : 10.1016 / S0012-365X (96) 00045-3 , МР  1432221
  • Фишберн, Питер С. (1985), Интервальные порядки и интервальные графы: исследование частично упорядоченных множеств , Серия Wiley-Interscience по дискретной математике, Нью-Йорк: John Wiley & Sons
  • Фулкерсон, Д.Р . ; Гросс, О. А. (1965), "Заболеваемость матрицы и графы интервалов", Pacific Journal математики , 15 (3): 835-855, DOI : 10,2140 / pjm.1965.15.835
  • Гарди, Фредерик (2007), "Робертс характеристика собственных и единичных интервальных графов", Дискретная математика , 307 (22): 2906-2908, DOI : 10.1016 / j.disc.2006.04.043
  • Гилмор, ПК; Хоффман, AJ (1964), "Характеристика сопоставимости графов и графов интервалов", Canadian Journal математики , 16 : 539-548, DOI : 10,4153 / CJM-1964-055-5
  • Голумбик, Мартин Чарльз (1980), теория алгоритмических графов и совершенные графы , Academic Press, ISBN 978-0-12-289260-8
  • Голумбик, Мартин Чарльз ; Шамир, Рон (1993), "Сложность и алгоритмы рассуждения о времени: граф теоретико-подход", Журнал ACM , 40 (5): 1108-1133, CiteSeerX  10.1.1.35.528 , DOI : 10,1145 / 174147,169675 , S2CID  15708027
  • Хабиб, Мишель; МакКоннелл, Росс; Пол, Кристоф; Viennot, Лоран (2000), "Lex-BFS и уточнение раздела, с приложениями к переходной ориентации, интервал распознавания графов и последовательных единиц тестирования" , Теоретическая информатика , 234 (1-2): 59-84, DOI : 10.1016 / S0304-3975 (97) 00241-7
  • Сюй, Вэнь-Лянь (1992), «Простой тест для интервальных графов», в Mayr, Ernst W. (ed.), 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
  • Клавик, Павел; Отачи, Йота; Шейноха, Иржи (2019), «О классах интервальных графов ограниченной вложенности и подсчета длин», Algorithmica , 81 (4): 1490–1511, arXiv : 1510.03998 , doi : 10.1007 / s00453-018-0481-y , Руководство по ремонту  3936165
  • Lekkerkerker, CG ; Боланд, JC (1962), "Представление конечного графа с помощью множества интервалов на вещественной оси", Fundamenta Mathematicae , 51 : 45-64, DOI : 10,4064 / FM-51-1-45-64
  • Макки, Терри А .; Макморрис, FR (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и приложениям, ISBN 978-0-89871-430-2
  • Проскуровский, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями с ограниченным интервалом», Дискретная математика и теоретическая информатика , 3 (4): 167–176, CiteSeerX  10.1.1.39.9532
  • Робертс, Ф.С. (1969), «Графы безразличия», в Harary, Frank (ed.), Proof Techniques in Graph Theory , New York, NY : Academic Press , стр. 139–146, ISBN. 978-0123242600, OCLC  30287853
  • Виллангер, Ингве; Хеггернес, Пинар ; Пол, Кристоф; Телле, Ян Арне (2009), «Завершение интервала с фиксированным параметром, управляемым», SIAM Journal on Computing , 38 (5): 2007–2020, CiteSeerX  10.1.1.73.8999 , doi : 10.1137 / 070710913
  • Чжан, Пейсен; Schon, Eric A .; Фишер, Стюарт Дж .; Каянис, Эфтихия; Вайс, Джени; Кистлер, Сьюзен; Борна, Филип Е. (1994), «алгоритм , основанный на теории графов для сборки контигов в физическом отображении ДНК», биоинформатики , 10 (3): 309-317, DOI : 10,1093 / биоинформатики / 10.3.309 , PMID  7922688

Внешние ссылки [ править ]

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