Раскраска графа

Раскрасьте граф как можно меньшим числом цветов

Об этом калькуляторе

Калькулятор раскраски графа находит хроматическое число χ(G) — наименьшее число цветов, в которые можно раскрасить вершины графа так, чтобы ни одно ребро не соединяло две вершины одного цвета, — и показывает одну оптимальную раскраску. Введите число вершин и список рёбер; калькулятор точно вычисляет χ методом ветвей и границ, показывает максимальную степень Δ и наибольшую клику ω (нижнюю оценку χ), отмечает двудольные и полные графы и рисует раскрашенный граф. Полезно для составления расписаний, распределения регистров, раскраски карт и изучения хроматических чисел.

Как раскрасить граф

  1. Введите число вершин; они нумеруются от 1 до n.
  2. Перечислите рёбра парами вида 1-2, 2-3 — по одной паре на каждое соединение.
  3. Посмотрите хроматическое число χ(G) и цвет, назначенный каждой вершине.
  4. Сравните χ с наибольшей кликой ω, чтобы понять, почему нужно именно столько цветов, или загрузите пример для изучения.

Типичные примеры

  • Треугольнику (K₃) нужно 3 цвета — все пары его вершин смежны.
  • Чётные циклы двудольны, и им достаточно 2 цветов; нечётным циклам, таким как C₅, нужно 3.
  • Полному графу Kₙ нужно ровно n цветов.
  • Наибольшая клика размера ω требует не менее ω цветов, поэтому χ(G) ≥ ω.
  • Графу Грёцша нужно 4 цвета, хотя в нём нет треугольников, поэтому χ может превышать кликовое число.

Часто задаваемые вопросы

Что такое хроматическое число?

Хроматическое число χ(G) — это наименьшее число цветов, необходимое для раскраски вершин графа так, чтобы ни одно ребро не соединяло две вершины одного цвета.

Как находится минимальное число цветов?

Поскольку граф небольшой, калькулятор ищет точно: пробует 1 цвет, затем 2 и так далее и возвращает первое число, при котором существует правильная раскраска. Это число гарантированно является истинным минимумом.

Что такое максимальная степень и наибольшая клика?

Максимальная степень Δ — наибольшее число рёбер, сходящихся в одной вершине. Наибольшая клика ω — самое большое множество попарно смежных вершин; поскольку все они должны иметь разные цвета, χ(G) не меньше ω.

Почему графу без треугольников всё равно может понадобиться много цветов?

Большая клика требует много цветов, но это не единственная причина. Нечётным циклам и графам вроде графа Грёцша нужны дополнительные цвета даже без треугольников, поэтому χ(G) может быть больше кликового числа.

Есть ли ограничение на размер графа?

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