Граф дуг кола

Граф дуг кола (ліворуч) і відповідна модель дуг (праворуч).

У теорії графів графом дуг кола називають граф перетинів множини дуг кола. Граф має одну вершину для кожної дуги кола і ребро між двома вершинами, якщо відповідні дуги перетинаються.

Формально, нехай

$I_1,I_2,\dots ,I_n\subset C_1$

— множина дуг. Тоді відповідний їм граф дуг кола — це G = (V, E), де

$V=\{I_1,I_2,\dots ,I_n\}$

і

$\{I_{\alpha },I_{\beta }\}\in E⟺I_{\alpha }\cap I_{\beta }\ne \varnothing .$

Сімейство дуг, відповідне графу G, називають дугового моделлю.

Розпізнавання

ТукерШаблон:Sfn знайшов перший поліноміальний алгоритм розпізнавання для графів дуг кола, що працює за час $𝒪(n^3)$. Пізніше МакконнелШаблон:Sfn знайшов перший лінійний алгоритм розпізнавання за час $(𝒪(n+m))$.

Зв'язок з іншими класами графів

Графи дуг кола є природним узагальненням інтервальних графів. Якщо граф дуг кола G має дугову модель, що не покриває деяких точок кола, коло можна розірвати в такій точці і випростати у відрізок, що дає інтервальне подання. Однак, на відміну від інтервальних графів, графи дуг кола не завжди досконалі, оскільки непарні цикли без хорд C_5, C₇ тощо є графами дуг кола.

Деякі підкласи

Нижче нехай $G=(V,E)$ — довільний граф.

Графи одиничних дуг кола

$G$ є графом одиничних дуг кола, якщо існує дугова модель, у якій всі дуги мають однакову довжину.

Правильні графи дуг кола

$G$ є правильним графом дуг кола (або цикловим інтервальним графомШаблон:Sfn), якщо існує відповідна дугова модель, у якій жодна дуга не містить повністю іншої. Розпізнати такий граф і побудувати правильну дугову модель можна за лінійний час $(𝒪(n+m))$.Шаблон:Sfn

Циркулярні графи дуг Геллі

$G$ є циркулярним графом дуг Геллі, якщо існує відповідна дугова модель така, що дуги утворюють сімейство Геллі. ГаврилШаблон:Sfn дає опис цього класу, з якого випливає алгоритм розпізнавання за час $𝒪(n^3)$.

Йоріс і співавториШаблон:Sfn дають інші характеристики (зокрема, перелік заборонених породжених підграфів) цього класу, звідки випливає алгоритм розпізнавання, що працює за час O(n+m). Якщо вхідний граф не є циркулярним графом дуг Геллі, то алгоритм повертає підтвердження цього факту у вигляді забороненого породженого підграфа. Вони дали також алгоритм визначення, чи утворює дана циркулярна дугова модель сімейство Геллі, за час O(n).

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

Циркулярні графи дуг корисні в моделюванні задач періодичного розподілу ресурсів у дослідженні операцій. Кожен інтервал подає запит на певний період, повторюваний у часі.

Див. також

• Граф одиничних кругів

Посилання

• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Книга Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Cite web
• Шаблон:Стаття.