Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

У теорії графів коловий граф це граф перетинів множини хорд кола Тобто це неорієнтований граф вершини якого можна ототож

Коловий граф

Коловий граф

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

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

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

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

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

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

Хроматичне число

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

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

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

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

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

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

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

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

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

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

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

Примітки

  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 // . — 1996. — Т. 152, вип. 1-3 (6 липня). — С. 295–298. — DOI:10.1016/0012-365X(95)00349-2.
  • A. A. Ageev. Every circle graph of girth at least 5 is 3-colourable // . — 1999. — Т. 195, вип. 1-3 (6 липня). — С. 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 (6 липня). — С. 1399–1440. — arXiv:0905.4537. — DOI:10.1137/090760301.
  • Jakub Černý. Coloring circle graphs // Electronic Notes in Discrete Mathematics. — 2007. — Т. 29 (6 липня). — С. 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 (6 липня). — С. 216–227. — DOI:10.1137/0601025.
  • A. Gyárfás. On the chromatic number of multiple interval graphs and overlap graphs // . — 1985. — Т. 55, вип. 2 (6 липня). — С. 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 // . — 1985. — Т. 55, вип. 2 (6 липня). — С. 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 (6 липня). — С. 51–63. — DOI:10.1016/0166-218X(93)90178-Q.
  • Ton Kloks. Treewidth of Circle Graphs // Int. J. Found. Comput. Sci.. — 1996. — Т. 7, вип. 2 (6 липня). — С. 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 (6 липня). — С. 272–289. — DOI:10.1006/jagm.1998.0936.
  • А. В. Косточка. Модели и методы оптимизации / В. Т. Дементьев. — 1988. — Т. 10. — С. 204–226. — (Труды Института математики) — , ББК В1я54 + В18я54.
  • A.V. Kostochka, J. Kratochvíl. Covering and coloring polygon-circle graphs // . — 1997. — Т. 163, вип. 1–3 (6 липня). — С. 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 // . — 2010. — Т. 116, вип. 16 (6 липня). — С. 630–634. — DOI:10.1016/j.ipl.2010.05.016.
  • Jeremy Spinrad. Recognition of circle graphs // Journal of Algorithms. — 1994. — Т. 16, вип. 2 (6 липня). — С. 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. — .

Посилання

  • . Архів оригіналу за 29 червня 2021. Процитовано 25 червня 2021.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

