stringtranslate.com

Граф, представимый в виде слова

В математической области теории графов граф , представимый в виде слова , — это граф , который можно охарактеризовать словом (или последовательностью), элементы которого чередуются заданным образом. В частности, если множество вершин графа равно V , то можно выбрать слово w из алфавита V таким образом, чтобы буквы a и b чередовались в w тогда и только тогда, когда пара ab является ребром в графе. (Буквы a и b чередуются в w , если после удаления из w всех букв, кроме копий a и b , получается слово abab ... или слово baba ....) Например, граф-цикл, помеченный a , b , c и d по часовой стрелке, является представимым в виде слова, поскольку его можно представить как abdacdbc : пары ab , bc , cd и ad чередуются, но пары ac и bd — нет.

Слово w является словесным представлением G , и говорят, что w представляет G. Наименьшим (по числу вершин) непредставимым в виде слова графом является граф-колесо W 5 , который является единственным непредставимым в виде слова графом на 6 вершинах.

Определение графа, представимого словом, работает как в маркированных, так и в немаркированных случаях, поскольку любая маркировка графа эквивалентна любой другой маркировке. Кроме того, класс графов, представимых словом, является наследственным . Графы, представимые словом, обобщают несколько важных классов графов, таких как круговые графы , 3-раскрашиваемые графы и графы сравнимости . Различные обобщения теории графов, представимых словом, допускают представление любого графа.

История

Графы, представимые в виде слов, были введены Сергеем Китаевым [1] в 2004 году на основе совместного исследования со Стивеном Сейфом [2] полугруппы Перкинса , которая играет важную роль в теории полугрупп с 1960 года. [3] Первое систематическое исследование графов, представимых в виде слов, было предпринято в статье Китаева и Артема Пяткина 2008 года, [4] положившей начало развитию теории. Одним из ключевых авторов в этой области является Магнус М. Халлдорссон. [5] [6] [7] На сегодняшний день по этой теме написано более 35 статей, а основная часть книги [3] Сергея Китаева и Вадима Лозина посвящена теории графов, представимых в виде слов. Быстрый способ ознакомиться с этой областью — прочитать одну из обзорных статей. [8] [9] [10]

Мотивация к изучению графиков

Согласно [3], графы, представимые в виде слов, имеют отношение к различным областям, тем самым мотивируя изучать графы. Эти области — алгебра , теория графов , информатика , комбинаторика слов и планирование . Графы, представимые в виде слов, особенно важны в теории графов, поскольку они обобщают несколько важных классов графов, например, круговые графы , 3-раскрашиваемые графы и графы сравнимости .

Первые результаты

В [4] показано , что граф G является представимым в виде слова, если он является представимым в виде слова для некоторого k , то есть G может быть представлен словом, имеющим k копий каждой буквы. Более того, если граф является представимым в виде слова , то он также является ( k  + 1)-представимым. Таким образом, понятие числа представления графа , как минимального k, такого что граф является представимым в виде слова, является корректно определенным. Непредставимые в виде слова графы имеют число представления ∞. Графы с числом представления 1 являются в точности множеством полных графов , в то время как графы с числом представления 2 являются в точности классом круговых неполных графов. В частности, леса (за исключением отдельных деревьев с не более чем 2 вершинами), лестничные графы и циклические графы имеют число представления 2. Никакой классификации для графов с числом представления 3 не известно. Однако есть примеры таких графов, например, граф Петерсена и призмы. Более того, 3- подразделение любого графа является 3-представимым. В частности, для каждого графа G существует 3-представимый граф H , который содержит G в качестве минора . [4]

Граф G является перестановочно представимым , если он может быть представлен словом вида p 1 p 2 ... p k , где p i является перестановкой . Можно также сказать, что G является перестановочно k -представимым . Граф является перестановочно представимым тогда и только тогда, когда он является графом сравнимости . [2] Граф является представимым в виде слова влечет, что окрестность каждой вершины является перестановочно представимой (т.е. является графом сравнимости ). [2] Обратное к последнему утверждению утверждение неверно. [5] Однако тот факт, что окрестность каждой вершины является графом сравнимости , подразумевает, что задача о максимальной клике полиномиально разрешима на графах, представимых в виде слова . [6] [7]

