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

Граф без троек смежных вершин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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) опроверг эту гипотезу, найдя контрпример, в котором каждая вершина графа Грётша заменяется независимым набором тщательно выбранного размера. Jin (1995) показал, что любой n- вершинный граф без треугольников, в котором каждая вершина имеет более 10 n /29 соседей, должен быть 3-раскрашиваемым; это наилучший возможный результат этого типа, поскольку граф Хэггквиста требует четырех цветов и имеет ровно 10 n /29 соседей на вершину. Наконец, Brandt & Thomassé (2006) доказали, что любой n -вершинный граф без треугольников, в котором каждая вершина имеет более n /3 соседей, должен быть 4-раскрашиваемым. Дополнительные результаты этого типа невозможны, поскольку Hajnal ^[11] нашел примеры графов без треугольников с произвольно большим хроматическим числом и минимальной степенью (1/3 − ε) n для любого ε > 0.

Смотрите также

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

Ссылки

Примечания

1. Алон, Юстер и Цвик (1994).
2. Аббуд и др. (2022 г.); Чан (2023 г.); Джин и Сюй (2023)
3. Ле Галл (2014), улучшение предыдущих алгоритмов Ли, Магниеса и Санты (2013) и Беловса (2012).
4. Боппана и Халлдорссон (1992) стр. 184, основано на идее из более раннего алгоритма аппроксимации раскраски Ави Вигдерсона .
5. Ким (1995).
6. Эрдеш, Суен и Винклер (1995); Бохман (2009).
7. Алон, Бен-Шимон и Кривелевич (2010).
8. Грётч (1959); Томассен (1994)).
9. Декарт (1947); Декарт (1954)
10. Хватал (1974).
11. см. Эрдеш и Симоновиц (1973).

Источники

• Аббуд, Амир; Брингманн, Карл; Хури, Сери; Замир, Ор (2022), «Трудность аппроксимации в P посредством удаления коротких циклов: обнаружение циклов, оракулы расстояний и т. д.», в Леонарди, Стефано; Гупта, Анупам (ред.), STOC '22: 54-й ежегодный симпозиум ACM SIGACT по теории вычислений, Рим, Италия, 20–24 июня 2022 г. , {ACM}, стр. 1487–1500, arXiv : 2204.10465 , doi : 10.1145/3519935.3520066, S2CID  248366492
• Алон, Нога ; Бен-Шимон, Сонни; Кривелевич, Майкл (2010), «Заметка о регулярных графах Рамсея», Журнал теории графов , 64 (3): 244–249, arXiv : 0812.2386 , doi : 10.1002/jgt.20453, MR  2674496, S2CID  1784886.
• Алон, Н .; Юстер, Р.; Цвик, У. (1994), «Поиск и подсчет циклов заданной длины», Труды 2-го Европейского симпозиума по алгоритмам, Утрехт, Нидерланды , стр. 354–364.
• Andrásfai, B.; Erdős, P .; Sós, VT (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), «Процесс без треугольников», Advances 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. Math. Monthly , 61 : 352.
• Chvátal, Vašek (1974), «Минимальность графа Мыцельского», Графы и комбинаторика (Proc. Capital Conf., George Washington Univ., Вашингтон, округ Колумбия, 1973) , Lecture Notes in Mathematics, т. 406, Springer-Verlag, стр. 243–246.
• Эрдёш, П.; Симоновиц , М. (1973), «О проблеме валентности в экстремальной теории графов», Дискретная математика , 5 (4): 323–334, doi : 10.1016/0012-365X(73)90126-X.
• Эрдёш, П.; Суен, С.; Винклер, П. (1995), «О размере случайного максимального графа», Случайные структуры и алгоритмы , 6 (2–3): 309–318, doi :10.1002/rsa.3240060217.
• Гимбел, Джон; Томассен, Карстен (2000), «Раскраска графов без треугольников с фиксированным размером», Дискретная математика , 219 (1–3): 275–277, doi : 10.1016/S0012-365X(00)00087-X.
• Гретч, Х. (1959), "Zur Theorie der Discreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. З. Мартин-Лютер-У., Галле-Виттенберг, Math.-Nat. Рейхе , 8 : 109–120..
• Häggkvist, R. (1981), «Нечетные циклы указанной длины в недвудольных графах», Теория графов (Кембридж, 1981), т. 62, стр. 89–99, doi :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.
• Jin, Ce; Xu, Yinzhan (2023), «Удаление аддитивной структуры в сокращениях на основе 3SUM», в Saha, Barna; Servedio, Rocco A. (ред.), Труды 55-го ежегодного симпозиума ACM по теории вычислений, STOC 2023, Орландо, Флорида, США, 20-23 июня 2023 г. , {ACM}, стр. 405–418, arXiv : 2211.07048 , doi : 10.1145/3564246.3585157, S2CID  253510334
• Джин, Г. (1995), «Четырехцветные графы без треугольников», Дискретная математика , 145 (1–3): 151–170, doi :10.1016/0012-365X(94)00063-O.
• Ким, Дж. Х. (1995), «Число Рамсея имеет порядок величины », Случайные структуры и алгоритмы , 7 (3): 173–207, doi :10.1002/rsa.3240070302, S2CID  16658980 ${\displaystyle R(3,t)}$ ${\displaystyle {\tfrac {t^{2}}{\log t}}}$.
• Ле Галль, Франсуа (октябрь 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), «Sur le coloriage desgraphes», Colloq. Математика. , 3 (2): 161–162, doi : 10,4064/см-3-2-161-162.
• Нилли, А. (2000), «Графы без треугольников с большими хроматическими числами», Дискретная математика , 211 (1–3): 261–262, doi : 10.1016/S0012-365X(99)00109-0.
• Ширер, Дж. Б. (1983), «Заметка о числе независимости графов без треугольников», Дискретная математика , 46 (1): 83–87, doi : 10.1016/0012-365X(83)90273-X.
• Томассен, К. (1994), «Теорема Грётша о трёх цветах», Журнал комбинаторной теории, Серия B , 62 (2): 268–279, doi : 10.1006/jctb.1994.1069.

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

• «Graphclass: triangle-free», Информационная система по классам графов и их включениям