U teoriyi grafiv kolovij graf ce graf peretiniv mnozhini hord kola Tobto ce neoriyentovanij graf vershini yakogo mozhna ototozhniti z hordami kola i ci vershini sumizhni todi j tilki todi koli vidpovidni hordi peretinayutsya Kolo z p yatma hordami i vidpovidnij kolovij grafAlgoritmichna skladnistSpinrad predstaviv algoritm yakij pracyuye za chas O n2 yakij pereviryaye chi ye zadanij neoriyentovanij graf z n vershinami kolovim i yaksho vin kolovij buduye mnozhinu hord yaki dayut kolovij graf Bagato inshih zadach yaki NP povni na grafah zagalnogo viglyadu mayut algoritmi polinomialnogo chasu yaksho obmezhitisya kolovimi grafami Napriklad Kloks pokazav sho derevnu shirinu kolovogo grafa mozhna viznachiti a optimalne derevo dekompoziciyi pobuduvati za chas O n3 Krim togo najmenshe zamishennya tobto hordalnij graf z yakomoga menshim chislom reber sho mistit danij kolovij graf yak pidgraf mozhna znajti za chas O n3 Tiskin pokazav sho najbilshu kliku kolovogo grafa mozhna znajti za chas O n log2n a Nesh i Gregg pokazali sho najbilshu nezalezhnu mnozhinu nezvazhenogo kolovogo grafa mozhna znajti za chas O n min d a de d parametr grafa vidomij yak shilnist a a chislo nezalezhnosti kolovogo grafa Vse zh ye zadachi yaki zalishayutsya NP povnimi navit yaksho obmezhitisya kolovimi grafami Do cih zadach nalezhat poshuki dominivnoyi mnozhini najmenshoyi zv yaznoyi dominivnoyi mnozhini i najmenshoyi totalnoyi dominivnoyi mnozhini Hromatichne chisloHordi sho utvoryuyut graf Ageyeva vilnij vid trikutnikiv kolovij graf z 220 vershinami i hromatichnim chislom 5 podanij u viglyadi konfiguraciyi pryamih na giperbolichnij ploshini Hromatichne chislo kolovogo grafa dorivnyuye najmenshomu chislu koloriv yaki mozhna vikoristati dlya rozfarbovuvannya hord tak shob niyaki dvi peretinni hordi ne mali odnakovogo koloru Oskilki mozhna utvoriti kolovij graf u yakomu dovilna velika mnozhina hord peretinayut odna odnu hromatichne chislo kolovogo grafa mozhe buti dovilno velikim a viznachennya hromatichnogo chisla kolovogo grafa ye NP povnoyu zadacheyu NP povnoyu zadacheyu ye j perevirka chi mozhna rozfarbuvati kolovij graf chotirma kolorami Unger stverdzhuvav sho poshuk rozfarbuvannya troma kolorami mozhna zdijsniti za polinomialnij chas ale v opisi jogo rezultativ vidsutni bagato podrobic Deyaki avtori doslidzhuvali zadachu rozfarbovuvannya obmezhenih pidklasiv kolovih grafiv malim chislom koloriv Zokrema kolovi grafi v yakih nemaye mnozhin z k i bilshe hord v yakih vsi hordi peretinayut odna odnu mozhna rozfarbuvati ne perevishuyuchi 21 2k 24k 24 displaystyle 21 cdot 2 k 24k 24 koloriv Zokrema pri k 3 tobto dlya kolovih grafiv bez trikutnikiv hromatichne chislo ne perevishuye p yati i cya mezha tochna vsi kolovi grafi bez trikutnikiv mozhna rozfarbuvati v p yat koloriv i isnuyut kolovi grafi bez trikutnikiv sho vimagayut p yati koloriv dlya rozfarbovuvannya Yaksho kolovij graf maye obhvat shonajmenshe p yat tobto v nomu nemaye trikutnikiv i cikliv z chotirma vershinami jogo mozhna rozfarbuvati obmezhivshis troma kolorami Zadacha rozfarbovuvannya ramkovih grafiv bez trikutnikiv ekvivalentna zadachi podannya ramkovih grafiv u viglyadi grafa izometrichnogo pryamomu dobutku derev U cij vidpovidnosti zadach chislo koloriv u rozfarbuvanni vidpovidaye chislu derev u dobutku ZastosuvannyaKolovi grafi z yavlyayutsya pid chas proyektuvannya NVIS yak abstrakciya okremogo vipadku trasuvannya drukovanih plat vidomogo yak dvopolyusne trasuvannya peretiniv kanaliv U comu vipadku dilyanka trasuvannya ye pryamokutnikom usi merezhi ye dvopolyusnikami a vivodi roztashovuyutsya po perimetru pryamokutnika Legko bachiti sho graf peretiniv ciyeyi merezhi ye kolovim grafom Odna z cilej trasuvannya zabezpechennya vidsutnosti elektrichnogo kontaktu mizh riznimi merezhami ta roztashuvannya mozhlivih peretinnih chastin na riznih sharah Takim chinom kolovi grafi ohoplyuyut chastinu zadach trasuvannya Rozfarbuvannya kolovih grafiv mozhna vikoristovuvati takozh dlya poshuku knizhkovogo vkladennya dovilnih grafiv yaksho vershini zadanogo grafa G roztashovani na koli a rebra grafa G utvoryuyut hordi kola to graf peretiniv cih hord ye kolovim grafom a rozfarbuvannya cogo kolovogo grafa ekvivalentne knizhkovomu vkladennyu sho zberigaye kolove roztashuvannya U cij ekvivalentnosti chislo koloriv vidpovidaye chislu storinok u knizhkovomu vkladenni Pov yazani klasi grafivGraf peretiniv mnozhini intervaliv na pryamij nazivayetsya intervalnim grafom Graf ye kolovim todi i tilki todi koli vin ye pravilnim intervalnim grafom Ce grafi vershini yakih vidpovidayut vidkritim vidrizkam na pryamij i dvi vershini z yednani rebrom yaksho dva intervali mayut neporozhnij peretin Pri comu niyakij interval ne mistitsya povnistyu v inshomu intervali Strunni grafi grafi peretiniv krivih na ploshini vklyuchayut kolovi grafi yak okremij vipadok Bud yakij distancijno uspadkovuvanij graf ye kolovim grafom yak i bud yakij graf perestanovki abo indiferentnij graf Bud yakij zovniplanarnij graf takozh ye kolovim PrimitkiSpinrad 1994 Kloks 1996 Kloks Kratsch Wong 1998 Tiskin 2010 Nash Gregg 2010 Keil 1993 Ageev 1996 Garey Johnson Miller Papadimitriou 1980 Unger 1988 Unger 1992 Cerny 2007 Dlya bolee rannih granic sm Gyarfas 1985 Kostochka 1988 i Kostochka Kratochvil 1997 Sm Kostochka 1988 dlya verhnej granicy i Ageev 1996 grafov dostigayushih nizhnyuyu granicu Karapetyan Karapetyan 1984 i Gyarfas Lehel 1985 ukazali ranee bolee slabye granicy dlya toj zhe zadachi Ageev 1999 Bandelt Chepoi Eppstein 2010 Sherwani 2000 Wessel Poschel 1985 LiteraturaA A Ageev A triangle free circle graph with chromatic number 5 1996 T 152 vip 1 3 6 lipnya S 295 298 DOI 10 1016 0012 365X 95 00349 2 A A Ageev Every circle graph of girth at least 5 is 3 colourable 1999 T 195 vip 1 3 6 lipnya S 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 T 24 vip 4 6 lipnya S 1399 1440 arXiv 0905 4537 DOI 10 1137 090760301 Jakub Cerny Coloring circle graphs Electronic Notes in Discrete Mathematics 2007 T 29 6 lipnya S 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 T 1 vip 2 6 lipnya S 216 227 DOI 10 1137 0601025 A Gyarfas On the chromatic number of multiple interval graphs and overlap graphs 1985 T 55 vip 2 6 lipnya S 161 166 DOI 10 1016 0012 365X 85 90044 5 Yak procitovano v Ageyeva Ageev 1996 A Gyarfas J Lehel Covering and coloring problems for relatives of intervals 1985 T 55 vip 2 6 lipnya S 167 180 DOI 10 1016 0012 365X 85 90045 7 Yak procitovano v Ageyeva Ageev 1996 I A Karapetyan O sovershennyh dugovyh i hordovyh grafah Novosibirsk Institut matematiki 1984 Avtoreferat dissertacii kand Fiz matyu nauk 01 01 09 J Mark Keil The complexity of domination problems in circle graphs Discrete Applied Mathematics 1993 T 42 vip 1 6 lipnya S 51 63 DOI 10 1016 0166 218X 93 90178 Q Ton Kloks Treewidth of Circle Graphs Int J Found Comput Sci 1996 T 7 vip 2 6 lipnya S 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 T 28 vip 2 6 lipnya S 272 289 DOI 10 1006 jagm 1998 0936 A V Kostochka Modeli i metody optimizacii V T Dementev 1988 T 10 S 204 226 Trudy Instituta matematiki ISBN 5 02 028584 6 BBK V1ya54 V18ya54 A V Kostochka J Kratochvil Covering and coloring polygon circle graphs 1997 T 163 vip 1 3 6 lipnya S 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 2010 T 116 vip 16 6 lipnya S 630 634 DOI 10 1016 j ipl 2010 05 016 Jeremy Spinrad Recognition of circle graphs Journal of Algorithms 1994 T 16 vip 2 6 lipnya S 264 282 DOI 10 1006 jagm 1994 1012 Alexander Tiskin Proceedings of ACM SIAM SODA 2010 2010 S 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 T 294 S 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 T 577 S 389 400 Lecture Notes in Computer Science DOI 10 1007 3 540 55210 3 199 W Wessel R Poschel Graphs Hypergraphs and Applications Proceedings of the Conference on Graph Theory Held in Eyba October 1st to 5th 1984 B G Teubner 1985 T 73 S 207 210 Teubner Texte zur Mathematik Yak procitovano v Unger 1988 Naveed Sherwani Algorithms for VLSI Physical Design Automation Boston Dordrecht London Kluwer Academic Publishers 2000 ISBN 0 7923 8393 1 Posilannya Arhiv originalu za 29 chervnya 2021 Procitovano 25 chervnya 2021

Дата публікації:
Топ