Алгоритм с возвратом

Очевидный алгоритм, который можно применить для нахождения независимых множеств вершин, это «полный перебор всех возможностей»: генерируем все возможные подмножества вершин заданного графа или орграфа и проверяем, является ли оно независимым. Среди всех независимых множеств выбираем максимальные. Опишем теперь общий метод, позволяющий значительно сократить число шагов в алгоритмах полного перебора всех возможностей. Чтобы применить этот метод, представим искомое решение в виде последовательности <x₁,…x _n>. Основная идея метода состоит в том, что решение строится последовательно, начиная с пустой последовательности ε (длины 0). Вообще, имея данное частичное решение <x₁,…x _k>, мы стараемся найти такое допустимое значение x _k+1, относительно которого мы не можем сразу сказать, что <x₁,…x _k, x _k+1> можно расширить до некоторого решения (либо <x₁,…x _k, x _k+1> уже является решением). Если такое предполагаемое, но еще не использованное значение x _k+1 существует, то мы добавляем его к нашему частичному решению и продолжаем процесс для последовательности <x₁,…x _k, x _k+1>. Если его не существует, то мы возвращаемся к нашему частичному решению <x₁,…x _k-1> и продолжаем процесс, отыскивая новое, еще не использованное допустимое значение x_k – отсюда название «алгоритм с возвратом» (англ.: backtracking).

2. Раскраска графа

Задачи раскраски вершин или ребер графа занимают важное место в теории графов. К построению раскрасок сводится целый ряд практических задач. Характерной особенностью этих задач является существование объектов, которые по каким-либо причинам не могут быть объединены в одну группу.

Пусть G – некоторый граф, k – натуральное число. Произвольная функция вида f: V → {1,2,…,k} называется вершинной k-раскраской или просто k-раскраской графа G.

Раскраска называется правильной, если f(v)≠f(u) для любых смежных вершин v и u. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым.

Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом этого графа и обозначается χ (G). Если χ (G)=k, то граф называется k-хроматическим. Правильная k-раскраска графа при k =χ (G) называется минимальной.

Алгоритм раскрашивания графов

1. Выберем в графе G некоторое максимальное независимое множество вершин U (лучше наибольшее). Покрасим все вершины данного множества в один цвет.

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

3. Шаг 2 повторять до тех пор, пока в графе G не будут раскрашены все вершины.

Реберной k-раскраской графа G называется функция φ, ставящая в соответствие каждому его ребру x число φ(x) из множества {1,2,…,k}. Реберная окраска называется правильной, если смежные ребра имеют разные цвета. Граф, допускающий правильную реберную k-раскраску, называется реберно k-раскрашиваемым. Минимальное число k, при котором граф G является реберно k-раскрашиваемым, называется хроматическим классом (хроматическим индексом или реберным хроматическим числом) графа G и обозначается через χ ‘(G). Если χ ‘(G)=k, то граф называется реберно k-хроматическим.

Независимые множества ребер графа G находятся во взаимно однозначном соответствии с независимыми множествами вершин реберного графа L(G)=(V₁,X₁), который для графа G=(V,X) определяется следующими двумя условиями:

1. V₁ = X,

2. вершины х₁ и х₂ смежны в L(G) тогда и только тогда, когда ребра х₁ и х₂ смежны в G.

На рис. 2 изображены два графа – G и L(G). Вершины графа G – темные кружки, вершины графа L(G) – светлые кружки. Ребра графа G – тонкие линии, ребра графа L(G) – жирные линии.

Рис. 2

Поскольку ребра любого графа G смежны тогда, когда смежны соответствующие вершины реберного графа L(G) (правило построения реберного графа смотри ниже), то χ ‘(G) можно определить как хроматическое число графа L(G), т.е. χ ‘(G)=χ (L(G)).