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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

Sources