Представленный в слове граф

В математической области теории графов словесно -представимый граф — это граф , который можно охарактеризовать словом (или последовательностью), элементы которого чередуются заданным образом. В частности, если множество вершин графа равно 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. что Наименьшим (по числу вершин) непредставимым словом графом является колесо W5 _{граф -} , который является единственным непредставимым словом графом на 6 вершинах.

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

История

Представленные в слове графы были представлены Сергеем Китаевым. в 2004 году на основе совместного исследования со Стивеном Сейфом. о полугруппе Перкинса , сыгравшей важную роль в теории полугрупп с 1960 года. Первое систематическое исследование графов, представимых в виде слов, было предпринято в 2008 году в статье Китаева и Артёма Пяткина. приступить к разработке теории. Одним из ключевых вкладчиков в эту область является Магнус М. Халлдорссон . На сегодняшний день по этой теме написано более 35 статей, и основная часть книги Сергея Китаева и Вадима Лозина посвящена теории словесно представимых графов. Быстрый способ познакомиться с местностью — прочитать одну из обзорных статей.

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

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

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

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

Граф G является перестановочно представимым, его можно представить словом вида p ₁ p ₂ ... p _k , где pi _{перестановка} - если . Он также может сказать, что перестановочно k G - представима . Граф является перестановочно представимым тогда и только тогда, когда он является графом сравнимости . Граф представим в словах означает, что окрестность каждой вершины представима перестановками (т. е. является графом сравнимости ). Обратное к последнему утверждению неверно. Однако тот факт, что окрестность каждой вершины является графом сравнимости, означает, что проблема максимальной клики полиномиально разрешима на графах, представимых в словах.

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

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

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

Непредставимые словами графы

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

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

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

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

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

Вычислительная сложность

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

ПРОБЛЕМА	СЛОЖНОСТЬ
решение о словесной репрезентативности	NP-полный
Доминирующий набор	NP-жесткий
Покрытие клики	NP-жесткий
Максимальный независимый набор	NP-жесткий
Великая клика	в П
аппроксимация числа представлений графа в пределах коэффициента n 1- е для любого ε > 0	NP-жесткий

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

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

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

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

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

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

Обобщения

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

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

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

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

Открытые проблемы с графами, представимыми в словах, можно найти в: и они включают в себя:

• Охарактеризуйте (не)представимые словами плоские графы.
• Охарактеризовать словесно представимые почти триангуляции, содержащие полный граф K ₄ (такая характеристика известна для K ₄ -свободных плоских графов ).
• Классифицируйте графы с номером представления 3. (См. за современное состояние в этом направлении.)
• Всегда ли линейный график графа, не представимого словами, всегда не представим в словах?
• Существуют ли графы на n вершинах, для представления которых требуется более пол( n /2) копий каждой буквы?
• Верно ли, что из всех двудольных графов коронные графы требуют самых длинных слов-представителей? (Видеть для соответствующего обсуждения.)
• Охарактеризовать графы, представимые в словах, в терминах (индуцированных) запрещенных подграфов.
• Какие (сложные) задачи на графах можно перевести в слова, представляющие их, и решить на словах (эффективно)?

Литература

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

