YaChudo

Граф дуг кола

Переглядів: 0. Оновлено 05.11.2026.

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

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

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

I 1 , I 2 , … , I n ⊂ C 1 {\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}}

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

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

і

{ I α , I β } ∈ E ⟺ I α ∩ I β ≠ ∅ . {\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .}

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

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

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

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

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

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

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

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

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

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

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

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

G {\displaystyle G} є циркулярним графом дуг Геллі, якщо існує відповідна дугова модель така, що дуги утворюють сімейство Геллі. Гаврил[5] дає опис цього класу, з якого випливає алгоритм розпізнавання за час O ( n 3 ) {\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 (29 жовтня). — С. 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 (29 жовтня). — С. 1–24. — DOI:10.1137/0209001..
  • Ross McConnell. Linear-time recognition of circular-arc graphs // Algorithmica. — 2003. — Т. 37, вип. 2 (29 жовтня). — С. 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 (29 жовтня). — С. 390–403. — DOI:10.1137/S0097539792269095..
  • Fanica Gavril. Algorithms on circular-arc graphs // Networks. — 1974. — Т. 4, вип. 4 (29 жовтня). — С. 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 (29 жовтня). — С. 812–834. — (Series B). — DOI:10.1016/j.jctb.2008.03.001. Архівовано з джерела 25 червня 2010. Процитовано 20 травня 2021..

Джерело: стаття у Вікіпедії та історія редагувань (автори).