WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

Приложения

Циркулярные графы дуг полезны при моделировании задач периодического распределения ресурсов^[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.
• 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..

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.