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

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

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

В графе с 2n вершинами, не имеющем треугольников, должно быть меньше $n^2+1$ рёбер.

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

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

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

Как показали Имрих, Клавжар и Мулдер Шаблон:Harv, распознавание графов без треугольников эквивалентно по сложности с распознаванием медианных графов. Однако на текущий момент лучшие алгоритмы медианных графов используют в качестве подпрограммы распознавание треугольников, а не наоборот.

Шаблон:Не переведено 5 или Шаблон:Не переведено 5 задачи, где запросы к оракулу, запоминающему матрицы смежности графа, равна Θ(n²). Однако для квантовых алгоритмов лучшая нижняя граница равна Ω(n), но лучший известный алгоритм имеет оценку O(n^1.29) Шаблон:Harv.

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

Независимое множество из $\sqrt{n}$ вершин в графе с n вершинами, не имеющем треугольников, легко найти — либо существует вершина с более чем $\sqrt{n}$ соседями (в этом случае соседи образуют независимое множество), либо у всех вершин меньше чем $\sqrt{n}$ соседей (в этом случае любое наибольшее независимое множество должно иметь по меньшей мере $\sqrt{n}$ вершин)Шаблон:Sfn. Эту границу можно слегка улучшить — в любом графе без треугольников существует независимое множество с $\mathrm{\Omega }(\sqrt{n\log n})$ вершинами, а в некоторых графах без треугольников любое независимое множество имеет $O(\sqrt{n\log n})$ вершин.Шаблон:Sfn Один из способов создать графы без теугольников, в котором все независимые множества малы — это triangle-free process (процесс без треугольников), который создаёт максимальные графы без треугольников путём последовательного добавления случайно выбранных рёбер, избегая создания треугольников. С большой степенью вероятности процесс образует графы с числом независимости $O(\sqrt{n\log n})$. Можно найти также регулярные графы с теми же свойствами.Шаблон:Sfn

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

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

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

Мычельский Шаблон:Harv определил конструкцию, теперь называемую мычельскианом, которая образует новый граф без треугольников из другого графа без треугольников. Если граф имеет хроматическое число k, его мычельскиан имеет хроматическое число k + 1, так что данную конструкцию можно использовать, чтобы показать, что произвольно большое число цветов может потребоваться для раскраски непланарного графа без треугольников. В частности, граф Грёча, граф с 11 вершинами, образованный повторением конструкции Мычельского, является графом без треугольников, который нельзя раскрасить меньше чем четырьмя цветами, и является наименьшим графом с этими свойствами.Шаблон:Sfn Гимбель и Томассен Шаблон:Harv и Шаблон:Harv показали, что число цветов, необходимых для расцветки любого m-рёберного графа без треугольников, равно

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

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

Имеются также некоторые результаты относительно связи раскраски с минимальной степенью графов без треугольников. Андрасфай и Эрдёш Шаблон:Harv доказали, что любой граф с n вершинами без треугольников, в котором каждая вершина имеет более $2n/5$ соседей, должен быть двудольным. Это лучший возможный результат такого типа, так как 5-цикл требует три цвета, но имеет в точности $2n/5$ соседей для каждой вершины. Воодушевлённые этим результатом, Эрдёш и Симомонович Шаблон:Harv высказали гипотезу, что любой граф без треугольников с n вершинами, в котором каждая вершина имеет по меньшей мере $n/3$ соседей, может быть раскрашен только в три цвета. Однако Хэггквист Шаблон:Harv опроверг эту гипотезу, представив контрпример, в котором каждая вершина графа Грёча заменена независимым множеством специально подобранного размера. Джин Шаблон:Harv показал, что любой граф без треугольников с n вершинами, в котором каждая вершина имеет более $10n/29$ соседей, можно раскрасить в 3 цвета. Это лучший результат этого типа, поскольку для графа Хэггквиста требуется четыре цвета и он имеет в точности $10n/29$ соседей для каждой вершины. Наконец, Брандт и Томасси Шаблон:Harv доказали, что любой граф без треугольников с n вершинами, в котором любая вершина имеет более чем $n/3$ соседей, можно раскрасить в 4 цвета. Дополнительные результаты этого вида невозможны, поскольку Ха́йналь (Hajnal) нашёл примеры графов без треугольников с произвольно большим хроматическим числом и минимальной степенью $(1/3-ϵ)n$ для любого $ϵ>0$.

Ссылки

Sources

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья