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

Стру нний граф це граф перетинів кривих на площині кожна крива при цьому називається струною Якщо дано граф G він є стру

Струнний граф

Струнний граф

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

image
Подання планарного графа у вигляді струнного графа

Передумови

Бензер (Benzer, 1959) описував концепцію, близьку до струнних графів, але для загальніших структур. У цьому контексті він також сформулював спеціальний випадок перетину інтервалів на прямій, що став класичним класом інтервальних графів. Пізніше Сінден (Sinden, 1966) висловив ту ж ідею для електричних мереж і друкованих схем. Математичне вивчення струнних графів почалося зі статті , [en] і Тарджана (Ehrlich, Even, Tarjan, 1976) і, за сприяння Сіндена і Рональда Грема 1976 року опис струнних графів поставлено як відкриту проблему на 5-му угорському колоквіумі з комбінаторики. Зрештою, було доведено, що розпізнавання струнних графів є NP-повною задачею, звідки випливає, що навряд чи існує простий опис цього класу.

image
(Розбиття) графа K5, що не є струнним графом.

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

Будь-який планарний граф є струнним — для будь-якого вкладеного в площину графа можна утворити подання у вигляді струнного графа, намалювавши для кожної вершини криву, яка обходить по колу вершину і середину кожного суміжного ребра, як показано на малюнку. Для будь-якого ребра uv графа, струни для u і v перетинаються двічі поблизу середини ребра uv, і не існує інших перетинів, так що перетини пари струн представляють суміжну пару вершин початкового планарного графа. Як варіант, за , будь-який планарний граф можна подати у вигляді набору кіл, будь-які два з яких перетинаються тоді й лише тоді, коли відповідні вершини суміжні. Ці кола (з початковою і кінцевою точкою, вибраними для перетворення кола у відкриту криву) є поданням заданого планарного графа у вигляді струнного графа. Чалопін, Гонсалвіс і Ошан (Chalopin, Gonçalves, Ochem, 2007) довели, що будь-який планарний граф має подання у вигляді струнного графа, в якому кожна пара струн має максимум один перетин, а не так, як описано вище. Гіпотеза Шейнермана, нині доведена, є навіть строгішим твердженням, що будь-який планарний граф можна подати як граф перетинів відрізків. Якщо всі ребра даного графа G (розбиваються), отриманий граф є струнним графом тоді й лише тоді, коли граф G планарний. Зокрема, розбиття повного графа K5, показане на малюнку, струнним графом не є, оскільки K5 не планарний.

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

Доповнення графа будь-якого графа порівнянності також є струнним графом.

Інші результати

Ерліх, Івен і Тарджан (Ehrlich, Even, Tarjan, 1976) показали, що обчислення хроматичного числа струнного графа є NP-складною задачею. [en] (Kratochvil, 1991a) виявив, що струнні графи утворюють замкнутий клас породжених мінорів, але не мінорно замкнутий клас графів.

Будь-який струнний граф з m ребрами можна розбити на дві підмножини, при цьому кожна підмножина становитиме фіксовану частку від розміру всього графа, видаливши O(m3/4log1/2m) ребер. Звідси випливає, що струнні графи без клік, струнні графи, що не містять підграфів Kt,t для жодного сталого t, мають O(n) ребер і мають поліноміальне розширення.

Примітки

  1. Graham, 1976.
  2. Кратохвіл (Kratochvil, 1991b) показав, що розпізнавання струнного графа є NP-складною задачею, але не зміг показати, що її можна розв'язати в класі NP. Після проміжних результатів Шефера та Стефанковича (Schaefer, Štefankovič, 2001), Паха і Тота (Pach, Tóth, 2002), Шефера, Седжвіка і Стефанковича (Schaefer, Sedgwick, Štefankovič, 2003) завершено доведення, що задача NP-повна.
  3. Шефер і Стефанкович (Schaefer, Štefankovič, 2001) приписують це спостереження Сіндену (Sinden, 1966).
  4. Golumbic, Rotem, Urrutia, 1983; Lovász, 1983. Див. також статтю Фокса і Паха (Fox, Pach, 2009).
  5. Fox, Pach, 2009.
  6. Dvořák, Norin, 2015.

