Вікіпедія

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

граф перетинів кривих на площині

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

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

Передумови ред.

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

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

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

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

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

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

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

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

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

Примітки ред.

  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 // Combinatorics, Probability and Computing. — 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 // Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001). — 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.
Отримано з https://uk.wikipedia.org/w/index.php?title=Струнний_граф&oldid=35759153