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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle Oleft ({frac {m ^ {1/3}} {(log m) ^ {2/3}}} ight)}$

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

Также было несколько результатов, касающихся раскраски до минимальной степени в графах без треугольников. Андрашфай, Эрдёш и Сош (1974) доказал, что любой п-вершинный граф без треугольников, в каждой вершине которого более 2п/ 5 соседи должны быть двудольными. Это наилучший возможный результат этого типа, так как 5-цикл требует трех цветов, но имеет ровно 2п/ 5 соседей на вершину. Мотивированные этим результатом, Эрдеш и Симоновиц (1973) предположил, что любой п-вершинный граф без треугольников, в котором каждая вершина имеет не менее п/ 3 соседей можно раскрасить только тремя цветами; Однако, Хэггквист (1981) опроверг эту гипотезу, найдя контрпример, в котором каждая вершина графа Грёча заменяется независимым множеством тщательно подобранного размера. Джин (1995) показал, что любой п-вершинный граф без треугольников, в котором каждая вершина имеет более 10п/ 29 соседи должны быть 3-х цветными; это наилучший возможный результат такого типа, потому что граф Хэггквиста требует четырех цветов и имеет ровно 10п/ 29 соседей на вершину. В заключение, Брандт и Томассе (2006) доказал, что любой п-вершинный граф без треугольников, в котором каждая вершина имеет более п/ 3 соседи должны быть 4-цветными. Дополнительные результаты такого типа невозможны, поскольку Хайнал^[9] нашли примеры графов без треугольников со сколь угодно большим хроматическим числом и минимальной степенью (1/3 - ε)п для любого ε> 0.

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

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

использованная литература

Заметки

Источники

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

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