Література

  • S. Benzer. On the topology of the genetic fine structure // Proceedings of the National Academy of Sciences of the United States of America. — 1959. — Т. 45, вип. 11. — С. 1607–1620. — Bibcode:1959PNAS...45.1607B. — DOI:10.1073/pnas.45.11.1607.
  • J. Chalopin, D. Gonçalves, P. Ochem. Planar graphs are in 1-STRING // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — ACM and SIAM, 2007. — С. 609–617.
  • Zdeněk Dvořák, Sergey Norin. Strongly sublinear separators and polynomial expansion. — 2015. — arXiv:1504.04821.
  • G. Ehrlich, S. Even, R. E. Tarjan. Intersection graphs of curves in the plane // Journal of Combinatorial Theory. — 1976. — Т. 21, вип. 1. — С. 8–20. — DOI:10.1016/0095-8956(76)90022-8.
  • Jacob Fox, János Pach. A separator theorem for string graphs and its applications // . — 2009. — Т. 19, вип. 3. — С. 371. — DOI:10.1017/s0963548309990459.
  • M. Golumbic, D. Rotem, J. Urrutia. Comparability graphs and intersection graphs // Discrete Mathematics. — 1983. — Т. 43, вип. 1. — С. 37–46. — DOI:10.1016/0012-365X(83)90019-5.
  • R. L. Graham. Problem 1 // Open Problems at 5th Hungarian Colloquium on Combinatorics. — 1976.
  • Jan Kratochvil. String Graphs. I. The number of critical nonstring graphs is infinite // Journal of Combinatorial Theory, Series B. — 1991a. — Т. 52, вип. 1. — С. 53–66. — DOI:10.1016/0095-8956(91)90090-7.
  • Jan Kratochvil. String Graphs. II. Recognizing string graphs is NP-Hard // Journal of Combinatorial Theory, Series B. — 1991b. — Т. 52, вип. 1. — С. 67–78. — DOI:10.1016/0095-8956(91)90091-W.
  • L. Lovász. Perfect graphs // Selected Topics in Graph Theory. — London : Academic Press, 1983. — Т. 2. — С. 55–87.
  • János Pach, Geza Tóth. Recognizing string graphs is decidable // Discrete and Computational Geometry. — 2002. — Т. 28, вип. 4. — С. 593–606. — DOI:10.1007/s00454-002-2891-4.
  • Marcus Schaefer, Daniel Štefankovič. Decidability of string graphs // . — 2001. — С. 241–246.
  • Marcus Schaefer, Eric Sedgwick, Daniel Štefankovič. Recognizing string graphs in NP // Journal of Computer and System Sciences. — 2003. — Т. 67, вип. 2. — С. 365–380. — DOI:10.1016/S0022-0000(03)00045-X.
  • F. W. Sinden. Topology of thin film RC-circuits // Bell System Technical Journal. — 1966. — Т. 45. — С. 1639–1662. — DOI:10.1002/j.1538-7305.1966.tb01713.x.

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

