Теорема Брукса

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Для полных графов требуется на единицу больше цветов, чем их максимальная степень. Эти графы и нечётные циклы являются единстевенными исключениями для теоремы Брукса.

Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов.

Теорема носит имя Леонарда Брукса (англ. R. Leonard Brooks), опубликовавшего доказательство теоремы в 1941 году. Раскраска с использованием числа цветов, указанной в теореме Брукса иногда называется раскраской Брукса, или Δ-раскраской.

Формулировка[править | править вики-текст]

Для связного ненаправленного графа G с максимальной степенью Δ, хроматическое число графа G не больше Δ, за исключением случаев, когда G — клика или нечётный цикл. В этих случаях хроматическое число равно Δ + 1.

Доказательство[править | править вики-текст]

Ласло Ловас (László Lovász 1975) даёт упрощённое доказательство теоремы Брукса[1]. Если граф не является двусвязным, его двусвязные компоненты можно раскрасить по отдельности, а затем объединить раскраски. Если граф содержит вершину v со степенью, меньшей Δ, то алгоритм жадной раскраски, который раскрашивает вершины согласно расстоянию от v (дальние — в первую очередь, ближние — в последнюю) использует максимум Δ цветов [1]. Таким образом, наиболее сложными случаями для доказательства являются двусвязные Δ-регулярные графы с Δ ≥ 3. Ловас показывает, что можно найти остовное дерево, такое что две несмежные соседи u и w корня v лежат на дереве. Присвоим вершинам u и w один (любой) цвет. Жадный алгоритм, начинаясь в u и w и проходящий остальные вершины остовного дерева (поднимаясь от корня к листьям), использует максимум Δ цветов. Когда все вершины, отличные от v, раскрашены, они имеют неокрашенного родителя, так что уже выкрашенные цвета не могут использовать все свободные цвета, поскольку два соседа v (u и w) имеют один цвет. В неиспользованный цвет раскрасим саму вершину v.

Обобщения[править | править вики-текст]

Более общая версия теоремы относится к предписанной раскраске[en] — если задан связный неориентированный граф с максимальной степенью Δ, не являющийся ни кликой, ни циклом нечётной длины, и список Δ цветов для каждой вершины, можно выбрать цвет каждой вершины из списка так, что никакие две смежные вершины не имеют один цвет. Другими словами, предписанное хроматическое число связного неориентированного графа никогда не превосходит Δ, если только G не является кликой или циклом нечётной длины. Теорема была доказана Визингом (Vizing 1976).

Для некоторых типов графов нужно даже меньше Δ цветов. Рид (Reed 1999) показал, что Δ − 1 цветов достаточно тогда и только тогда, когда граф не содержит Δ-клики, но при этом Δ должно быть достаточно большим. Для графов без треугольников, а также для более общего класса графов, в которых окрестности вершин достаточно разрежены, достаточно O(Δ/log Δ) цветов.[2]

Степень графов появляется также при оценке верхней границы другого типа окраски — рёберной. То, что хроматический индекс не превосходит Δ + 1 является теоремой Визинга. Расширение теоремы Брукса на тотальную раскраску, утверждающее, что тотальное хроматическое число не превосходит Δ + 2, было предложено Бехзадом и Визингом в качестве гипотезы. Теорема Хайналя — Семереди о равномерной раскраске[en] утверждает, что любой граф имеет (Δ + 1)-цветную раскраску, при которой число вершин двух различных цветов отличается максимум на единицу.

Алгоритмы[править | править вики-текст]

Δ-раскраску, или даже предписанную Δ-раскраску, графа со степенью Δ можно найти за линейное время.[3] Известны эффективные алгоритмы для поиска раскраски Брукса в параллельных и распределённых средах вычислений.[4]

Примечания[править | править вики-текст]

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

  • Noga Alon, Michael Krivelevich, Benny Sudakov Coloring graphs with sparse neighborhoods // Journal of Combinatorial Theory, Series B. — 1999. — В. 1. — Т. 77. — С. 73–82. — DOI:10.1006/jctb.1999.1910
  • R. L. Brooks On colouring the nodes of a network // Proc. Cambridge Philosophical Society, Math. Phys. Sci.. — 1941. — Т. 37. — С. 194–197. — DOI:10.1017/S030500410002168X.
  • Gary Chartrand, Ping Zhang Chromatic graph theory. — Boca Raton, London, New York: CRC Press/Chapman & Hall, 2009. — С. 187. — (Discrete Mathematics and its applications)..
  • David A. Grable, Alessandro Panconesi Journal of Algorithms. SODA '98: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. — Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1998. — Т. 37. — С. 473–480. — DOI:10.1006/jagm.2000.1097.
  • Péter Hajnal Brooks coloring in parallel // SIAM Journal on Discrete Mathematics. — 1990. — В. 1. — Т. 3. — С. 74–80. — DOI:10.1137/0403008.
  • H. J. Karloff An NC algorithm for Brooks' theorem // Theoretical Computer Science. — 1989. — В. 1. — Т. 68. — С. 89–103. — DOI:10.1016/0304-3975(89)90121-7.
  • L. Lovász Three short proofs in graph theory // Journal of Combinatorial Theory, Series B. — 1975. — Т. 19. — С. 269–271. — DOI:10.1016/0095-8956(75)90089-1.
  • Alessandro Panconesi The local nature of Δ-coloring and its algorithmic applications // Combinatorica. — 1995. — В. 2. — Т. 15. — С. 255–280. — DOI:10.1007/BF01200759.
  • Bruce Reed A strengthening of Brooks' theorem // Journal of Combinatorial Theory, Series B. — 1999. — В. 2. — Т. 76. — С. 136–149. — DOI:10.1006/jctb.1998.1891.
  • San Skulrattanakulchai Δ-List vertex coloring in linear time // Information Processing Letters. — 2006. — В. 3. — Т. 98. — С. 101–106. — DOI:10.1016/j.ipl.2005.12.007.
  • В.Г. Визинг Методы дискретного анализа в теории кодов и схем: сборник научных трудов.. — Новосибирск: Институт математики СО АН СССР, 1976. — Т. 29. — С. 3–10..
  • Weisstein, Eric W. Brooks' Theorem (англ.) на сайте Wolfram MathWorld.