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

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

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

и

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

Распознавание Тукер нашёл первый полиномиальный алгоритм распознавания для графов дуг окружности, работающий за время . Позднее МакКоннел нашёл первый линейный алгоритм распознавания за время .

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

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

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

Ниже пусть  — произвольный граф.

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

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

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

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

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

является циркулярным графом дуг Хелли, если существует соответствующая дуговая модель такая, что дуги образуют семейство Хелли. Гаврил даёт описание этого класса, из которого вытекает алгоритм распознавания за время .

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

Приложения

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

Примечания

Ссылки . .

Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004. .

.

Категория:Геометрические графы