1. Э. Акгюн, ИП Гент, С. Китаев, Х. Зантема. Решение вычислительных задач теории графов, представимых в словах. Журнал целочисленных последовательностей 22 (2019), статья 19.2.5.
2. П. Акроботу, С. Китаев и З. Масарова. О словесной представимости полимино триангуляций. Сибирский Адв. Математика. 25 (2015), 1−10.
3. Б. Броэр. Представимые в слове графы, 2018. Магистерская диссертация в Университете Радбауд, Неймеген.
4. Б. Броэр и Х. Зантема. « К -куб является k -представимым», J. Autom., Lang., and Combin. 24 (2019) 1, 3-12.
5. Дж. Н. Чен и С. Китаев. О 12-представимости индуцированных подграфов сеточного графа, Дискуссии Mathematicae Graph Theory, чтобы появиться
6. TZQ Чен, С. Китаев и А. Сайто. Представление разделенных графов словами, arXiv:1909.09471.
7. TZQ Chen, С. Китаев и BY Sun. Представимость в словах подразделений граней треугольных сеточных графов, Graphs и Combin. 32(5) (2016), 1749–1761.
8. TZQ Chen, С. Китаев и BY Sun. Представимость в словах триангуляций цилиндрических графов, покрытых сеткой, Дискрет. Прил. Математика. 213 (2016), 60−70.
9. Г.-С. Чеон, Дж. Ким, М. Ким и С. Китаев. Представимость в словах графов Теплица, Дискрет. Прил. Матем., появиться.
10. Г.-С. Чеон, Дж. Ким, М. Ким и А. Пяткин. О k -11-представимых графах. Дж. Комбин. 10 (2019) 3, 491−513.
11. И. Чой, Дж. Ким и М. Ким. Об операциях, сохраняющих полутранзитивную ориентацию графов, Журнал комбинаторной оптимизации 37 (2019) 4, 1351–1366.
12. А. Коллинз, С. Китаев и В. Лозин. Новые результаты о графах, представимых в словах, Дискрет. Прил. Математика. 216 (2017), 136−141.
13. А. Дайгаване, М. Сингх, Б. К. Джордж. 2-однородные слова: графы циклов и алгоритм проверки конкретных словесных представлений графов. arXiv:1806.04673 (2018).
14. М. Гаец и К. Джи. Перечисление и расширения словесно представимых графов. Конспект лекций по информатике 11682 (2019) 180−192. В Р. Меркасе, Д. Рейденбахе (ред.) Комбинаторика слов. СЛОВА 2019.
15. М. Гаец и К. Джи. Перечисление и расширения представителей Word, arXiv:1909.00019.
16. М. Гаец и К. Джи. Перечисление и расширение слов-представителей, Комбинаторика слов, 180–192, Конспекты лекций по вычислительной технике. Sci., 11682, Спрингер, Чам, 2019.
17. А. Гао, С. Китаев и П. Чжан. О 132-представимых графах. Австралазийский Дж. Комбин. 69 (2017), 105−118.
18. Я, Глен. Раскрашиваемость и представимость слов почти триангуляций, Чистая математика и приложения, 28(1), 2019, 70−76.
19. Я, Глен. О представимости полимино-триангуляций и коронных графов в словах, 2019. Кандидатская диссертация, Университет Стратклайда.
20. М. Е. Глен и С. Китаев. Представленность в словах триангуляций прямоугольного полимино с одной плиткой домино, J. Combin.Math. Комбинировать. Вычислить. 100, 131−144, 2017.
21. М. Е. Глен, С. Китаев и А. Пяткин. О числе представления коронного графа, Дискр. Прил. Математика. 244, 2018, 89−93.
22. М. М. Халлдорссон, С. Китаев, А. Пяткин О представимых графах, полутранзитивных ориентациях и числах представления, arXiv:0810.0310 (2008).
23. М.М. Халлдорссон, С. Китаев, А. Пяткин (2010) Графики, фиксирующие чередования в словах. В: Ю. Гао, Х. Лу, С. Секи, С. Ю (ред.), Развитие теории языка. DLT 2010. Конспекты лекций Сборник. наук. 6224, Спрингер, 436–437.
24. М.М. Халлдорссон, С. Китаев, А. Пяткин (2011) Графы альтернирования. В: П. Колман, Дж. Краточвил (редакторы), Теоретико-графовые концепции в информатике. WG 2011. Конспекты лекций Comp. наук. 6986, Спрингер, 191–202.
25. М. Халлдорссон, С. Китаев и А. Пяткин. Полутранзитивные ориентации и представимые в словах графы, Дискрет. Прил. Математика. 201 (2016), 164−171.
26. М. Джонс, С. Китаев, А. Пяткин и Дж. Реммель. Представление графиков с помощью слов, избегающих шаблонов, Electron. Дж. Комбин. 22 (2), Рез. Пап. С2.53, 1–20 (2015).
27. С. Китаев. О графах с номером представления 3, J. Autom., Lang. и Комбин. 18 (2013), 97−112.
28. С. Китаев. Всестороннее введение в теорию графов, представимых в словах. В: Э. Шарлье, Дж. Лерой, М. Риго (редакторы), Развитие теории языка. ДЛТ 2017. Конспект лекций Сост. наук. 10396, Спрингер, 36–67 лет.
29. С. Китаев. Существование u-представления графов, Journal of Graph Theory 85 (2017) 3, 661–668.
30. С. Китаев, Ю. Лонг, Дж. Ма, Х. Ву. Представленность разделенных графов в словах, arXiv:1709.09725 (2017).
31. С. Китаев и В. Лозин. Слова и графики, Springer, 2015. ISBN   978-3-319-25859-1 .
32. С. Китаев и А. Пяткин. О представимых графах, J. Autom., Lang. и Комбин. 13 (2008), 45−54.
33. С. Китаев и А. Пяткин. Графические представления, представимые в слове: обзор, Журнал прикладной и промышленной математики 12 (2) (2018) 278–296.
34. С. Китаев и А. Пяткин. О полутранзитивной ориентируемости графов без треугольников, arXiv:2003.06204v1.
35. С. Китаев и А. Сайто. О полутранзитивной ориентируемости графов Кнезера и их дополнений, Дискретная математика.
36. С. Китаев, П. Салимов, К. Северс и Х. Ульфарссон (2011) О представимости линейных графов. В: Г. Маури, А. Лепорати (редакторы), Развитие теории языка. DLT 2011. Конспекты лекций Сборник. наук. 6795, Спрингер, 478–479.
37. С. Китаев и С. Сейф. Словесная задача полугруппы Перкинса через ориентированные ациклические графы, Приказ 25 (2008), 177−194.
38. Э. Лелуп. Словесно представимые графы. Магистерская диссертация, Льежский университет, 2019 г.
39. Мандельштам. О графах, представляемых словами, избегающими шаблонов, Discountes Mathematicae Graph Theory 39 (2019) 375–389.
40. С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25,номер 2, 19−53.

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

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

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