Алгоритм поиска минимального хроматического разложения графа и его практическое применение

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

Задача раскраски произвольного графа минимальным количеством цветов принадлежит классу задач, которые называются NP-сложными задачами [1, с 133].

Алгоритм последовательной раскраски включает действия:

Первой вершине из списка SV приписывается цвет 1.

Следующей в списке SV вершине приписывается минимальный цвет, не использованный при раскраске вершин из ее окружения.

Шаг 2 повторяется до исчерпания списка вершин.

Идея алгоритма заключается в многократном применении процедуры последовательной раскраски с модификацией списка SV на каждой итерации. В результате получается новый список SV, при этом трудные для распределения вершины окажутся в начале списка, к модифицированному списку вновь применяется процедура раскраски и т.д. Работа алгоритма заканчивается при выполнении условий остановки [1, с 136].

Блок-схема рассмотренного алгоритма представлена на рисунке 3.

Рис. 3. Алгоритм поиска минимального хроматического разложения графа

Заключение

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

Литература

1. Новиков Ф.А. Дискретная математика. Учебник для вузов. – СПб. Питер, 2011. – 133-136с.