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

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

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

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

$I_1,I_2,\dots <!--\; \dots \; -->,I_n\subset <!--\; \subset \; -->C_1$$I_{1},I_{2},\ldots ,I_{n}\subset C_{1}$

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

$V=\{I_1,I_2,\dots <!--\; \dots \; -->,I_n\}$$V=\{I_{1},I_{2},\ldots ,I_{n}\}$

и

$\{I_{\mathrm{\alpha <!--\; \alpha \; -->}},I_{\mathrm{\beta <!--\; \beta \; -->}}\}\in <!--\; \in \; -->E⟺<!--\; ⟺\; -->I_{\mathrm{\alpha <!--\; \alpha \; -->}}\cap <!--\; \cap \; -->I_{\mathrm{\beta <!--\; \beta \; -->}}\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}.$$\{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .$

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

РаспознаваниеПравить

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

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

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

Некоторые подклассыПравить

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

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

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

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

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

Циркулярные графы дуг ХеллиПравить

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

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

ПриложенияПравить

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

СсылкиПравить

• 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. — С. 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. — С. 1–24. — doi:10.1137/0209001..
• Ross McConnell. Linear-time recognition of circular-arc graphs // Algorithmica. — 2003. — Т. 37, вып. 2. — С. 93–147. — doi:10.1007/s00453-003-1032-7.
• Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-444-51530-5. 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. — С. 390–403. — doi:10.1137/S0097539792269095..
• Fanica Gavril. Algorithms on circular-arc graphs // Networks. — 1974. — Т. 4, вып. 4. — С. 357–369. — doi:10.1002/net.3230040407.
• circular arc graph  (неопр.). Information System on Graph Class Inclusions. Дата обращения: 14 декабря 2013. Архивировано 21 декабря 2013 года.
• Maria Chudnovsky, Paul Seymour. Claw-free graphs. III. Circular interval graphs // Journal of Combinatorial Theory. — 2008. — Т. 98, вып. 4. — С. 812–834. — doi:10.1016/j.jctb.2008.03.001..