График дуги окружности

В теории графов граф дуг окружности — это граф пересечений набора дуг окружности. Он имеет одну вершину для каждой дуги в наборе и ребро между каждой парой вершин, соответствующих пересекающимся дугам.

Формально пусть

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, называется моделью дуг .

Признание

Такер (1980) продемонстрировал первый алгоритм полиномиального распознавания графов дуги окружности, который работает в ${\mathcal {O}}(n^{3})$ время. МакКоннелл (2003) дал первое линейное $({\mathcal {O}}(n+m))$ алгоритм распознавания времени, где $m$ это количество ребер. Совсем недавно Каплан и Нуссбаум ^[1] разработал более простой алгоритм распознавания линейного времени.

Связь с другими классами графов

Графы дуг окружности являются естественным обобщением интервальных графов . Если граф дуги окружности G имеет дуговую модель, которая оставляет некоторую точку круга непокрытой, круг можно разрезать в этой точке и растянуть до линии, что приводит к интервальному представлению. Однако, в отличие от интервальных графов, графы дуг окружности не всегда идеальны , поскольку нечетные циклы без хорд C ₅ , C ₇ и т. д. являются графами дуг окружности.

Некоторые подклассы

В дальнейшем пусть $G=(V,E)$ быть произвольным графом.

Единичные дуговые графики

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

Число помеченных единичных дуг окружностей на n вершинах определяется выражением $(n+2){\binom {2n-1}{n-1}}-2^{2n-1}$ . ^[2]

Правильные графы дуги окружности

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

Графики дуги окружности Хелли

$G$ является графом круговых дуг Хелли , если существует соответствующая модель дуги, такая что дуги составляют семейство Хелли . Гаврил (1974) дает характеристику этого класса, подразумевающую ${{\mathcal {O}}(n^{3})}$ алгоритм распознавания.

Джорис и др. (2009) дают другие характеристики этого класса, которые подразумевают алгоритм распознавания, работающий за время O(n+m), когда входными данными является граф. Если входной граф не является дуговым графом Хелли, то алгоритм возвращает свидетельство об этом факте в виде запрещенного индуцированного подграфа. Они также предложили алгоритм за время O(n) для определения того, обладает ли данная модель дуги окружности свойством Хелли.

Приложения

Дуговые графики полезны при моделировании периодических распределения ресурсов задач при исследовании операций . Каждый интервал представляет собой повторяющийся во времени запрос ресурса за определенный период.

Примечания

^ Каплан, Хаим; Нуссбаум, Яхав (1 ноября 2011 г.). «Простое распознавание дуговых графов в линейном времени». Алгоритмика . 61 (3): 694–737. CiteSeerX 10.1.1.76.2480 . дои : 10.1007/s00453-010-9432-y . ISSN 0178-4617 .
^ Александерссон, Пер; Панова, Грета (декабрь 2018 г.). «Полиномы LLT, хроматические квазисимметричные функции и графики с циклами». Дискретная математика . 341 (12): 3453–3482. arXiv : 1705.10353 . дои : 10.1016/j.disc.2018.09.001 .
^ Jump up to: ^а ^б Описано другим, но эквивалентным определением Чудновского и Сеймура (2008) .
^ Дэн, Ад и Хуан (1996), стр. ?

Ссылки

Чудновская Мария ; Сеймур, Пол (2008), «Графы без когтей. III. Графы круговых интервалов» (PDF) , Журнал комбинаторной теории , серия B, 98 (4): 812–834, doi : 10.1016/j.jctb.2008.03. 001 , МР 2418774 .
Дэн, Сяоте; Черт, Павол ; Хуанг, Цзин (1996), «Алгоритмы представления в линейном времени для правильных графов дуг окружности и правильных интервальных графов», SIAM Journal on Computing , 25 (2): 390–403, doi : 10.1137/S0097539792269095 .
Гаврил, Фаника (1974), «Алгоритмы на графах окружности», Networks , 4 (4): 357–369, doi : 10.1002/net.3230040407 .
Голумбик, Мартин Чарльз (1980), алгоритмическая теория графов и совершенные графы , Academic Press, ISBN 978-0-444-51530-8 , заархивировано из оригинала 22 мая 2010 г. , получено 21 мая 2008 г. Второе издание, Анналы дискретной математики 57, Elsevier, 2004.
Джоерис, Бенсон Л.; Лин, Мин Чи; МакКоннелл, Росс М.; Спинрад, Джереми П.; Шварцфитер, Джейм Л. (2009), «Распознавание в линейном времени моделей и графиков гелли с круговыми дугами», Algorithmica , 59 (2): 215–239, CiteSeerX 10.1.1.298.3038 , doi : 10.1007/s00453-009- 9304-5 .
МакКоннелл, Росс (2003), «Распознавание графов дуг окружности в линейном времени», Algorithmica , 37 (2): 93–147, CiteSeerX 10.1.1.22.4725 , doi : 10.1007/s00453-003-1032-7 .
Такер, Алан (1980), «Эффективный тест для графов дуг окружности», SIAM Journal on Computing , 9 (1): 1–24, doi : 10.1137/0209001 .

Внешние ссылки

Круговой дуговой граф , Информационная система по включению классов графов

[1] Каплан, Хаим; Нуссбаум, Яхав (1 ноября 2011 г.). «Простое распознавание дуговых графов в линейном времени». Алгоритмика . 61 (3): 694–737. CiteSeerX 10.1.1.76.2480 . дои : 10.1007/s00453-010-9432-y . ISSN 0178-4617 .

[2] Александерссон, Пер; Панова, Грета (декабрь 2018 г.). «Полиномы LLT, хроматические квазисимметричные функции и графики с циклами». Дискретная математика . 341 (12): 3453–3482. arXiv : 1705.10353 . дои : 10.1016/j.disc.2018.09.001 .

[claw3-3] Jump up to: ^а ^б Описано другим, но эквивалентным определением Чудновского и Сеймура (2008) .

[4] Дэн, Ад и Хуан (1996), стр. ?

[1]

[2]

[3]

[4]