Точное хроматическое число малого графа
Найти минимальное число цветов для простого графа до 8 вершин и предъявить допустимую раскраску, перебирая ограниченное число состояний.
Ваш пример
Разбор примера
Хроматическое число = 3
- Для каждого меньшего числа цветов поиск завершился без раскраски.
- Предъявленная раскраска проверяет верхнюю границу.
Метод и условия расчёта
Проверяем возможность раскраски последовательно в 1,2,… цветов.
Соседние вершины обязаны иметь разные цвета; имена цветов сами по себе не значат ничего.
Теория к методу
Любая корректная раскраска даёт верхнюю границу хроматического числа. Чтобы утверждать минимальность, нужно дополнительно исключить все меньшие числа цветов. В малом графе это можно сделать полным поиском с проверкой соседства и явным пределом вычислений.
Каждой вершине присваивается один цвет, а концы любого ребра должны иметь разные цвета. Цветовые номера являются только метками: глобальная перестановка номеров не меняет раскраску. Поэтому поиск может вводить новые цвета последовательно, не перебирая все переименования одного и того же решения. Это сокращает работу без потери существенно разных назначений.
Пример: В треугольнике каждая пара вершин соединена. Два цвета невозможны: третья вершина соседствует с обеими уже разными. Три различных цвета дают корректную раскраску.
Здесь есть и нижняя, и верхняя граница три. Для цикла из пяти вершин нижняя граница два не достигается из-за нечётности, но три цвета также достаточны.
Вопросы по теме
Жадная раскраска всегда минимальна?
Нет. Здесь минимальность получается отказами полного ограниченного поиска для всех меньших чисел цветов.
Что при достижении лимита поиска?
Возвращается ошибка ограничения вычислений. Промежуточная верхняя граница не выдаётся за точное хроматическое число.
Графы и маршруты: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.