Інтервальний граф

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

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

Визначення

Нехай ${\displaystyle \{I_{1},I_{2},...,I_{n}\}\subset P(R)}$ — множина інтервалів.

Відповідний інтервальний граф — це G= (V, E), де

• ${\displaystyle V=\{I_{1},I_{2},...,I_{n}\}}$ і
• ${\displaystyle \{I_{\alpha },I_{\beta }\}\in E}$ тоді й тільки тоді, коли ${\displaystyle I_{\alpha }\cap I_{\beta }\neq \emptyset }$.

З цієї побудови можна отримати загальні властивості інтервальних графів. Так, граф G є інтервальним тоді й тільки тоді, коли найбільші кліки графу G можуть бути впорядковані ${\displaystyle M_{1},M_{2},...,M_{k}}$ так, що для будь-якого ${\displaystyle v\in M_{i}\cap M_{k}}$, де ${\displaystyle i<k}$, виконується також ${\displaystyle v\in M_{j}}$ для будь-якого ${\displaystyle M_{j},i\leq j\leq k}$^[1].

Ефективні алгоритми розпізнавання

Визначити, чи є граф ${\displaystyle G=(V,E)}$ інтервальним можна за час ${\displaystyle O(|V|+|E|)}$ шляхом впорядкування найбільших клік графу G.

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

Пов'язані сім'ї графів

Інтервальні графи є хордальними, і, як наслідок, досконалими^[1][2]. Їх доповнення належать до класу графів порівняння^[3], і відношення порівняння — це інтервальний порядок^[1].

Інтервальні графи, які мають інтервальне представлення, в якому будь-які два інтервали або не перетинаються, або вкладені, є тривіальними досконалими графами.

Правильні інтервальні графи — це інтервальні графи, які мають інтервальне представлення, в якому жоден інтервал не є власною підмножиною жодного іншого інтервалу. Одиничні інтервальні графи — це інтервальні графи, які мають інтервальне представлення, в якому кожен інтервал має одиничну довжину. Будь-який правильний інтервальний граф не має клешень. Але обернене твердження не є правильним — граф без клешень не обов'язково є правильним інтервальним графом^[4]. Якщо набір сегментів є множиною, тобто повторення сегментів не є дозволеним, то граф є одиничним інтервальним графом тоді й тільки тоді, коли він є правильним інтервальним графом^[5].

Графи перетинів дуг кола утворюють графи дуг кола — клас графів, який містить інтервальні графи. Трапецеїдальні графи, перетин трапецій, всі паралельні сторони яких лежать на двох паралельних прямих, є узагальненням інтервальних графів.

Шляхова ширина інтервального графа на одиницю менша, ніж розмір максимальної кліки (або, що є еквівалентним, на одиницю менша, ніж його хроматичне число), а шляхова ширина будь-якого графа G дорівнює найменшій шляховій ширині інтервального графа, який містить G як підграф.

Споріднені інтервальні графи без трикутників — це те ж, що і гусеничне дерево^[6].

Застосування

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

Коуен застосував інтервальні графи у математичних моделях популяцій, особливо харчових ланцюгів^[8].

Інші застосування включають генетику, біоінформатику та інформатику. Пошук множини відрізків, які представляють інтервальний граф, може використовуватися як методика збірки неперервних послідовностей в ДНК^[9]. Інтервальні графи використовуються в підстановці задач на розміщення ресурсів, у дослідженнях операцій і плануванні виконання задач. Кожний відрізок представляє запит на ресурс на певний період часу. Задача знаходження незалежної множини максимальної ваги графу представляє задачу пошуку кращої підмножини запитів, які можна виконати без конфліктів^[10].

Див. також

• Граф Мейнеля

Примітки

1. Fishburn, 1985.
2. Golumbic, 1980.
3. Gilmore, Hoffman, 1964.
4. Faudree, Flandrin, Ryjáček, 1997, с. 89
5. Roberts, 1969.
6. Eckhoff, 1993.
7. Cohen, 1978 ix-10
8. Cohen, 1978 12-33
9. Zhang та ін., 1994.
10. Bar-Noy, Bar-Yehuda, Freund, Naor, 2001.

Література

• 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. — Т. 48, вип. 5. — С. 1069—1090. — DOI:10.1145/502102.502107.
• Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1—2. — С. 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. — Т. 13, вип. 3. — С. 335—379. — DOI:10.1016/S0022-0000(76)80045-1.
• Joel E. Cohen (1978). Food webs and niche space. Monographs in Population Biology. Т. 11. Princeton, NJ: Princeton University Press. с. xv+1–190. ISBN 978-0-691-08202-8.
• Eckhoff. Extremal interval graphs // Journal of Graph Theory. — 1993. — Т. 17, вип. 1. — С. 117—127. — DOI:10.1002/jgt.3190170112.
• Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. Claw-free graphs — A survey // Discrete Mathematics. — 1997. — Т. 164, вип. 1—3. — С. 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. — Т. 10, вип. 3. — С. 309—317. — DOI:10.1093/bioinformatics/10.3.309.

Посилання

• interval graph. Information System on Graph Classes and their Inclusions. Архів оригіналу за 7 листопада 2016. Процитовано 19 листопада 2016.
• Weisstein, Eric W. Інтервальний граф(англ.) на сайті Wolfram MathWorld.