Полутранзитивные ориентации

Полутранзитивные ориентации предоставляют мощный инструмент для изучения графов, представимых в виде слова. Ориентированный граф является полутранзитивно ориентированным тогда и только тогда, когда он ацикличен и для любого ориентированного пути u 1 → u 2 → ...→ u t , t ≥ 2, либо нет ребра из u 1 в u t , либо существуют все ребра u i → u j для 1 ≤ i < j ≤ t . Ключевая теорема в теории графов, представимых в виде слова, утверждает, что граф является представимым в виде слова тогда и только тогда, когда он допускает полутранзитивную ориентацию. [7] В качестве следствия из доказательства ключевой теоремы получаем верхнюю границу для графов, представимых в виде слова: каждый неполный граф, представимый в виде слова , является 2( n  −  κ ( G ))-представимым, где κ ( G ) — размер максимальной клики в G . [7] Как непосредственное следствие последнего утверждения, можно сказать, что проблема распознавания представимости в виде слова лежит в NP . В 2014 году Винсент Лимузи заметил, что распознавание того, является ли заданный граф представимым в виде слова, является NP-полной проблемой . [3] [8] Другое важное следствие ключевой теоремы заключается в том, что любой 3-раскрашиваемый граф представим в виде слова. Последний факт подразумевает, что многие классические графовые задачи являются NP-трудными для представимых в виде слова графов.  

Обзор выбранных результатов

Графы, не представимые в виде слов

Графы-колеса W 2 n +1 , для n ≥ 2, не являются представимыми в виде слова, а W 5 является минимальным (по числу вершин) не представимым в виде слова графом. Взяв любой несравнимый граф и добавив вершину (вершину, соединенную с любой другой вершиной), мы получим не представимый в виде слова граф, который затем может произвести бесконечно много не представимых в виде слова графов. [3] Любой граф, полученный таким образом, обязательно будет иметь треугольник (цикл длины 3) и вершину степени не менее 5. Существуют не представимые в виде слова графы максимальной степени 4 [11] и существуют не представимые в виде слова графы без треугольников. [6] Существуют также регулярные не представимые в виде слова графы. [3] Неизоморфные не представимые в виде слова связные графы с не более чем восемью вершинами были впервые перечислены Хеманом ZQ Ченом. Его вычисления были расширены в [12] , где было показано, что числа неизоморфных, непредставимых в виде слов связных графов с 5−11 вершинами равны соответственно 0, 1, 25, 929, 54957, 4880093, 650856040. Это последовательность A290814 в Онлайн-энциклопедии целочисленных последовательностей (OEIS).

Операции над графами и представимостью слов

Операции, сохраняющие представимость в виде слова, — это удаление вершины, замена вершины модулем, декартово произведение, корневое произведение, подразделение графа, соединение двух графов ребром и склеивание двух графов в вершине. [3] Операции, не обязательно сохраняющие представимость в виде слова, — это взятие дополнения, взятие линейного графа, сокращение ребра, [3] склеивание двух графов в клику размера 2 или более, [13] тензорное произведение, лексикографическое произведение и сильное произведение. [14] Удаление ребра, добавление ребра и поднятие ребра относительно представимости в виде слова (эквивалентно, полутранзитивная ориентируемость) изучаются в. [14]

Графики с высоким числом представлений

В то время как каждый неполный граф, представимый в виде слова , является 2( n  −  κ ( G ))-представимым, где κ ( G ) — размер максимальной клики в G , [7] наибольшее известное число представлений — это floor( n /2), заданное графами корон со всеми смежными вершинами. [7] Интересно, что такие графы — не единственные графы, которым требуются длинные представления. [15] Показано, что сами графы корон требуют длинных (возможно, самых длинных) представлений среди двудольных графов. [16]

Сложность вычислений

Известные вычислительные сложности для задач на графах, представимых в виде слов, можно обобщить следующим образом: [3] [8]

Представление планарных графов

Планарные графы без треугольников представимы в виде слова. [7] Почти триангуляция без K4 является 3-раскрашиваемой тогда и только тогда, когда она представима в виде слова; [17] этот результат обобщает исследования в [18] [19] Представимость в виде слова подразделений граней графов треугольной сетки изучается в [20] , а представимость в виде слова триангуляции графов цилиндров, покрытых сеткой, изучается в [21]

