Граф дуг кола

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

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

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

${\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}}$

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

${\displaystyle V=\{I_{1},I_{2},\ldots ,I_{n}\}}$

і

${\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .}$

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

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

Тукер[1] знайшов перший поліноміальний алгоритм розпізнавання для графів дуг кола, що працює за час ${\displaystyle {\mathcal {O}}(n^{3})}$. Пізніше Макконнел[2] знайшов перший лінійний алгоритм розпізнавання за час ${\displaystyle ({\mathcal {O}}(n+m))}$.

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

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

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

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

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

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

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

${\displaystyle G}$ є правильним графом дуг кола (або цикловим інтервальним графом[3]), якщо існує відповідна дугова модель, у якій жодна дуга не містить повністю іншої. Розпізнати такий граф і побудувати правильну дугову модель можна за лінійний час ${\displaystyle ({\mathcal {O}}(n+m))}$.[4]

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

${\displaystyle G}$ є циркулярним графом дуг Геллі, якщо існує відповідна дугова модель така, що дуги утворюють сімейство Геллі. Гаврил[5] дає опис цього класу, з якого випливає алгоритм розпізнавання за час ${\displaystyle {{\mathcal {O}}(n^{3})}}$.

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

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

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

Див. також

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

Примітки

1. Tucker, 1980.
2. McConnell, 2003.
3. Chudnovsky, Seymour, 2008.
4. Deng et al, 1996.
5. Gavril, 1974.
6. Joeris et al, 2009.

Посилання

• Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Linear-Time Recognition of Helly Circular-Arc Models and Graphs // Algorithmica. — 2009. — Т. 59, вип. 2 (27 грудня). — С. 215–239. — DOI:10.1007/s00453-009-9304-5..
• Alan Tucker. An efficient test for circular-arc graphs // SIAM Journal on Computing. — 1980. — Т. 9, вип. 1 (27 грудня). — С. 1–24. — DOI:10.1137/0209001..
• Ross McConnell. Linear-time recognition of circular-arc graphs // Algorithmica. — 2003. — Т. 37, вип. 2 (27 грудня). — С. 93–147. — DOI:10.1007/s00453-003-1032-7.
• Martin Charles Golumbic. [1] — Academic Press, 1980. — ISBN 0-444-51530-5. Архівовано з джерела 22 травня 2010 Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Xiaotie Deng, Pavol Hell, Jing Huang. Linear-Time representation algorithms for proper circular-arc graphs and proper interval graphs // SIAM Journal on Computing. — 1996. — Т. 25, вип. 2 (27 грудня). — С. 390–403. — DOI:10.1137/S0097539792269095..
• Fanica Gavril. Algorithms on circular-arc graphs // Networks. — 1974. — Т. 4, вип. 4 (27 грудня). — С. 357–369. — DOI:10.1002/net.3230040407.
• circular arc graph. Information System on Graph Class Inclusions. Архів оригіналу за 21 грудня 2013. Процитовано 20 травня 2021.
• Maria Chudnovsky, Paul Seymour. Claw-free graphs. III. Circular interval graphs // Journal of Combinatorial Theory. — 2008. — Т. 98, вип. 4 (27 грудня). — С. 812–834. — (Series B). — DOI:10.1016/j.jctb.2008.03.001. Архівовано з джерела 25 червня 2010. Процитовано 20 травня 2021..