Коловий граф

У теорії графів коловий граф — це граф перетинів множини хорд кола. Тобто це неорієнтований граф, вершини якого можна ототожнити з хордами кола, і ці вершини суміжні тоді й тільки тоді, коли відповідні хорди перетинаються.

Коло з п'ятьма хордами і відповідний коловий граф

Алгоритмічна складність

Спінрад[1] представив алгоритм, який працює за час O(n2), який перевіряє, чи є заданий неорієнтований граф з n вершинами коловим, і якщо він коловий, будує множину хорд, які дають коловий граф.

Багато інших задач, які NP-повні на графах загального вигляду, мають алгоритми поліноміального часу, якщо обмежитися коловими графами. Наприклад, Клокс[2] показав, що деревну ширину колового графу можна визначити, а оптимальне дерево декомпозиції побудувати за час O(n3). Крім того, найменше заміщення (тобто хордальний граф з якомога меншим числом ребер, що містить даний коловий граф як підграф) можна знайти за час O(n3)[3]. Тіскін[4] показав, що найбільшу кліку колового графу можна знайти за час O(n log2 n), а Неш і Грегг[5] показали, що найбільшу незалежну множину незваженого колового графу можна знайти за час O(n min{d, α}), де d — параметр графу, відомий як щільність, а α — число незалежності колового графу.

Все ж є задачі, які залишаються NP-повними, навіть якщо обмежитися коловими графами. До цих задач належать пошуки домінівної множини, найменшої зв'язної домінівної множини і найменшої тотальної домінівної множини[6].

Хроматичне число
Хорди, що утворюють граф Агеєва, вільний від трикутників коловий граф з 220 вершинами і хроматичним числом 5[7], поданий у вигляді конфігурації прямих на гіперболічній площині

Хроматичне число колового графу дорівнює найменшому числу кольорів, які можна використати для розфарбовування хорд, так, щоб ніякі дві перетинні хорди не мали однакового кольору. Оскільки можна утворити коловий граф, у якому довільна велика множина хорд перетинають одна одну, хроматичне число колового графу може бути довільно великим, а визначення хроматичного числа колового графу є NP-повною задачею[8]. NP-повною задачею є й перевірка, чи можна розфарбувати коловий граф чотирма кольорами[9]. Унгер[10] стверджував, що пошук розфарбування трьома кольорами можна здійснити за поліноміальний час, але в описі його результатів відсутні багато подробиць[10].

Деякі автори досліджували задачу розфарбовування обмежених підкласів колових графів малим числом кольорів. Зокрема, колові графи, в яких немає множин з k і більше хорд, в яких всі хорди перетинають одна одну, можна розфарбувати, не перевищуючи кольорів[11]. Зокрема, при k = 3 (тобто для колових графів без трикутників) хроматичне число не перевищує п'яти, і ця межа точна — всі колові графи без трикутників можна розфарбувати в п'ять кольорів і існують колові графи без трикутників, що вимагають п'яти кольорів для розфарбовування[12]. Якщо коловий граф має обхват щонайменше п'ять (тобто в ньому немає трикутників і циклів з чотирма вершинами), його можна розфарбувати, обмежившись трьома кольорами[13]. Задача розфарбовування рамкових графів без трикутників еквівалентна задачі подання рамкових графів у вигляді графу, ізометричного прямому добутку дерев. У цій відповідності задач число кольорів у розфарбуванні відповідає числу дерев у добутку[14].

Застосування

Колові графи з'являються під час проєктування НВІС як абстракція окремого випадку трасування друкованих плат, відомого як «двополюсне трасування перетинів каналів». У цьому випадку ділянка трасування є прямокутником, усі мережі є двополюсниками, а виводи розташовуються по периметру прямокутника. Легко бачити, що граф перетинів цієї мережі є коловим графом[15]. Одна з цілей трасування — забезпечення відсутності електричного контакту між різними мережами та розташування можливих перетинних частин на різних шарах. Таким чином, колові графи охоплюють частину задач трасування.

Розфарбування колових графів можна використовувати також для пошуку книжкового вкладення довільних графів — якщо вершини заданого графу G розташовані на колі, а ребра графу G утворюють хорди кола, то граф перетинів цих хорд є коловим графом, а розфарбування цього колового графу еквівалентне книжковому вкладенню, що зберігає колове розташування. У цій еквівалентності число кольорів відповідає числу сторінок у книжковому вкладенні[9].

Пов'язані класи графів

Граф перетинів множини інтервалів на прямій називається інтервальним графом.

Граф є коловим тоді і тільки тоді, коли він є правильним інтервальним графом. Це графи, вершини яких відповідають (відкритим) відрізкам на прямий і дві вершини з'єднані ребром, якщо два інтервали мають непорожній перетин. При цьому ніякий інтервал не міститься повністю в іншому інтервалі.

Струнні графи, графи перетинів кривих на площині, включають колові графи як окремий випадок.

Будь-який дистанційно-успадковуваний граф є коловим графом, як і будь-який граф перестановки або індиферентний граф. Будь-який зовніпланарний граф також є коловим[16][9].

