График без треугольников

В математической области теории графов граф без треугольников — это неориентированный граф, в котором никакие три вершины не образуют треугольник ребер. Графы без треугольников можно эквивалентным образом определить как графы с числом кликов ≤ 2, графы с обхватом ≥ 4, графы без индуцированного 3-цикла или локально независимые графы.

Графы без треугольников с наибольшим количеством ребер в вершинах являются сбалансированными полными двудольными графами . Многие графы без треугольников не являются двудольными, например, любой граф циклов C _n для нечетного n > 3.

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

Задача нахождения треугольника

Проблема поиска треугольников или проблема обнаружения треугольников — это проблема определения того, является ли граф свободным от треугольников или нет. Когда граф содержит треугольник, алгоритмам часто требуется вывести три вершины, образующие треугольник в графе.

Можно проверить, является ли график с $m$ ребра не имеют треугольников во времени ${\tilde {O}}{\bigl (}m^{2\omega /(\omega +1)}{\bigr )}$ где ${\tilde {O}}$ скрывает субполиномиальные факторы. Здесь $\omega$ – показатель быстрого умножения матриц ; $\omega <2.372$ из чего следует, что обнаружение треугольников можно решить за время $O(m^{1.407})$. подход состоит в том, чтобы найти след A Другой ³ , где A — матрица смежности графа. След равен нулю тогда и только тогда, когда граф не содержит треугольников. Для плотных графов более эффективно использовать этот простой алгоритм, который снова основан на умножении матриц, поскольку он снижает временную сложность до $O(n^{\omega })$, где $n$ это количество вершин.

Даже если алгоритмы умножения матриц со временем $O(n^{2})$ были обнаружены, наилучшие временные рамки, на которые можно было бы рассчитывать при использовании этих подходов, таковы: $O(m^{4/3})$ или $O(n^{2})$. В мелкозернистой сложности гипотеза разреженного треугольника представляет собой недоказанное предположение о вычислительной сложности, утверждающее, что форма не ограничена по времени. $O(m^{4/3-\delta })$ возможно, для любого $\delta >0$, относительно того, какие алгоритмические методы используются. Это и соответствующая гипотеза плотного треугольника о том, что нет временных ограничений в форме $O(n^{\omega -\delta })$ возможно, подразумевают нижние оценки для некоторых других вычислительных задач комбинаторной оптимизации и вычислительной геометрии .

Как показали Имрих, Клавжар и Малдер (1999) , распознавание графов без треугольников по сложности эквивалентно распознаванию медианных графов ; однако лучшие на данный момент алгоритмы распознавания медианных графов используют обнаружение треугольников как подпрограмму, а не наоборот.

Сложность дерева решений или сложность запроса задачи, когда запросы относятся к оракулу, хранящему матрицу смежности графа, равна Θ( n ² ) . Однако для квантовых алгоритмов самая известная нижняя граница — это Ω( n ) , а самый известный алгоритм — O ( n ^5/4 ) .

Число независимости и теория Рамсея

набор Независимый ​ $\lfloor {\sqrt {n}}\rfloor$ вершины (где $\lfloor \cdot \rfloor$ — функция пола ) в n -вершинном графе без треугольников найти легко: либо существует вершина с хотя бы $\lfloor {\sqrt {n}}\rfloor$ соседей (в этом случае эти соседи представляют собой независимое множество) или все вершины имеют строго меньше, чем $\lfloor {\sqrt {n}}\rfloor$ соседей (в этом случае любое максимальное независимое множество должно иметь не менее $\lfloor {\sqrt {n}}\rfloor$ вершины). Эту оценку можно немного ужесточить: в каждом графе без треугольников существует независимый набор $\Omega ({\sqrt {n\log n}})$ вершин, а в некоторых графах без треугольников каждое независимое множество имеет $O({\sqrt {n\log n}})$ вершины. Одним из способов создания графов без треугольников, в которых все независимые множества малы, является процесс без треугольников. в котором создается максимальный граф без треугольников путем многократного добавления случайно выбранных ребер, которые не завершают треугольник. С высокой вероятностью этот процесс создает граф с числом независимости $O({\sqrt {n\log n}})$. Также можно найти регулярные графы с теми же свойствами.