Представление разделенных графов

Представление в виде слов расщепленных графов изучается в [22] [13] В частности, в [22] предлагается характеристика в терминах запрещенных индуцированных подграфов представимых в виде слов расщепленных графов, в которых вершины в независимом множестве имеют степень не более 2 или размер клики равен 4, в то время как вычислительная характеристика представимых в виде слов расщепленных графов с кликой размера 5 дана в [13] Кроме того, необходимые и достаточные условия для того, чтобы ориентация расщепленного графа была полутранзитивной, даны в [22], в то время как в [13] показано, что пороговые графы представимы в виде слов, и расщепленные графы используются для демонстрации того, что склеивание двух представимых в виде слов графов в любой клике размера не менее 2 может привести или не привести к представимому в виде слов графу, что решило давнюю открытую проблему.

Графы, представленные шаблоном, избегающим слов

Граф является p -представимым, если он может быть представлен словом, избегающим шаблона p . Например, 132-представимые графы — это те, которые могут быть представлены словами w 1 w 2 ... w n , где нет 1 ≤ ​​a < b < c ≤ n таких, что w a < w c < w b . В [23] показано, что любой 132-представимый граф обязательно является круговым графом , а любое дерево и любой циклический граф , а также любой граф с не более чем 5 вершинами, являются 132-представимыми. В [24] было показано , что не все круговые графы являются 132-представимыми, и что 123-представимые графы также являются собственным подклассом класса круговых графов.

Обобщения

Ряд обобщений [25] [26] [27] понятия графа, представимого в виде слова, основаны на наблюдении Джеффа Реммеля , что не-ребра определяются вхождениями шаблона 11 (две последовательные равные буквы) в слово, представляющее граф, в то время как ребра определяются избеганием этого шаблона. Например, вместо шаблона 11 можно использовать шаблон 112 или шаблон 1212 или любой другой бинарный шаблон, где предположение о том, что алфавит упорядочен, может быть сделано таким образом, что буква в слове, соответствующая 1 в шаблоне, меньше, чем буква, соответствующая 2 в шаблоне. Позволяя u быть упорядоченным бинарным шаблоном, мы таким образом получаем понятие графа, представимого в виде слова . Таким образом, графы, представимые в виде слова, являются просто классом графов, представимых в виде слова. Интересно, что любой граф может быть u -представлен, предполагая, что u имеет длину не менее 3. [28]

Другой способ обобщения понятия графа, представимого в виде слова, снова предложенный Реммелем, заключается во введении «степени толерантности» k для вхождений шаблона p, определяющего ребра/не-ребра. То есть, мы можем сказать, что если имеется до k вхождений p , образованных буквами a и b , то между a и b есть ребро . Это дает понятие k - p -представимого графа, и k -11-представимые графы изучаются в [29] . Обратите внимание, что 0-11-представимые графы являются именно графами, представимыми в виде слова. Ключевые результаты в [29] заключаются в том, что любой граф является 2-11-представимым и что графы, представимые в виде слова, являются собственным подклассом 1-11-представимых графов. Является ли любой граф 1-11-представимым или нет, является сложной открытой проблемой.

Для еще одного типа соответствующего обобщения Ханс Зантема предложил понятие k -полутранзитивной ориентации , уточняющее понятие полутранзитивной ориентации. [15] Идея здесь заключается в том, чтобы ограничиться рассмотрением только направленных путей длины, не превышающей k , допуская при этом нарушения полутранзитивности на более длинных путях.

Открытые проблемы

Открытые проблемы, связанные с графами, представимыми в виде слов, можно найти в [3] [8] [9] [10] , и они включают в себя:

Литература

