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

Граф пересечения для набора дуг на окружности

Граф дуг окружности (слева) и соответствующая модель дуги (справа).

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

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

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

Признание

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

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

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

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

Далее пусть будет произвольным графом. ${\displaystyle G=(V,E)}$

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

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

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

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

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

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

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

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

Приложения

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

Примечания

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

Ссылки

• Чудновски, Мария ; Сеймур, Пол (2008), «Графы без клешней. III. Круговые интервальные графы» (PDF) , Журнал комбинаторной теории , Серия B, 98 (4): 812–834, doi : 10.1016/j.jctb.2008.03.001 , MR  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.
• Golumbic, Martin Charles (1980), Алгоритмическая теория графов и совершенные графы, Academic Press, ISBN 978-0-444-51530-8, архивировано из оригинала 2010-05-22 , извлечено 2008-05-21. Второе издание, Annals of Discrete Mathematics 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.

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

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