Эти результаты можно также интерпретировать как предоставление асимптотических оценок чисел Рамсея R(3, t ) вида $\Theta ({\tfrac {t^{2}}{\log t}})$: если ребра полного графа на $\Omega ({\tfrac {t^{2}}{\log t}})$ вершины окрашены в красный и синий цвета, то либо красный граф содержит треугольник, либо, если он не содержит треугольников, то он должен иметь независимое множество размера t, соответствующее клике того же размера в синем графе.

Раскраска графов без треугольников

Граф Грётча — это граф без треугольников, который нельзя раскрасить менее чем в четыре цвета.

Многие исследования графов без треугольников были сосредоточены на раскраске графов . Каждый двудольный граф (то есть каждый граф, раскрашиваемый в 2 цвета) не содержит треугольников, а теорема Греча без треугольников утверждает, что каждый плоский граф может быть 3-цветным. Однако для неплоских графов без треугольников может потребоваться гораздо больше трех цветов.

Первая конструкция графов без треугольников со сколь угодно большим хроматическим числом принадлежит Тутте (писавшему как Бланш Декарт) . ). Эта конструкция началась с графа с одной вершиной, скажем $G_{1}$ и индуктивно построенный $G_{k+1}$ от $G_{k}$ следующим образом: пусть $G_{k}$ иметь $n$ вершин, затем возьмем набор $Y$ из $k(n-1)+1$ вершин и для каждого подмножества $X$ из $Y$ размера $n$ добавить несвязную копию $G_{k}$ и присоединиться к нему $X$ с соответствием. Из принципа «ячейки» индуктивно следует, что $G_{k+1}$ не $k$ раскрашиваемо, поскольку хотя бы одно из множеств $X$ должен быть окрашен в однотонный цвет, если нам разрешено использовать только k цветов. Мицельский (1955) определил конструкцию, теперь называемую Мицельскианом , для формирования нового графа без треугольников из другого графа без треугольников. Если граф имеет хроматическое число k , его Мицельскиан имеет хроматическое число k + 1, поэтому эту конструкцию можно использовать, чтобы показать, что для раскраски неплоских графов без треугольников может потребоваться сколь угодно большое количество цветов. В частности , граф Греча , граф с 11 вершинами, образованный повторным применением конструкции Мицельского, представляет собой граф без треугольников, который нельзя раскрасить менее чем в четыре цвета, и является наименьшим графом с этим свойством. Гимбел и Томассен (2000) и Нилли (2000) показали, что количество цветов, необходимых для раскраски любого графа без треугольников с m -ребрами, равно

$O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)$

и что существуют графы без треугольников, хроматические числа которых пропорциональны этой границе.

Также было получено несколько результатов, касающихся окраски минимальной степени в графах без треугольников. Андрашфаи, Эрдеш и Сос (1974) доказали, что любой n -вершинный граф без треугольников, в котором каждая вершина имеет более 2 n /5 соседей, должен быть двудольным. Это наилучший возможный результат такого типа, поскольку 5-цикл требует трех цветов, но имеет ровно 2 n /5 соседей на каждую вершину. Руководствуясь этим результатом, Эрдеш и Симоновиц (1973) предположили, что любой n граф без треугольников с -вершинами, в котором каждая вершина имеет не менее n /3 соседей, может быть раскрашен только тремя цветами; однако Хэггквист (1981) опроверг эту гипотезу, найдя контрпример, в котором каждая вершина графа Грётча заменяется независимым набором тщательно выбранного размера. Джин (1995) показал, что любой граф без треугольников с n -вершинами, в котором каждая вершина имеет более 10 n /29 соседей, должен быть раскрашиваем в 3 цвета; это наилучший возможный результат такого типа, поскольку граф Хэггквиста требует четырех цветов и имеет ровно 10 n /29 соседей на вершину. Окончательно, Брандт и Томассе (2006) доказали, что любой n- вершинный граф без треугольников, в котором каждая вершина имеет более n /3 соседей, должен быть раскрашиваем в 4 цвета. Дополнительные результаты этого типа невозможны, так как Хайнал нашел примеры графов без треугольников со сколь угодно большим хроматическим числом и минимальной степенью (1/3 - ε) n для любого ε > 0.

См. также