Список публикаций по изучению представления графов словами содержит, но не ограничивается

  1. Ö. Акгюн, ИП Гент, С. Китаев, Х. Зантема. Решение вычислительных задач в теории графов, представимых в виде слов. Журнал целочисленных последовательностей 22 (2019), статья 19.2.5.
  2. П. Акроботу, С. Китаев и З. Масарова. О представимости полимино-триангуляций в словах. Siberian Adv. Math. 25 (2015), 1−10.
  3. Б. Броэр. Представленные в слове графы, 2018. Магистерская диссертация в Университете Радбауд, Неймеген.
  4. Б. Броэр и Х. Зантема. «К-куб k-представим», J. Autom., Lang., and Combin. 24 (2019) 1, 3-12.
  5. JN Chen и S. Китаев. О 12-представимости индуцированных подграфов решетчатого графа, Discussiones Mathematicae Graph Theory, в печати
  6. TZQ Chen, S. Kitaev и A. Saito. Представление разделенных графов словами, arXiv:1909.09471
  7. TZQ Chen, S. Китаев и BY Sun. Словесное представление гранных подразделений треугольных решетчатых графов, Графы и комбинации. 32(5) (2016), 1749−1761.
  8. TZQ Chen, S. Kitaev и BY Sun. Представимость в виде слов триангуляции графов цилиндров, покрытых сеткой, Discr. Appl. Math. 213 (2016), 60−70.
  9. Чон Г.-С., Ким Дж., Ким М. и Китаев С. Представимость графов Теплица в виде слов, Discr. Appl. Math., в печати.
  10. G.-S. Cheon, J. Kim, M. Kim и A. Pyatkin. О k-11-представимых графах. J. Combin. 10 (2019) 3, 491−513.
  11. И. Чой, Дж. Ким и М. Ким. Об операциях, сохраняющих полутранзитивную ориентируемость графов, Журнал комбинаторной оптимизации 37 (2019) 4, 1351−1366.
  12. А. Коллинз, С. Китаев и В. Лозин. Новые результаты о графах, представимых в виде слов, Discr. Appl. Math. 216 (2017), 136−141.
  13. А. Дайгаване, М. Сингх, Б. К. Джордж. 2-однородные слова: циклические графы и алгоритм проверки конкретных словесных представлений графов. arXiv:1806.04673 (2018).
  14. M. Gaetz и C. Ji. Перечисление и расширения графов, представимых в виде слов. Lecture Notes in Computer Science 11682 (2019) 180−192. В R. Mercas, D. Reidenbach (Eds) Combinatorics on Words. WORDS 2019.
  15. М. Гаец и К. Джи. Перечисление и расширения слов-представителей, arXiv:1909.00019.
  16. М. Гетц и К. Джи. Перечисление и расширения репрезентантов слов, Комбинаторика слов, 180-192, Lecture Notes in Comput. Sci., 11682, Springer, Cham, 2019.
  17. А. Гао, С. Китаев и П. Чжан. О 132-представимых графах. Австралазийский Дж. Комбин. 69 (2017), 105−118.
  18. ME Glen. Раскрашиваемость и словесное представление почти триангуляций, Pure Mathematics and Applications, 28(1), 2019, 70−76.
  19. ME Glen. О словесном представлении полимино-триангуляций и коронных графов, 2019. Кандидатская диссертация, Университет Стратклайда.
  20. ME Glen и S. Китаев. Word-представимость триангуляции прямоугольного полимино с одной плиткой домино, J. Combin.Math. Combin. Comput. 100, 131−144, 2017.
  21. М. Е. Глен, С. Китаев и А. Пяткин. О числе представлений графа короны, Discr. Appl. Math. 244, 2018, 89−93.
  22. М. М. Халлдорссон, С. Китаев, А. Пяткин О представимых графах, полутранзитивных ориентациях и числах представлений, arXiv:0810.0310 (2008).
  23. MM Halldórsson, S. Kitaev, A. Pyatkin (2010) Графы, фиксирующие чередования в словах. В: Y. Gao, H. Lu, S. Seki, S. Yu (ред.), Developments in Language Theory. DLT 2010. Lecture Notes Comp. Sci. 6224, Springer, 436−437.
  24. MM Halldórsson, S. Kitaev, A. Pyatkin (2011) Графы чередования. В: P. Kolman, J. Kratochvíl (ред.), Графовые концепции в информатике. WG 2011. Lecture Notes Comp. Sci. 6986, Springer, 191−202.
  25. М. Халлдорссон, С. Китаев и А. Пяткин. Полутранзитивные ориентации и графы, представимые в виде слов, Discr. Appl. Math. 201 (2016), 164−171.
  26. М. Джонс, С. Китаев, А. Пяткин и Дж. Реммель. Представление графов с помощью слов, избегающих шаблонов, Electron. J. Combin. 22 (2), Res. Pap. P2.53, 1−20 (2015).
  27. Китаев С. О графах с числом представлений 3, J. Autom., Lang. and Combin. 18 (2013), 97−112.
  28. S. Китаев. Всестороннее введение в теорию графов, представимых в виде слов. В: É. Charlier, J. Leroy, M. Rigo (ред.), Developments in Language Theory. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36−67.
  29. Китаев С. Существование u-представления графов, Журнал теории графов 85 (2017) 3, 661−668.
  30. Китаев С., Лонг Ю., Ма Дж., Ву Х. Представимость графов расщепления в виде слов, arXiv:1709.09725 (2017).
  31. Китаев С. и Лозин В. Слова и графы, Springer, 2015. ISBN  978-3-319-25859-1 .
  32. Китаев С. и Пяткин А. О представимых графах, J. Autom., Lang. and Combin. 13 (2008), 45−54.
  33. Китаев С. и Пяткин А. Графы, представимые в виде слов: обзор, Журнал прикладной и промышленной математики 12(2) (2018) 278−296.
  34. Китаев С. и Пяткин А. О полутранзитивной ориентируемости графов без треугольников, arXiv:2003.06204v1.
  35. Китаев С. и Сайто А. О полутранзитивной ориентируемости графов Кнезера и их дополнений, Дискретная математика, в печати.
  36. S. Китаев, P. Салимов, C. Северс и H. Ульфарссон (2011) О представимости линейных графов. В: G. Mauri, A. Leporati (ред.), Developments in Language Theory. DLT 2011. Lecture Notes Comp. Sci. 6795, Springer, 478−479.
  37. Китаев С. и Сейф С. Проблема слов полугруппы Перкинса с помощью направленных ациклических графов, Заказ 25 (2008), 177−194.
  38. Э. Лелуп. Представленные графики по большей части. Магистерская диссертация, Льежский университет, 2019 г.
  39. Мандельштам, О графах, представляемых словами, избегающими шаблонов, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.
  40. С. В. Китаев, А. В. Пяткин. Графы, представленные в виде слов. Обзор результатов, Дискретн. анализ и исследование. опер., 2018, том 25, номер 2, 19−53.

