Раскраска графа

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

Пусть 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) (правило построения реберного графа смотри ниже), то χ ‘(G) можно определить как хроматическое число графа L(G), т.е. χ ‘(G)=χ (L(G)).

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

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

11. Найти хроматическое число заданного графа, используя алгоритм Магу для нахождения независимых множеств, указать, какие вершины в какой цвет окрашиваются.

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

7. Паросочетания

Не менее важным, чем понятие вершинной независимости, является понятие реберной независимости.

Произвольное подмножество попарно несмежных ребер графа называется паросочетанием ( или независимым множеством ребер).

В качестве иллюстрации рассмотрим граф, изображенный на рис.2. В нем паросочетаниями являются, например, х₁,х₃,х₅,х₇, х₁, х₂, х₂,х₆.

х₁ х₂ х₃ х₄ х₅ х₆ х₇

Рис. 2.

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

Число ребер в наибольшем паросочетании графа G называется числом паросочетания и обозначается ₁(G).

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

1. V₁ = X,

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

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

Рис. 3

13. Найти все максимальные паросочетания в заданном графе, используя алгоритм с возвратом для нахождения независимых множеств.

14. Найти все максимальные паросочетания в заданном графе, используя алгоритм Магу для нахождения независимых множеств.

15. Найти наибольшее паросочетание в заданном графе, используя алгоритм с возвратом для нахождения независимых множеств.

16. Найти наибольшее паросочетание в заданном графе, используя алгоритм Магу для нахождения независимых множеств.