• Граф Андрашфаи , семейство циркулянтных графов без треугольников диаметром два.
• Граф Хенсона — бесконечный граф без треугольников, который содержит все конечные графы без треугольников в качестве индуцированных подграфов.
• Граф сдвига , семейство графов без треугольников с произвольно большим хроматическим числом.
• График Кнезера $KG_{3k-1,k}$ не содержит треугольников и имеет хроматическое число $k+1$
• Проблема монохроматического треугольника , проблема разделения ребер данного графа на два графа без треугольников.
• Проблема Ружи – Семереди о графах, в которых каждое ребро принадлежит ровно одному треугольнику.

Ссылки

Источники

• Аббуд, Амир; Брингманн, Карл; Хури, Сери; Замир, Ор (2022), «Трудность аппроксимации в P посредством удаления короткого цикла: обнаружение цикла, оракулы расстояний и не только», Леонарди, Стефано; Гупта, Анупам (ред.), STOC '22: 54-й ежегодный симпозиум ACM SIGACT по теории вычислений, Рим, Италия, 20–24 июня 2022 г. , {ACM}, стр. 1487–1500, arXiv : 2204.10465 , doi : 10.1145 /3519935.3520066 , S2CID   248366492
• Алон, Нога ; Бен-Шимон, Сонни; Кривелевич, Майкл (2010), «Заметки о регулярных графах Рэмси», Journal of Graph Theory , 64 (3): 244–249, arXiv : 0812.2386 , doi : 10.1002/jgt.20453 , MR   2674496 , S2CID   1784886 .
• Алон, Н. ; Юстер, Р.; Цвик, У. (1994), «Нахождение и подсчет циклов заданной длины», Труды 2-го Европейского симпозиума по алгоритмам, Утрехт, Нидерланды , стр. 354–364 .
• Андрасфаи, Б.; Эрдеш, П .; Сос, В.Т. (1974), «О связи между хроматическим числом, максимальной кликой и минимальной степенью графа» (PDF) , Discrete Mathematics , 8 (3): 205–218, doi : 10.1016/0012-365X(74) 90133-2 .
• Беловс, Александрс (2012), «Программы Span для функций с 1-сертификатами постоянного размера», Труды сорок четвертого ежегодного симпозиума ACM по теории вычислений (STOC '12) , Нью-Йорк, Нью-Йорк, США: ACM, стр. . 77–84, arXiv : 1105.4024 , doi : 10.1145/2213977.2213985 , ISBN.  978-1-4503-1245-5 , S2CID   18771464 .
• Боман, Том (2009), «Процесс без треугольников», Advance in Mathematics , 221 (5): 1653–1677, arXiv : 0806.4375 , doi : 10.1016/j.aim.2009.02.018 , MR   2522430 , S2CID   17701040 .
• Боппана, Рави; Халлдорссон, Магнус М. (1992), «Аппроксимация максимальных независимых множеств путем исключения подграфов», BIT , 32 (2): 180–196, doi : 10.1007/BF01994876 , MR   1172185 , S2CID   123335474 .
• Брандт, С.; Томассе, С. (2006), Плотные графы без треугольников раскрашиваются в четыре цвета: решение проблемы Эрдеша – Симоновица (PDF) .
• Чан, Тимоти М. (2023), «Поиск треугольников и других небольших подграфов в графах геометрических пересечений», в Бансале, Нихил; Нагараджан, Вишванат (ред.), Труды симпозиума ACM-SIAM 2023 по дискретным алгоритмам, SODA 2023, Флоренция, Италия, 22–25 января 2023 г. , {SIAM}, стр. 1777–1805, arXiv : 2211.05345 , doi : 10.1137/1.9781611977554.ch68
• Чиба, Н.; Нишизеки, Т. (1985), «Древовидность и алгоритмы перечисления подграфов», SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 , S2CID   207051803 .
• Декарт, Бланш (апрель 1947 г.), «Задача трёх цветов», Эврика , 21 .
• Декарт, Бланш (1954), «Решение сложной проблемы № 4526», Amer. Математика. Ежемесячно , 61 :352 .
• Хватал, Вашек (1974), «Минимальность графа Мисельского», Графы и комбинаторика (Proc. Capital Conf., Университет Джорджа Вашингтона, Вашингтон, округ Колумбия, 1973) , Конспекты лекций по математике, том. 406, Springer-Verlag, стр. 243–246 .
• Эрдеш, П .; Симоновиц, М. (1973), «О проблеме валентности в экстремальной теории графов», Discrete Mathematics , 5 (4): 323–334, doi : 10.1016/0012-365X(73)90126-X .
• Эрдеш, П .; Суен, С.; Винклер, П. (1995), «О размере случайного максимального графа», Случайные структуры и алгоритмы , 6 (2–3): 309–318, doi : 10.1002/rsa.3240060217 .
• Гимбел, Джон; Томассен, Карстен (2000), «Раскраска графов без треугольников фиксированного размера», Discrete Mathematics , 219 (1–3): 275–277, doi : 10.1016/S0012-365X(00)00087-X .
• Гретч, Х. (1959), «К теории дискретных сущностей, VII: теорема о трех цветах для сетей без трех окружностей на сфере», Wiss. З. Мартин-Лютер-У., Галле-Виттенберг, Math.-Nat. Серия , 8 : 109–120 .
• Хэггквист, Р. (1981), «Нечетные циклы заданной длины в недвудольных графах», Теория графов (Кембридж, 1981) , том. 62, стр. 89–99, номер документа : 10.1016/S0304-0208(08)73552-7 .
• Имрих, Вильфрид; Клавжар, Санди; Малдер, Генри Мартин (1999), «Медианные графики и графики без треугольников», SIAM Journal on Discrete Mathematics , 12 (1): 111–118, doi : 10.1137/S0895480197323494 , MR   1666073 , S2CID   14364050 .
• Итай, А.; Роде, М. (1978), «Нахождение минимальной схемы в графе», SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137/0207033 .
• Джин, Се; Сюй, Иньжан (2023), «Удаление аддитивной структуры в сокращениях на основе 3SUM», в Саха, Барна; Серведио, Рокко А. (ред.), Труды 55-го ежегодного симпозиума ACM по теории вычислений, STOC 2023, Орландо, Флорида, США, 20–23 июня 2023 г. , {ACM}, стр. 405–418, arXiv : 2211.07048 , doi : 10.1145/3564246.3585157 , S2CID   253510334
• Джин, Г. (1995), «Четыреххроматические графы без треугольников», Discrete Mathematics , 145 (1–3): 151–170, doi : 10.1016/0012-365X(94)00063-O .
• Ким, Дж. Х. (1995), «Число Рэмси $R(3,t)$ имеет порядок величины ${\tfrac {t^{2}}{\log t}}$", Случайные структуры и алгоритмы , 7 (3): 173–207, doi : 10.1002/rsa.3240070302 , S2CID   16658980 .
• Ле Галль, Франсуа (октябрь 2014 г.), «Улучшенный квантовый алгоритм поиска треугольников с помощью комбинаторных аргументов», Труды 55-го ежегодного симпозиума по основам компьютерных наук (FOCS 2014) , IEEE, стр. 216–225, arXiv : 1407.0085 , doi : 10.1109/focs.2014.31 , ISBN  978-1-4799-6517-5 , S2CID   5760574 .
• Ли, Трой; Манье, Фредерик; Санта, Миклос (2013), «Улучшенные алгоритмы квантовых запросов для поиска треугольников и проверки ассоциативности» , Труды двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2013): Новый Орлеан, Луизиана, США, 6–8 января. , 2013 , Ассоциация вычислительной техники (ACM); Общество промышленной и прикладной математики (SIAM), стр. 1486–1502, ISBN.  978-1-611972-51-1 .
• Мисельски, Дж. (1955), “О раскраске графов”, Коллок. Математика. , 3 (2): 161–162, doi : 10,4064/см-3-2-161-162 .
• Нилли, А. (2000), «Графы без треугольников с большими хроматическими числами», Discrete Mathematics , 211 (1–3): 261–262, doi : 10.1016/S0012-365X(99)00109-0 .
• Ширер, Дж. Б. (1983), «Примечание о числе независимости графов без треугольников», Discrete Mathematics , 46 (1): 83–87, doi : 10.1016/0012-365X(83)90273-X .
• Томассен, К. (1994), «Теорема Греча о трех цветах», Журнал комбинаторной теории, серия B , 62 (2): 268–279, doi : 10.1006/jctb.1994.1069 .

Внешние ссылки

• «Графкласс: без треугольников» , Информационная система по классам графов и их включениям