Примітки
  1. Spinrad, 1994.
  2. Kloks, 1996.
  3. Kloks, Kratsch, Wong, 1998.
  4. Tiskin, 2010.
  5. Nash, Gregg, 2010.
  6. Keil, 1993.
  7. Ageev, 1996.
  8. Garey, Johnson, Miller, Papadimitriou, 1980.
  9. Unger, 1988.
  10. Unger, 1992.
  11. Černý, 2007. Для более ранних границ см. Gyárfás, 1985, Косточка, 1988 и Kostochka, Kratochvíl, 1997.
  12. См. Косточка, 1988 для верхней границы и Ageev, 1996 графов, достигающих нижнюю границу. Карапетян (Карапетян, 1984) и (Gyárfás, Lehel, 1985) указали ранее более слабые границы для той же задачи.
  13. Ageev, 1999.
  14. Bandelt, Chepoi, Eppstein, 2010.
  15. Sherwani, 2000.
  16. Wessel, Pöschel, 1985.

Література
  • A. A. Ageev. A triangle-free circle graph with chromatic number 5 // Discrete Mathematics. — 1996. — Т. 152, вип. 1-3 (1 березня). — С. 295–298. — DOI:10.1016/0012-365X(95)00349-2.
  • A. A. Ageev. Every circle graph of girth at least 5 is 3-colourable // Discrete Mathematics. — 1999. — Т. 195, вип. 1-3 (1 березня). — С. 229–233. — DOI:10.1016/S0012-365X(98)00192-7.
  • H.-J. Bandelt, V. Chepoi, D. Eppstein. Combinatorics and geometry of finite and infinite squaregraphs // SIAM Journal on Discrete Mathematics. — 2010. — Т. 24, вип. 4 (1 березня). — С. 1399–1440. — arXiv:0905.4537. — DOI:10.1137/090760301.
  • Jakub Černý. Coloring circle graphs // Electronic Notes in Discrete Mathematics. — 2007. — Т. 29 (1 березня). — С. 357–361. — DOI:10.1016/j.endm.2007.07.072.
  • M. R. Garey, D. S. Johnson, G. L. Miller, C. Papadimitriou. The complexity of coloring circular arcs and chords // SIAM. J. on Algebraic and Discrete Methods. — 1980. — Т. 1, вип. 2 (1 березня). — С. 216–227. — DOI:10.1137/0601025.
  • A. Gyárfás. On the chromatic number of multiple interval graphs and overlap graphs // Discrete Mathematics. — 1985. — Т. 55, вип. 2 (1 березня). — С. 161–166. — DOI:10.1016/0012-365X(85)90044-5.. Як процитовано в Агеєва (Ageev, 1996)
  • A. Gyárfás, J. Lehel. Covering and coloring problems for relatives of intervals // Discrete Mathematics. — 1985. — Т. 55, вип. 2 (1 березня). — С. 167–180. — DOI:10.1016/0012-365X(85)90045-7.. Як процитовано в Агеєва (Ageev, 1996)
  • И. А. Карапетян. О совершенных дуговых и хордовых графах. — Новосибирск : Институт математики, 1984. — (Автореферат диссертации канд. Физ-матю наук: 01.01.09)
  • J. Mark Keil. The complexity of domination problems in circle graphs // Discrete Applied Mathematics. — 1993. — Т. 42, вип. 1 (1 березня). — С. 51–63. — DOI:10.1016/0166-218X(93)90178-Q.
  • Ton Kloks. Treewidth of Circle Graphs // Int. J. Found. Comput. Sci.. — 1996. — Т. 7, вип. 2 (1 березня). — С. 111–120. — DOI:10.1142/S0129054196000099.
  • T. Kloks, D. Kratsch, C. K. Wong. Minimum fill-in on circle and circular-arc graphs // Journal of Algorithms. — 1998. — Т. 28, вип. 2 (1 березня). — С. 272–289. — DOI:10.1006/jagm.1998.0936.
  • А. В. Косточка. Модели и методы оптимизации / В. Т. Дементьев. — 1988. — Т. 10. — С. 204–226. — (Труды Института математики) — ISBN 5-02-028584-6, ББК В1я54 + В18я54.
  • A.V. Kostochka, J. Kratochvíl. Covering and coloring polygon-circle graphs // Discrete Mathematics. — 1997. — Т. 163, вип. 1–3 (1 березня). — С. 299–305. — DOI:10.1016/S0012-365X(96)00344-5.
  • Nicholas Nash, David Gregg. An output sensitive algorithm for computing a maximum independent set of a circle graph // Information Processing Letters. — 2010. — Т. 116, вип. 16 (1 березня). — С. 630–634. — DOI:10.1016/j.ipl.2010.05.016.
  • Jeremy Spinrad. Recognition of circle graphs // Journal of Algorithms. — 1994. — Т. 16, вип. 2 (1 березня). — С. 264–282. — DOI:10.1006/jagm.1994.1012.
  • Alexander Tiskin. Proceedings of ACM-SIAM SODA 2010. — 2010. — С. 1287–1296.
  • Walter Unger. STACS 88: 5th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 11–13, 1988, Proceedings. — Berlin : Springer, 1988. — Т. 294. — С. 61–72. — (Lecture Notes in Computer Science) — DOI:10.1007/BFb0035832.
  • Walter Unger. STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings. — Berlin : Springer, 1992. — Т. 577. — С. 389–400. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-55210-3_199.
  • W. Wessel, R. Pöschel. Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984. — B.G. Teubner, 1985. — Т. 73. — С. 207–210. — (Teubner-Texte zur Mathematik). Як процитовано в Unger, 1988.
  • Naveed Sherwani. Algorithms for VLSI Physical Design Automation. — Boston/Dordrecht/London : Kluwer Academic Publishers, 2000. — ISBN 0-7923-8393-1.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.