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

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

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

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

• 1 Задача поиска треугольника
• 2 Число независимости и теория Рамсея
• 3 Раскрашивание графиков без треугольников
• 4 Чувствительность и чувствительность блоков
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

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

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

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

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

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

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

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

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

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

$O\; (m\; 1/3\; (журнал\; \; м)\; 2/3)\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (\{\backslash \; frac\; \{m\; ^\; \{1/3\}\}\; \{(\backslash \; log\; m)\; ^\; \{2/3\}\}\}\; \backslash \; right)\}$

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

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

Для булевой функции чувствительность $f\; \{\backslash \; displaystyle\; f\}$при $x\; \{\backslash \; displaystyle\; x\}$, обозначаемый $s\; (f,\; x)\; \{\backslash \; displaystyle\; s\; (f,\; x)\}$, представляет собой количество однобитовых изменений в $x\; \{\backslash \; displaystyle\; x\}$, которые изменяют значение $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$. Затем чувствительность определяется как максимальное значение чувствительности в $x\; \{\backslash \; displaystyle\; x\}$для всех значений $x\; \{\backslash \; displaystyle\; x\}$. Чувствительность блока, $b\; s\; (f)\; \{\backslash \; displaystyle\; bs\; (f)\}$, аналогичным образом определяется путем одновременного переключения нескольких битов. Хотя наиболее часто исследуемые булевы функции удовлетворяют $bs\; (f)\; =\; O\; (s\; (f))\; \{\backslash \; displaystyle\; bs\; (f)\; =\; O\; (s\; (f))\}$, гипотеза о чувствительности, что $bs\; (f)\; =\; O\; (s\; (f)\; 2)\; \{\backslash \; displaystyle\; bs\; (f)\; =\; O\; (s\; (f)\; ^\; \{2\})\}$оказалось трудно доказать, поэтому математикам рассмотреть вопрос о построении примеров функций, которые показывают большие промежутки между двумя величинами. Однако в июле 2019 года Хао Хуанг из Университета Эмори представил элегантное доказательство гипотезы о чувствительности.

Biderman et al. (2015) обнаружил самый большой известный разрыв между двумя величинами, рассматривая функцию, которая является индикаторной функцией для свойства быть изолированным графом без треугольников. Треугольник в графе $G\; \{\backslash \; displaystyle\; G\}$называется изолированным, если вершины, составляющие треугольник, не смежны ни с какими другими вершинами, кроме тех, которые составляют треугольник. Бидерман и др. (2015) далее показали, что этот результат сохраняется, когда «треугольник» заменяется любым циклом или любой кликой.

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

Примечания

Источники

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