Эскизный проект. 
Прикладная программа. 
Раскраска графа

Переборный алгоритм раскраски

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

Выберем в данном графе G две несмежные вершины и и построим два новых графа:, получающийся добавлением ребра к графу G, и, получающийся из G слиянием вершин x и y. Операция слияния состоит в удалении вершин x и y и добавлении новой вершины z и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин x, y. На рис. 2 показаны графы и, получающиеся из графа G, изображенного на рис. 1, с помощью этих операций, если в качестве x и y взять вершины a и .

Рис. 2.

Если в правильной раскраске графа G вершины x и y имеют разные цвета, то она будет правильной и для графа. Если же цвета вершин x и y в раскраске графа G одинаковы, то граф можно раскрасить в то же число цветов: новая вершина z окрашивается в тот цвет, в который окрашены вершины x и y, а все остальные вершины сохраняют те цвета, которые они имели в графе G. И наоборот, раскраска каждого из графов, , очевидно, дает раскраску графа G в то же число цветов. Поэтому, что дает возможность рекурсивного нахождения раскраски графа в минимальное число цветов. Заметим, что граф имеет столько же вершин, сколько исходный граф, но у него больше ребер. Поэтому рекурсия, в конечном счете, приводит к полным графам, для которых задача о раскраске решается тривиально.