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

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

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

Определение[править | править вики-текст]

Пусть \{I_1, I_2, ..., I_n\} \subset P(R) — множество интервалов.

Соответствующий интервальный граф — это G = (V, E), где

  • V = \{I_1, I_2,..., I_n\}, и
  • \{I_\alpha, I_\beta\} \in E если и только если I_\alpha \cap I_\beta \ne \emptyset.

Из этого построения можно получить общие свойства интервальных графов. Так, граф G является интервальным тогда и только тогда, когда наибольшие клики графа G могут быть упорядочены M_1, M_2,..., M_k так, что для любой v \in M_i \cap M_k, где i < k, выполняется также v \in M_j для любого M_j, i \le j \le k.[1]

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

Определить, является ли граф G = (V, E) интервальным можно за время O(|V|+|E|) путём упорядочения наибольших клик графа G.

Первоначальный алгоритм распознавания за линейное время Бута и Люкера (Booth, Lueker 1976) основывается на сложной структуре PQ-деревьев, но Хабиб, МакКонел, Пауль и Вьенно (Habib, McConnell, Paul, Viennot 2000) показали как решить задачу проще, используя лексикографический поиск в ширину[en] и основываясь на факте, что граф является интервальным тогда и только тогда, когда он хордален и его дополнение — граф сравнимости[1][2].

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

Интервальные графы являются хордальными и, следовательно, совершенными[1][2]. Их дополнения принадлежат к классу графов сравнимости[3], и отношение сравнения — в точности итнервальный порядок[en][1].

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

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

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

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

Родственные интервальные графы без треугольников — это в точности деревья-гусеницы[en][7].

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

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

Другие приложения включают генетику, биоинформатику, и информатику. Поиск множества отрезков, представляющих интервальный граф, может быть использован в качестве методики сборки непрерывных последовательностей в ДНК[10]. Интервальные графы используются в постановке задач размещения ресурсов[en] в исследовании операций и планировании выполнения задач. Каждый промежуток представляет запрос на ресурс на определённый период времени. Задача нахождения независимого множества максимального веса графа представляет задачу поиска лучшего подмножества запросов, которые можно выполнить без конфликтов[11].

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber A unified approach to approximating resource allocation and scheduling // Journal of the ACM. — 2001. — В. 5. — Т. 48. — С. 1069–1090. — DOI:10.1145/502102.502107.
  • Hans L. Bodlaender A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — В. 1–2. — Т. 209. — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4.
  • K. S. Booth, G. S. Lueker Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // J. Comput. System Sci.. — 1976. — В. 3. — Т. 13. — С. 335–379. — DOI:10.1016/S0022-0000(76)80045-1.
  • Joel E. Cohen Food webs and niche space. — Princeton, NJ: Princeton University Press, 1978. — Vol. 11. — P. xv+1–190. — ISBN 978-0-691-08202-8
  • Eckhoff Extremal interval graphs // Journal of Graph Theory. — 1993. — В. 1. — Т. 17. — С. 117–127. — DOI:10.1002/jgt.3190170112.
  • Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček Claw-free graphs — A survey // Discrete Mathematics. — 1997. — В. 1–3. — Т. 164. — С. 87–147. — DOI:10.1016/S0012-365X(96)00045-3.
  • Peter C. Fishburn Interval orders and interval graphs: A study of partially ordered sets. — New York, 1985. — (Wiley-Interscience Series in Discrete Mathematics).
  • D. R. Fulkerson, O. A. Gross Incidence matrices and interval graphs // Pacific Journal of Mathematics. — 1965. — Т. 15. — С. 835–855..
  • P. C. Gilmore, A. J. Hoffman A characterization of comparability graphs and of interval graphs // Can. J. Math.. — 1964. — Т. 16. — С. 539–548. — DOI:10.4153/CJM-1964-055-5.
  • Martin Charles Golumbic Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-12-289260-7..
  • Martin Charles Golumbic, Ron Shamir Complexity and algorithms for reasoning about time: a graph-theoretic approach // J. Assoc. Comput. Mach.. — 1993. — Т. 40. — С. 1108–1133..
  • Michel Habib, Ross McConnell, Christophe Paul, Laurent Viennot Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing // Theor. Comput. Sci.. — 2000. — Т. 234. — С. 59–84. — DOI:10.1016/S0304-3975(97)00241-7.
  • F.S. Roberts Proof Techniques in Graph Theory. — Academic Press, New York, 1969. — С. 139–146..
  • Peisen Zhang, Eric A. Schon, Stuart G. Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler, Philip E. Bourne An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA // Bioinformatics. — 1994. — В. 3. — Т. 10. — С. 309–317. — DOI:10.1093/bioinformatics/10.3.309.

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