Построение цветных графов без проверки на изоморфизм

В работе рассматриваются графы, вершины или ребра которых раскрашены в заданное количество цветов — вершинные и реберные раскраски. Изучение раскрасок графов началось с середины XIX в., однако основное внимание уделяется правильным раскраскам, в которых накладывается ограничение, что цвета смежных вершин или ребер должны быть различными. В данной работе рассматриваются раскраски графов без каких-либо ограничений. Исследуется задача генерации всех неизоморфных вершинных и реберных $k$-раскрасок заданного графа без непосредственной проверки на изоморфизм. Задача о нахождении неизоморфных реберных $k$-раскрасок сводится к задаче построения всех вершинных $k$-раскрасок графа. В основе методов генерации графов без непосредственной проверки на изоморфизм лежит метод канонических представителей. Идея метода состоит в том, что предлагается способ кодирования графов и выбирается некоторое правило, по которому из всех изоморфных графов один граф объявляется каноническим. Строятся все коды и из них оставляются только канонические. Часто в качестве канонического выбирается представитель с наибольшим или наименьшим кодом. На практике порождение всех кодов требует больших вычислительных ресурсов, поэтому используются различные методы оптимизации перебора. В работе предлагаются два алгоритма решения задачи генерации вершинных $k$-раскрасок без проверки на изоморфизм методом МакКея и методом Рида – Фараджева. Производится сравнение разработанных алгоритмов генерации раскрасок на двух классах графов — цепях и циклах. Вычислительные эксперименты показывают, что для цепей и циклов алгоритм, построенный на основе метода Рида – Фараджева, работает быстрее.