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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Задача нахождения треугольников[править | править вики-текст]

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

Можно проверить, есть ли в графе с m рёбрами треугольники за время O(m1.41).[1] Другой подход — найти след матрицы A3, где A — это матрица смежности графа. След равен нулю в том, и только в том случае, если в графе нет треугольников. Для плотных графов более эффективен этот простой алгоритм, основанный на умножении матриц, поскольку он снижает временную сложность до O(n2.373), где n – число вершин.

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

Сложность дерева решений[en] или сложность запроса[en] задачи, где запросы к оракулу, запоминающему матрицы смежности графа, равна Θ(n2). Однако для квантовых алгоритмов лучшая нижняя граница равна Ω(n), но лучший известный алгоритм имеет оценку O(n1.29) (Belovs 2011).

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

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

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

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

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

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

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

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

Имеются также некоторые результаты относительно связи раскраски с минимальной степенью графов без треугольников. Андрасфай и Эрдёш (Andrásfai, Erdős, Sós 1974) доказали, что любой граф с n вершинами без треугольников, в котором каждая вершина имеет более 2n/5 соседей, должен быть двудольным. Это лучший возможный результат такого типа, так как 5-цикл требует три цвета, но имеет в точности 2n/5 соседей для каждой вершины. Воодушевлённые этим результатом, Эрдёш и Симомонович (Erdős, Simonovits 1973) высказали гипотезу, что любой граф без треугольников с n вершинами, в котором каждая вершина имеет по меньшей мере n/3 соседей, может быть раскрашен только в три цвета. Однако Хэггквист (Häggkvist 1981) опроверг эту гипотезу, представив контрпример, в котором каждая вершина графа Грёча заменена независимым множеством специально подобранного размера. Джин (Jin 1995) показал, что любой граф без треугольников с n вершинами, в котором каждая вершина имеет более 10n/29 соседей можно раскрасить в 3 цвета. Это лучший результат этого типа, поскольку для графа Хэггквиста требуется четыре цвета и он имеет в точности 10n/29 соседей для каждой вершины. Наконец, Брандт и Томасси (Brandt, Thomassé 2006) доказали, что любой граф без треугольников с n вершинами, в котором любая вершина имеет более чем n/3 соседей, можно раскрасить в 4 цвета. Дополнительные результаты этого вида невозможны, поскольку Ха́йналь (Hajnal)[8] нашёл примеры графов без треугольников с произвольно большим хроматическим числом и минимальной степенью  (1/3 - \epsilon)n для любого \epsilon > 0 .

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

Sources
  • N. Alon, S. Ben-Shimon, M. Krivelevich A note on regular Ramsey graphs. — 2008..
  • N. Alon, R. Yuster, U. Zwick Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands. — 1994. — С. 354–364..
  • B. Andrásfai, P. Erdős, V. T. Sós On the connection between chromatic number, maximal clique and minimal degree of a graph // Discrete Mathematics. — 1974. — В. 3. — Т. 8. — С. 205–218. — DOI:10.1016/0012-365X(74)90133-2.
  • T. Bohman The triangle-free process. — 2008..
  • Ravi Boppana, Magnús M. Halldórsson Approximating maximum independent sets by excluding subgraphs // BIT. — 1992. — В. 2. — Т. 32. — С. 180–196. — DOI:10.1007/BF01994876.
  • S. Brandt, S. Thomassé Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem. — 2006..
  • N. Chiba, T. Nishizeki Arboricity and subgraph listing algorithms // SIAM Journal on Computing. — 1985. — В. 1. — Т. 14. — С. 210–223. — DOI:10.1137/0214017.
  • Vašek Chvátal Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). — Springer-Verlag, 1974. — Т. 406. — С. 243–246. — (Lecture Notes in Mathematics)..
  • P. Erdős, M. Simonovits On a valence problem in extremal graph theory // Discrete Mathematics. — 1973. — В. 4. — Т. 5. — С. 323–334. — DOI:10.1016/0012-365X(73)90126-X.
  • P. Erdős, S. Suen, P. Winkler On the size of a random maximal graph // Random Structures and Algorithms. — 1995. — В. 2–3. — Т. 6. — С. 309–318. — DOI:10.1002/rsa.3240060217.
  • John Gimbel, Carsten Thomassen Coloring triangle-free graphs with fixed size // Discrete Mathematics. — 2000. — В. 1-3. — Т. 219. — С. 275–277. — DOI:10.1016/S0012-365X(00)00087-X.
  • H. Grötzsch Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. — 1959. — Т. 8. — С. 109–120..
  • R. Häggkvist Graph Theory (Cambridge, 1981). — 1981. — С. 89–99..
  • Wilfried Imrich, Sandi Klavžar, Henry Martyn Median graphs and triangle-free graphs // SIAM Journal on Discrete Mathematics. — 1999. — В. 1. — Т. 12. — С. 111–118. — DOI:10.1137/S0895480197323494.
  • A. Itai, M. Rodeh Finding a minimum circuit in a graph // SIAM Journal on Computing. — 1978. — В. 4. — Т. 7. — С. 413–423. — DOI:10.1137/0207033.
  • G. Jin Triangle-free four-chromatic graphs // Discrete Mathematics. — 1995. — В. 1-3. — Т. 145. — С. 151–170. — DOI:10.1016/0012-365X(94)00063-O.
  • J. H. Kim The Ramsey number R(3,t) has order of magnitude \tfrac{t^2}{\log t} // Random Structures and Algorithms. — 1995. — В. 3. — Т. 7. — С. 173–207..
  • Frederic Magniez, Miklos Santha, Mario Szegedy Quantum Algorithms for the Triangle Problem. — 2003..
  • J. Mycielski Sur le coloriage des graphes // Colloq. Math.. — 1955. — Т. 3. — С. 161–162..
  • A. Nilli Triangle-free graphs with large chromatic numbers // Discrete Mathematics. — 2000. — В. 1–3. — Т. 211. — С. 261–262. — DOI:10.1016/S0012-365X(99)00109-0.
  • J. B. Shearer Note on the independence number of triangle-free graphs // Discrete Mathematics. — 1983. — В. 1. — Т. 46. — С. 83–87. — DOI:10.1016/0012-365X(83)90273-X.
  • C. Thomassen Grötzsch's 3-color theorem // Journal of Combinatorial Theory, Серия B. — 1994. — В. 2. — Т. 62. — С. 268–279. — DOI:10.1006/jctb.1994.1069.
  • Aleksandrs Belovs Span Programs for Functions with Constant-Sized 1-certificates. — 2011..