Калькулятор раскраски графов

О Калькулятор раскраски графов

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

Что такое раскраска графа?

Правильная раскраска вершин графа G = (V, E) — это сопоставление цвета каждой вершине так, чтобы концы каждого ребра имели разные цвета. Хроматическое число, обозначаемое χ(G), — это наименьшее количество цветов, при котором такая раскраска возможна. Вычисление χ(G) в общем случае является NP-трудной задачей, но эта проблема имеет красивую математическую теорию и множество практических приложений: составление расписания экзаменов, распределение радиочастот, распределение регистров в компиляторах и знаменитая теорема о четырех красках для плоских карт.

Ключевые теоремы и границы

• Тривиальные границы: 1 ≤ χ(G) ≤ |V| для любого графа.
• Нижняя граница клики: χ(G) ≥ ω(G), где ω(G) — размер максимальной клики.
• Характеристика двудольности: χ(G) ≤ 2 тогда и только тогда, когда в G нет нечетных циклов (Кёниг).
• Теорема Брукса: χ(G) ≤ Δ(G), если G не является полным графом или нечетным циклом; в этих случаях χ(G) = Δ(G) + 1. Здесь Δ(G) — максимальная степень вершины.
• Теорема о четырех красках: Любой планарный граф можно раскрасить в 4 цвета.
• Жадная верхняя граница: Любой жадный алгоритм использует не более Δ(G) + 1 цветов.

Алгоритмы, используемые в этом калькуляторе

DSATUR (Degree of Saturation)

Предложенный Дэниелом Брелазом в 1979 году, DSATUR является одной из самых мощных практических эвристик для раскраски графов. Он последовательно выбирает нераскрашенную вершину с максимальной степенью насыщенности (количество различных цветов у уже раскрашенных соседей). При равенстве выбирается вершина с наибольшей степенью в нераскрашенном подграфе. Вершине назначается минимально возможный цвет. DSATUR оптимален для двудольных графов и многих структурированных семейств графов, работая за миллисекунды на графах с сотнями вершин.

Уэлша-Пауэлла (Welsh-Powell)

Алгоритм Уэлша-Пауэлла сортирует вершины в порядке убывания их степеней, а затем раскрашивает их жадным способом. Он работает за время O(|V|²) и гарантирует использование не более Δ(G) + 1 цветов. Это чрезвычайно быстрый алгоритм, который часто служит хорошим первым приближением.

Жадный алгоритм (по порядку ввода)

Самый простой алгоритм: проход по вершинам в порядке их ввода и назначение каждой из них минимального свободного цвета. Результат сильно зависит от порядка вершин, но случайный порядок дает базовый уровень для сравнения с более умными эвристиками.

Точный поиск с возвратом (Backtracking)

Для малых графов (примерно до 18 вершин) калькулятор может найти истинное хроматическое число, проверяя k = 2, 3, 4, ... и пытаясь раскрасить граф методом поиска в глубину с возвратом. Когда точный алгоритм успешно завершается, результат помечается как «Точный».

Форматы ввода

Список ребер

Запишите каждое ребро как две метки вершин, разделенные дефисом, пробелом или стрелкой. Разделяйте ребра запятыми или новыми строками. Метки могут содержать буквы, цифры или подчеркивания. Пример:

Список смежности

Запишите вершину, двоеточие и список ее соседей через запятую. Пример:

Петли (ребра из вершины в саму себя) не учитываются, так как вершина не может иметь цвет, отличный от своего. Дубликаты ребер удаляются автоматически, граф считается неориентированным.

Как пользоваться калькулятором

1. Выберите формат: Переключайтесь между списком ребер и списком смежности с помощью кнопок.
2. Введите граф: Вставьте свои данные или нажмите на один из примеров (треугольник, клика K₅, колесо, двудольный граф K₃,₃, расписание).
3. Выберите алгоритм: Оставьте «Авто» для лучшего результата или выберите конкретный метод.
4. Нажмите «Раскрасить граф»: Ниже появятся хроматическое число, список цветов, интерактивный SVG и пошаговая анимация.
5. Исследуйте: Используйте «Пуск» для просмотра анимации, перетаскивайте узлы для удобства обзора и используйте кнопки «Назад» / «Вперед» для ручного разбора.

Практическое применение раскраски графов

Расписание экзаменов

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

Распределение радиочастот

Передатчики, находящиеся в зоне взаимных помех, должны вещать на разных частотах. Хроматическое число графа помех — это минимальное количество необходимых частот.

Распределение регистров

В компиляторах временные интервалы жизни переменных — это вершины; если интервалы пересекаются, между ними есть ребро. k-раскраска позволяет назначить переменные k регистрам процессора без коллизий.

Картография

Страны, имеющие общую границу, должны быть раскрашены в разные цвета. Теорема о четырех красках (Аппель-Хакен, 1976) доказывает, что четырех цветов всегда достаточно для любой плоской карты.

Судоку и головоломки

Решенное судоку — это 9-раскраска графа, вершины которого — 81 ячейка, а ребра соединяют ячейки в одной строке, столбце или блоке 3×3. Раскраска графов лежит в основе многих задач на удовлетворение ограничений.

Интересные частные случаи

• Полный граф K_n: χ(K_n) = n. Все вершины соединены друг с другом, поэтому все цвета должны быть разными.
• Цикл C_n: χ(C_n) = 2, если n четное; 3, если n нечетное.
• Дерево: Любое дерево с ≥ 2 вершинами имеет χ = 2 (деревья двудольны).
• Двудольный граф: χ = 2, если в графе есть хотя бы одно ребро.
• Граф Петерсена: Знаменитый 3-регулярный граф с χ = 3.
• Колесо W_n: Центральная вершина, соединенная с циклом длины n. χ = 3, если n четное; 4, если n нечетное.

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

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