Программное обеспечение

Программное обеспечение для изучения графов, представляемых в виде слов, можно найти здесь:

  1. ME Glen. Программное обеспечение для работы с графами, представляемыми словами, 2017. Доступно по адресу https://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html.
  2. Х. Зантема. Программное обеспечение REPRNR для вычисления числа представлений графа, 2018. Доступно по адресу https://www.win.tue.nl/~hzantema/reprnr.html.

Ссылки

  1. ^ Steingrímsson, Einar (2023). "История группы комбинаторики Гётеборг–Рейкьявик–Стратклайд" (PDF) . Перечислительная комбинаторика и приложения . 3 (1): Статья S1H1. doi :10.54550/ECA2023V3S1H1.
  2. ^ abc С. Китаев и С. Сейф. Проблема слов полугруппы Перкинса с помощью направленных ациклических графов, Заказ 25 (2008), 177−194.
  3. ^ abcdefghij С. Китаев и В. Лозин. Words and Graphs, Springer, 2015. ISBN 978-3-319-25859-1 
  4. ^ abc С. Китаев и А. Пяткин. О представимых графах, J. Autom., Lang. and Combin. 13 (2008), 45−54.
  5. ^ ab MM Halldórsson, S. Kitaev, A. Pyatkin (2010) Graphs captureing alternations in words. В: Y. Gao, H. Lu, S. Seki, S. Yu (ред.), Developments in Language Theory. DLT 2010. Lecture Notes Comp. Sci. 6224, Springer, 436−437.
  6. ^ abc MM Halldórsson, S. Kitaev, A. Pyatkin (2011) Графы чередования. В: P. Kolman, J. Kratochvíl (ред.), Графовые концепции в информатике. WG 2011. Lecture Notes Comp. Sci. 6986, Springer, 191−202.
  7. ^ abcdefg М. Халлдорссон, С. Китаев и А. Пяткин. Полутранзитивные ориентации и графы, представимые в словах, Discr. Appl. Math. 201 (2016), 164−171.
  8. ^ abcd С. Китаев. Всестороннее введение в теорию графов, представимых в словах. В: É. Charlier, J. Leroy, M. Rigo (ред.), Developments in Language Theory. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36−67.
  9. ^ ab Китаев С. и Пяткин А. Графы, представимые в виде слов: обзор, Журнал прикладной и промышленной математики 12(2) (2018) 278−296.
  10. ^ аб С. В. Китаев, А. В. Пяткин. Графы, представленные в виде слов. Обзор результатов, Дискретн. анализ и исследование. опер., 2018, том 25,номер 2, 19−53
  11. ^ А. Коллинз, С. Китаев и В. Лозин. Новые результаты о графах, представимых в виде слов, Discr. Appl. Math. 216 (2017), 136–141.
  12. ^ Ö. Akgün, IP Gent, S. Kitaev, H. Zantema. Решение вычислительных задач в теории графов, представимых в виде слов. Journal of Integer Sequences 22 (2019), Статья 19.2.5.
  13. ^ abcd TZQ Chen, S. Kitaev, and A. Saito. Представление разделенных графов словами, arXiv:1909.09471
  14. ^ ab I. Choi, J. Kim и M. Kim. Об операциях, сохраняющих полутранзитивную ориентируемость графов, Journal of Combinatori Optimization 37 (2019) 4, 1351−1366.
  15. ^ ab Ö. Akgün, IP Gent, S. Kitaev, H. Zantema. Решение вычислительных задач в теории графов, представимых в виде слов. Journal of Integer Sequences 22 (2019), Статья 19.2.5.
  16. ^ ab М. Глен, С. Китаев и А. Пяткин. О числе представлений графа короны, Discr. Appl. Math. 244, 2018, 89–93.
  17. ^ ab M. Glen. Окрашиваемость и словесное представление почти триангуляций, Pure and Applied Mathematics, выйдет в 2019.
  18. ^ П. Акроботу, С. Китаев и З. Масарова. О представимости полимино-триангуляций в словах. Siberian Adv. Math. 25 (2015), 1−10.
  19. ^ М. Глен и С. Китаев. Word-Representability of Triangulations of Rectangular Polymino with a Single Domino Tile, J. Combin.Math. Combin. Comput. 100, 131−144, 2017.
  20. ^ TZQ Chen, S. Kitaev и BY Sun. Word-представимость гранных подразделений треугольных решетчатых графов, Graphs and Combin. 32(5) (2016), 1749−1761.
  21. ^ TZQ Chen, S. Kitaev и BY Sun. Word-представимость триангуляции графов цилиндров, покрытых сеткой, Discr. Appl. Math. 213 (2016), 60−70.
  22. ^ abc S. Китаев, Y. Long, J. Ma, H. Wu. Word-представимость расщепленных графов, arXiv:1709.09725 (2017).
  23. ^ А. Гао, С. Китаев и П. Чжан. О 132-представимых графах. Австралазиец Дж. Комбин. 69 (2017), 105−118.
  24. ^ Мандельштам. О графах, представляемых словами, избегающими шаблонов, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.
  25. ^ М. Джонс, С. Китаев, А. Пяткин и Дж. Реммель. Представление графов с помощью слов, избегающих шаблонов, Electron. J. Combin. 22 (2), Res. Pap. P2.53, 1−20 (2015).
  26. ^ M. Gaetz и C. Ji. Перечисление и расширения графов, представляемых словами. Lecture Notes in Computer Science 11682 (2019) 180−192. В R. Mercas, D. Reidenbach (Eds) Combinatorics on Words. WORDS 2019.
  27. ^ М. Гаец и К. Джи. Перечисление и расширения слов-представителей, arXiv:1909.00019.
  28. ^ Китаев С. Существование u-представления графов, Журнал теории графов 85 (2017) 3, 661−668.
  29. ^ ab G.-S. Cheon, J. Kim, M. Kim и A. Pyatkin. О k-11-представимых графах. J. Combin. 10 (2019) 3, 491−513.
  30. ^ Китаев С. О графах с числом представлений 3, J. Autom., Lang. and Combin. 18 (2013), 97−112.