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

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

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

Визначення

Нехай ${\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].

Див. також

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