Хроматическое число χ(G) — это минимальное количество цветов, необходимых для раскраски вершин графа так, чтобы никакие две смежные вершины не имели одинаковый цвет. Двудольные графы имеют хроматическое число не более 2; любой граф, содержащий треугольник, имеет хроматическое число не менее 3; согласно теореме Брукса, оно не превышает максимальную степень, за исключением полных графов и нечетных циклов.

Какой алгоритм использует этот калькулятор?

Для малых графов калькулятор запускает точный поиск с возвратом. Для больших графов используется эвристика DSATUR, которая последовательно раскрашивает вершины с наибольшей «насыщенностью» цветами соседей. Также доступны алгоритм Уэлша-Пауэлла и жадный алгоритм.

Как мне ввести свой граф?

Используйте режим списка ребер для ввода по одному ребру на строку (A-B) или через запятую. Используйте список смежности для формата «вершина: соседи» (A: B, C). Самопетли не допускаются.

Почему DSATUR не всегда находит истинное хроматическое число?

Задача раскраски NP-трудна, поэтому быстрых универсальных алгоритмов для нее не существует. DSATUR — отличная эвристика и часто дает точный результат, но на специально сконструированных графах может ошибаться. Калькулятор также выводит нижнюю границу (кликовое число), чтобы вы могли оценить точность.

Где применяется раскраска в реальной жизни?

Моделирование расписаний, назначение радиочастот, распределение регистров в процессорах, раскраска карт, решение судоку и оптимизация задач с конфликтующими ресурсами.

Всегда ли хроматическое число равно размеру максимальной клики?

Нет. Размер клики ω(G) — это нижняя граница. Они равны для совершенных графов (деревья, двудольные, интервальные). В общем случае χ(G) может быть гораздо больше ω(G), как в графах Мычельского.

Граф какого размера может обработать калькулятор?

Поддерживается до 60 вершин и 600 ребер. Для точного алгоритма лимит составляет около 18 вершин из-за высокой вычислительной сложности поиска с возвратом. Этого достаточно для большинства учебных и прикладных задач.

Дополнительная литература

• Раскраска графов — Википедия
• Алгоритм DSATUR — Википедия (англ.)
• Хроматический многочлен — Википедия
• Проблема четырех красок — Википедия
• Теорема Брукса — Википедия

Продвинутые математические операции:

• Антилогарифмический Калькулятор
• Калькулятор бета-функции
• Калькулятор биномиального коэффициента
• Калькулятор биномиального распределения
• Побитовый калькулятор Рекомендуемое
• Калькулятор центральной предельной теоремы
• Комбинированный калькулятор
• Калькулятор дополнительной функции ошибки
• Калькулятор комплексных чисел Рекомендуемое
• Калькулятор Энтропии
• Калькулятор функции ошибки
• Калькулятор экспоненциального распада
• Калькулятор экспоненциального роста: высокая точность
• Калькулятор экспоненциального интеграла
• калькулятор-показателей-высокая-точность
• Калькулятор факториала
• Калькулятор гамма-функции
• Калькулятор золотого сечения
• Калькулятор полураспада
• Калькулятор процентного роста
• Калькулятор перестановок
• Калькулятор распределения Пуассона
• Калькулятор корней многочленов с подробными шагами
• Калькулятор вероятности
• Калькулятор распределения вероятностей
• Калькулятор пропорций
• Калькулятор квадратичных формул
• Научный Калькулятор
• Калькулятор экспоненциальной записи
• Калькулятор значащих цифр Новый
• Калькулятор суммы кубов
• Калькулятор суммы последовательных чисел
• Калькулятор суммы квадратов
• Генератор таблицы истинности
• Калькулятор теории множеств
• Генератор диаграммы Венна (3 множества)
• Калькулятор китайской теоремы об остатках
• Калькулятор функции Эйлера
• Калькулятор расширенного алгоритма Евклида
• Калькулятор модулярного мультипликативного обратного
• Калькулятор цепных дробей
• Калькулятор кратчайшего пути Дейкстры
• Калькулятор минимального остовного дерева
• Валидатор последовательности степеней графа
• Калькулятор беспорядков (субфакториал)
• Калькулятор чисел Стирлинга
• Калькулятор принципа голубятни
• Калькулятор стационарного распределения цепи Маркова
• Калькулятор округления Новый
• Калькулятор отрицательного биномиального распределения Новый
• Калькулятор перестановок с повторениями Новый
• Калькулятор Модульного Возведения в Степень Новый
• Калькулятор первообразного корня
• Упроститель Булевой Алгебры Новый
• Решатель Карты Карно (K-Map) Новый
• Калькулятор раскраски графов Новый
• Калькулятор топологической сортировки Новый
• Калькулятор матрицы смежности Новый
• Калькулятор формулы включений-исключений Новый
• Решатель Линейного Программирования Новый
• Решатель задачи коммивояжёра (TSP) Новый
• Проверка Гамильтонова Пути Новый
• Проверка планарного графа Новый
• Калькулятор сетевого потока (Максимальный поток) Новый
• Решатель задачи о стабильных браках Новый
• Калькулятор Порядка в Теории Групп Новый
• Калькулятор Колец и Полей Новый