Граф дуг кола

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

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

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

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

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

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

і

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Посилання

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 (23 січня). — С. 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 (23 січня). — С. 1–24. — DOI:10.1137/0209001..
Ross McConnell. Linear-time recognition of circular-arc graphs // Algorithmica. — 2003. — Т. 37, вип. 2 (23 січня). — С. 93–147. — DOI:10.1007/s00453-003-1032-7.
Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-444-51530-5. 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 (23 січня). — С. 390–403. — DOI:10.1137/S0097539792269095..
Fanica Gavril. Algorithms on circular-arc graphs // Networks. — 1974. — Т. 4, вип. 4 (23 січня). — С. 357–369. — DOI:10.1002/net.3230040407.
circular arc graph. Information System on Graph Class Inclusions.
Maria Chudnovsky, Paul Seymour. Claw-free graphs. III. Circular interval graphs // Journal of Combinatorial Theory. — 2008. — Т. 98, вип. 4 (23 січня). — С. 812–834. — (Series B). — DOI:10.1016/j.jctb.2008.03.001..

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[FOOTNOTETucker1980-1] Tucker, 1980.

[FOOTNOTEMcConnell2003-2] McConnell, 2003.

[FOOTNOTEChudnovsky,_Seymour2008-3] Chudnovsky, Seymour, 2008.

[FOOTNOTEDeng_et_al1996-4] Deng et al, 1996.

[FOOTNOTEGavril1974-5] Gavril, 1974.

[FOOTNOTEJoeris_et_al2009-6] Joeris et al, 2009.