Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Проблема с поиском треугольника [ править ]

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

Можно проверить, является ли граф с m ребрами свободным от треугольников за время O ( m 1,41 ). [1] Другой подход состоит в нахождении следов от А 3 , где является матрицей смежности графа. След равен нулю тогда и только тогда, когда граф не содержит треугольников. Для плотных графов более эффективно использовать этот простой алгоритм, основанный на умножении матриц , поскольку он снижает временную сложность до O ( n 2.373 ), где n - количество вершин.

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

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

Число независимости и теория Рамсея [ править ]

Независимое множество из √ п вершин в п -vertex графа треугольника свободной легко найти: либо существует вершина с более чем √ п соседей (в этом случае эти соседи независимое множество) или все вершины имеют меньше , чем √ n соседей (в этом случае любое максимальное независимое множество должно иметь не менее √ n вершин). [3] Эта граница может быть немного ужесточена: в каждом графе без треугольников существует независимое множество вершин, а в некоторых графах без треугольников каждое независимое множество имеет вершины. [4]Один из способов создания графов без треугольников, в которых все независимые множества малы, - это процесс без треугольников [5], в котором генерируется максимальный граф без треугольников путем многократного добавления случайно выбранных ребер, которые не завершают треугольник. С большой вероятностью этот процесс дает граф с числом независимости . Также можно найти регулярные графы с такими же свойствами. [6]

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

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

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

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

Mycielski (1955) определил конструкцию, теперь называемую Mycielskian , для формирования нового графа без треугольников из другого графа без треугольников. Если у графа есть хроматическое число k , то его Микельскиан имеет хроматическое число k  + 1, поэтому эту конструкцию можно использовать, чтобы показать, что для раскрашивания неплоских графов без треугольников может потребоваться сколь угодно большое количество цветов. В частности, граф Грёча, граф с 11 вершинами, образованный повторным применением конструкции Мицельского, является графом без треугольников, который не может быть раскрашен менее чем в четыре цвета, и является наименьшим графом с этим свойством. [8] Гимбел и Томассен (2000) и Нилли (2000)показал, что количество цветов, необходимых для раскраски любого m- краевого графа без треугольников, равно

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

Также было несколько результатов, касающихся раскраски до минимальной степени в графах без треугольников. Андрашфай, Эрдеш и Сош (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-раскрашиваемым. Дополнительные результаты такого типа невозможны, поскольку Хайнал [9]нашли примеры графов без треугольников со сколь угодно большим хроматическим числом и минимальной степенью (1/3 - ε) n для любого ε> 0.

См. Также [ править ]

  • Граф Андрашфаи , семейство циркулянтных графов без треугольников с диаметром два
  • Граф Хенсона , бесконечный граф без треугольников, который содержит все конечные графы без треугольников как индуцированные подграфы
  • Задача о монохроматическом треугольнике , задача о разбиении ребер данного графа на два графа без треугольников.
  • Задача Ружи – Семереди на графах, в которых каждое ребро принадлежит ровно одному треугольнику

Ссылки [ править ]

Примечания
  1. ^ Алон, Юстер и Цвик (1994) .
  2. ^ Le Gall (2014) , улучшая предыдущие алгоритмы Lee, Magniez & Santha (2013) и Belovs (2012) .
  3. ^ Boppana & Halldórsson (1992) р. 184, основанный на идее из более раннего алгоритма аппроксимации окраски Ави Вигдерсона .
  4. ^ Ким (1995) .
  5. ↑ Erds, Suen & Winkler (1995) ; Бохман (2009) .
  6. ↑ Алон, Бен-Шимон и Кривелевич (2010) .
  7. ^ Grötzsch (1959) ; Томассен (1994) ).
  8. ^ Chvátal (1974) .
  9. ^ см. Erdős & Simonovits (1973) .
Источники
  • Алон, Нога ; Бен-Шимон, Сонни; Кривелевич, Майкл (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..
  • Andrásfai, B .; Erdős, P .; Sos, В. Т. (1974), "О связи между хроматическим числом, максимальной кликой и минимальной степенью графа" (PDF) , дискретная математика , 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), «Процесс без треугольников», Успехи в математике , 221 (5): 1653–1677, arXiv : 0806.4375 , doi : 10.1016 / j.aim.2009.02.018 , MR  2522430 , S2CID  17701040.
  • Боппана, Рави; Halldórsson, Magnus М. (1992), "Аппроксимация максимальных независимых множеств, исключая подграфы", БИТ , 32 (2): 180-196, DOI : 10.1007 / BF01994876 , МР  1172185 , S2CID  123335474.
  • Brandt, S .; Томассе, С. (2006), Плотные графы без треугольников можно раскрашивать в четыре цвета: решение проблемы Эрдеша – Симоновица (PDF).
  • Chiba, N .; Nishizeki, Т. (1985), "Arboricity и алгоритмы подграф листинга" , SIAM журнал по вычислениям , 14 (1): 210-223, DOI : 10,1137 / 0214017 , S2CID  207051803.
  • Chvátal, Вашек (1974), "Минимальность графа Mycielski", Графы и комбинаторика (Proc. Capital Conf., Университет Джорджа Вашингтона, Вашингтон, округ Колумбия, 1973) , Lecture Notes in Mathematics, 406 , Springer-Verlag, pp 243–246.
  • Erdős, P .; Simonovits, M. (1973), "Об одной задачи валентной в экстремальной теории графов", дискретная математика , 5 (4): 323-334, DOI : 10.1016 / 0012-365X (73) 90126-X.
  • Erdős, P .; Suen, S .; Винклер П. (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 diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Рейхе , 8 : 109–120.
  • Häggkvist, R. (1981), "нечетные циклы заданной длины в nonbipartite графов", Теория графов (Кембридж, 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.
  • Itai, A .; Rodeh, М. (1978), "Нахождение минимальной цепи в графе", SIAM журнал по вычислениям , 7 (4): 413-423, DOI : 10,1137 / 0207033.
  • Джин, Г. (1995), "Треугольник свободные четыре-хроматические графы", дискретная математика , 145 (1-3): 151-170, DOI : 10.1016 / 0012-365X (94) 00063-О.
  • Ким, JH (1995), "Число Рэмси имеет порядок величины " R ( 3 , t ) {\displaystyle R(3,t)} t 2 log ⁡ t {\displaystyle {\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.
  • Ли, Трой; Магнье, Фредерик; Santha, Miklos (2013), «Улучшенные алгоритмы квантовых запросов для поиска треугольников и тестирования ассоциативности» , Материалы двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2013) , Новый Орлеан, Луизиана, стр. 1486–1502, ISBN 978-1-611972-51-1.
  • Mycielski, J. (1955), "Sur le coloriage des graphes", 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.
  • Thomassen, C. (1994), "3-цветный теорема Грётша", Журнал комбинаторной теории, серии B , 62 (2): 268-279, DOI : 10,1006 / jctb.1994.1069.

Внешние ссылки [ править ]

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