Где применяется раскраска графов в реальном мире?

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

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

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

⚡ Попробуйте пример:

4-цикл C₄ Треугольник K₃ Полный граф K₅ Пятиугольник C₅ Колесо W₆ Двудольный K₃,₃ Пример смежности Расписание экзаменов

Формат ввода

⬌ Список ребер

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

Данные графа

Формат ребер: A-B или A B, через запятую или с новой строки. Макс. 60 вершин и 600 ребер.

Формат смежности: A: B, C, D — одна вершина на строку, затем ее соседи.

Алгоритм

Авто выбирает точный поиск для малых графов и DSATUR для больших.

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

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

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

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

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

Определение хроматического числа

χ(G) = min { k : G допускает правильную k-раскраску }

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

Тривиальные границы: 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, ... и пытаясь раскрасить граф методом поиска в глубину с возвратом. Когда точный алгоритм успешно завершается, результат помечается как «Точный».

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

Список ребер

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

A-B, B-C, C-D, D-A
A-C

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

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

A: B, C, D
B: A, D
C: A
D: A, B

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

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

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

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

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

Каждый экзамен — это вершина. Ребро проводится между экзаменами, на которые записан хотя бы один общий студент. Правильная раскраска в 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 вершин из-за высокой вычислительной сложности поиска с возвратом. Этого достаточно для большинства учебных и прикладных задач.

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

Ссылайтесь на этот контент, страницу или инструмент так:

"Калькулятор раскраски графов" на сайте https://ru.miniWebtool.com/калькулятор-раскраски-графов/ от MiniWebtool, https://MiniWebtool.com/

от команды miniwebtool. Обновлено: 20 апр. 2026 г.

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.