Независимые множества

 

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

Множество вершин U графа G = (V,X) называется независимым (внутренне устойчивым), если никакие две вершины из этого множества не смежны. Другими словами, если U ÍV и U независимо в графе G, то порожденный подграф G(U) является пустым. Очевидно, что если при этом U*Í U, то U* - также независимое множество.

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

Наибольшее по мощности независимое множество называется наибольшим.

Ясно, что наибольшее независимое множество является максимальным. Обратное, вообще говоря, неверно.

Число вершин в наибольшем независимом множестве графа G называется числом независимости (или числом внутренней устойчивости) этого графа и обозначается a(G).

2

1 3 7

5 4 6

Рис. 1.

 

Например, для графа G, изображенного на рис.1., a(G)=4, множества вершин {1,2,3,7}, {1,2,3,8}, {2,3,5,7}, {2,3,5,8} являются наибольшими независимыми, а {4,7} – максимальное независимое множество, не являющееся наибольшим.

 

Понятие внутренней устойчивости естественным образом переносятся и на случай ориентированного графа.

 

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

Очевидный алгоритм, который можно применить для нахождения независимых множеств вершин, это «полный перебор всех возможностей»: генерируем все возможные подмножества вершин заданного графа или орграфа и проверяем, является ли оно независимым. Среди всех независимых множеств выбираем максимальные. Опишем теперь общий метод, позволяющий значительно сократить число шагов в алгоритмах полного перебора всех возможностей. Чтобы применить этот метод, представим искомое решение в виде последовательности <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).

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

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

Пусть 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)).

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

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

 

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

 

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

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

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

 

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

 

Рис. 3.

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

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

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

1. V₁ = X,

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

 

 

 

Рис. 4

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

 

ЗАДАНИЕ 20. Найти все максимальные паросочетания в заданном графе, используя алгоритм с возвратом для нахождения независимых множеств вершин реберного графа.

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