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

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

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

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

$I_1,I_2,\dots ,I_n\subset C_1$

— множество дуг. Тогда соответствующий им граф дуг окружности — это G = (V, E), где

$V=\{I_1,I_2,\dots ,I_n\}$

и

$\{I_{\alpha },I_{\beta }\}\in E⟺I_{\alpha }\cap I_{\beta }\ne \varnothing .$

Семейство дуг, соответствующее графу G, называется дуговой моделью.

Распознавание

Тукер Шаблон:Sfn нашёл первый полиномиальный алгоритм распознавания для графов дуг окружности, работающий за время $𝒪(n^3)$. Позднее МакКоннел Шаблон:Sfn нашёл первый линейный алгоритм распознавания за время $(𝒪(n+m))$.

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

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

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

Ниже пусть $G=(V,E)$ — произвольный граф.

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

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

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

$G$ является правильным графом дуг окружности (или цикловым интервальным графомШаблон:Sfn), если существует соответствующая дуговая модель, в которой никакая дуга не содержит полностью другую. Распознавание таких графов и построение правильной дуговой модели можно осуществить за линейное время $(𝒪(n+m))$.Шаблон:Sfn

Циркулярные графы дуг Хелли

$G$ является циркулярным графом дуг Хелли, если существует соответствующая дуговая модель такая, что дуги образуют семейство Хелли. ГаврилШаблон:Sfn даёт описание этого класса, из которого вытекает алгоритм распознавания за время $𝒪(n^3)$.

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

Приложения

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

Ссылки

• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Книга Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Cite web
• Шаблон:Статья.