Stru nnij graf ce graf peretiniv krivih na ploshini kozhna kriva pri comu nazivayetsya strunoyu Yaksho dano graf G vin ye strunnim todi j lishe todi koli isnuye nabir krivih strun namalovanih na ploshini takih sho niyaki tri struni ne peretinayutsya v odnij tochci i graf G izomorfnij grafu vershini yakogo vidpovidayut krivim a duga v nomu vidpovidaye peretinu dvoh krivih Podannya planarnogo grafa u viglyadi strunnogo grafaPeredumoviBenzer Benzer 1959 opisuvav koncepciyu blizku do strunnih grafiv ale dlya zagalnishih struktur U comu konteksti vin takozh sformulyuvav specialnij vipadok peretinu intervaliv na pryamij sho stav klasichnim klasom intervalnih grafiv Piznishe Sinden Sinden 1966 visloviv tu zh ideyu dlya elektrichnih merezh i drukovanih shem Matematichne vivchennya strunnih grafiv pochalosya zi statti en i Tardzhana Ehrlich Even Tarjan 1976 i za spriyannya Sindena i Ronalda Grema 1976 roku opis strunnih grafiv postavleno yak vidkritu problemu na 5 mu ugorskomu kolokviumi z kombinatoriki Zreshtoyu bulo dovedeno sho rozpiznavannya strunnih grafiv ye NP povnoyu zadacheyu zvidki viplivaye sho navryad chi isnuye prostij opis cogo klasu Rozbittya grafa K5 sho ne ye strunnim grafom Pov yazani klasi grafivBud yakij planarnij graf ye strunnim dlya bud yakogo vkladenogo v ploshinu grafa mozhna utvoriti podannya u viglyadi strunnogo grafa namalyuvavshi dlya kozhnoyi vershini krivu yaka obhodit po kolu vershinu i seredinu kozhnogo sumizhnogo rebra yak pokazano na malyunku Dlya bud yakogo rebra uv grafa struni dlya u i v peretinayutsya dvichi poblizu seredini rebra uv i ne isnuye inshih peretiniv tak sho peretini pari strun predstavlyayut sumizhnu paru vershin pochatkovogo planarnogo grafa Yak variant za bud yakij planarnij graf mozhna podati u viglyadi naboru kil bud yaki dva z yakih peretinayutsya todi j lishe todi koli vidpovidni vershini sumizhni Ci kola z pochatkovoyu i kincevoyu tochkoyu vibranimi dlya peretvorennya kola u vidkritu krivu ye podannyam zadanogo planarnogo grafa u viglyadi strunnogo grafa Chalopin Gonsalvis i Oshan Chalopin Goncalves Ochem 2007 doveli sho bud yakij planarnij graf maye podannya u viglyadi strunnogo grafa v yakomu kozhna para strun maye maksimum odin peretin a ne tak yak opisano vishe Gipoteza Shejnermana nini dovedena ye navit strogishim tverdzhennyam sho bud yakij planarnij graf mozhna podati yak graf peretiniv vidrizkiv Yaksho vsi rebra danogo grafa G rozbivayutsya otrimanij graf ye strunnim grafom todi j lishe todi koli graf G planarnij Zokrema rozbittya povnogo grafa K5 pokazane na malyunku strunnim grafom ne ye oskilki K5 ne planarnij Bud yakij kolovij graf yak graf peretiniv vidrizkiv hord kola ye takozh strunnim grafom Bud yakij hordalnij graf mozhna podati yak strunnij graf hordalni grafi ye grafami peretiniv pidderev derev i mozhna utvoriti strunne podannya hordalnogo grafa planarnim vkladannyam vidpovidnogo dereva i zaminoyu kozhnogo piddereva strunoyu sho prohodit navkolo reber piddereva Dopovnennya grafa bud yakogo grafa porivnyannosti takozh ye strunnim grafom Inshi rezultatiErlih Iven i Tardzhan Ehrlich Even Tarjan 1976 pokazali sho obchislennya hromatichnogo chisla strunnogo grafa ye NP skladnoyu zadacheyu en Kratochvil 1991a viyaviv sho strunni grafi utvoryuyut zamknutij klas porodzhenih minoriv ale ne minorno zamknutij klas grafiv Bud yakij strunnij graf z m rebrami mozhna rozbiti na dvi pidmnozhini pri comu kozhna pidmnozhina stanovitime fiksovanu chastku vid rozmiru vsogo grafa vidalivshi O m3 4log1 2m reber Zvidsi viplivaye sho strunni grafi bez klik strunni grafi sho ne mistyat pidgrafiv Kt t dlya zhodnogo stalogo t mayut O n reber i mayut polinomialne rozshirennya PrimitkiGraham 1976 Kratohvil Kratochvil 1991b pokazav sho rozpiznavannya strunnogo grafa ye NP skladnoyu zadacheyu ale ne zmig pokazati sho yiyi mozhna rozv yazati v klasi NP Pislya promizhnih rezultativ Shefera ta Stefankovicha Schaefer Stefankovic 2001 Paha i Tota Pach Toth 2002 Shefera Sedzhvika i Stefankovicha Schaefer Sedgwick Stefankovic 2003 zaversheno dovedennya sho zadacha NP povna Shefer i Stefankovich Schaefer Stefankovic 2001 pripisuyut ce sposterezhennya Sindenu Sinden 1966 Golumbic Rotem Urrutia 1983 Lovasz 1983 Div takozh stattyu Foksa i Paha Fox Pach 2009 Fox Pach 2009 Dvorak Norin 2015 LiteraturaS Benzer On the topology of the genetic fine structure Proceedings of the National Academy of Sciences of the United States of America 1959 T 45 vip 11 S 1607 1620 Bibcode 1959PNAS 45 1607B DOI 10 1073 pnas 45 11 1607 J Chalopin D Goncalves P Ochem Planar graphs are in 1 STRING Proceedings of the Eighteenth Annual ACM SIAM Symposium on Discrete Algorithms ACM and SIAM 2007 S 609 617 Zdenek Dvorak Sergey Norin Strongly sublinear separators and polynomial expansion 2015 arXiv 1504 04821 G Ehrlich S Even R E Tarjan Intersection graphs of curves in the plane Journal of Combinatorial Theory 1976 T 21 vip 1 S 8 20 DOI 10 1016 0095 8956 76 90022 8 Jacob Fox Janos Pach A separator theorem for string graphs and its applications 2009 T 19 vip 3 S 371 DOI 10 1017 s0963548309990459 M Golumbic D Rotem J Urrutia Comparability graphs and intersection graphs Discrete Mathematics 1983 T 43 vip 1 S 37 46 DOI 10 1016 0012 365X 83 90019 5 R L Graham Problem 1 Open Problems at 5th Hungarian Colloquium on Combinatorics 1976 Jan Kratochvil String Graphs I The number of critical nonstring graphs is infinite Journal of Combinatorial Theory Series B 1991a T 52 vip 1 S 53 66 DOI 10 1016 0095 8956 91 90090 7 Jan Kratochvil String Graphs II Recognizing string graphs is NP Hard Journal of Combinatorial Theory Series B 1991b T 52 vip 1 S 67 78 DOI 10 1016 0095 8956 91 90091 W L Lovasz Perfect graphs Selected Topics in Graph Theory London Academic Press 1983 T 2 S 55 87 Janos Pach Geza Toth Recognizing string graphs is decidable Discrete and Computational Geometry 2002 T 28 vip 4 S 593 606 DOI 10 1007 s00454 002 2891 4 Marcus Schaefer Daniel Stefankovic Decidability of string graphs 2001 S 241 246 Marcus Schaefer Eric Sedgwick Daniel Stefankovic Recognizing string graphs in NP Journal of Computer and System Sciences 2003 T 67 vip 2 S 365 380 DOI 10 1016 S0022 0000 03 00045 X F W Sinden Topology of thin film RC circuits Bell System Technical Journal 1966 T 45 S 1639 1662 DOI 10 1002 j 1538 7305 1966 tb01713 x

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