Алгоритм кратчайшей раскраски графа

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

Условие оптимальности раскрашивания - использование минимального числа красок φ - хроматического числа графа.

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

Конечная грань - это внутренняя область плоскости, ограниченная
ребрами в плоском изображении графа. .

Теорема 3.5.1. Для плоских графов φ<4.

Пример 4.5.1. Рассмотрим граф G изображенный на рис.4.5.1, и произведем раскраску этого графа. φ=3 (0,1,2)

φ=3 (0,1,2)

Рис.4.5.1

Алгоритм граничного перебора построения максимальных внутренне устойчивых вершин графа(построение множества всех несмежных вершин графа).

0. Текущее множество Y={X1}, i=0.

1. Находим наибольший номер j, такой, что XjÎY :

a). Если j ¹ n и i = 0 переходим в п.3 (n – количество вершин графа).

b). Если j ¹ n и i ¹0 переходим в п.2.

c). Если j = n, то удаляем из множества Y вершину Xn: Y=Y/{Xn}//(множ.Y без вершины Xn):

если при этом Y¹Æ, то переходим в п.1,

иначе, если Y=Æ – переходим в п.6.

2. Удаляем элемент Xj из множества Y и проверяем:

если Y=Æ, то j=j+1, вводим в Y элемент Xj и переходим в п.3,

иначе, если Y¹Æ – переходим в п.3 (ничего не выполняя).

3. j=j+1. Если j > n, то переходим в п.4,

иначе проверяем на смежность вершины Xj со всеми вершинами множества Y. Если хотя бы для одного элемента Xl множества Y (XlÎY) вершины (Xj, Xl) смежные, выполняем п.3, иначе добавляем элемент Xj в множество Y и переходим в п.3.

4. Если i=0, то переходим в п.5,

иначе, если i¹0, проверяем на поглощение множество Y: Y£Ys (1 £ s £ i).

Если Ys поглощает Y, то переходим в п.1, иначе переходим в п.5.

5. i=i+1, Yi=Y. Переходим в п.1 (Yi – очередное построенное подмножество максимальных внутренне устойчивых вершин графа).

6. Построение всех Ys (1 £ s £ i), максимально внутренне устойчивых множеств закончено.

Алгоритм кратчайшей раскраски графа (словесное описание):

1. Методом граничного перебора строятся все максимальные внутренне устойчивые множества вершин графа (множество несмежных вершин).

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

3. Решается задача построения одного кратчайшего покрытия (например, методом минимального столбца максимальной строки).

4. Вершины принадлежащие каждому подмножеству вошедшему в найденное кратчайшее покрытие окрашиваются 1-й краской. Если некоторая вершина принадлежит нескольким вошедшим в покрытие подмножествам, то она в одном остается, из других исключается.

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

Несмежные вершины выбраны в таблице единицами. Далее решается задача построения одного кратчайшего покрытия (методом минимального столбца максимальной строки). Вершины, принадлежащие каждому подмножеству, вошедшему в найденное кратчайшее покрытие, окрашиваются одной краской. Если некоторая вершина принадлежит нескольким вошедшим в покрытие подмножествам, то она в одном остаётся, из остальных исключается. Для нашего примера получим два подмножества: Y₁, Y₂, Y₃. Таким образом, получим три краски 0,1,2 соответственно. И действительно (как показано на рис, 4.5.1): если х₁, покрасить краской 0, то все смежные с ней вершины
х₂, х₃, х₄, х₅ нельзя покрасить 0. х₂, х₄ - смежные, для них необходимо две разные краски
(1 и 2), х₃, х₄ - аналогично. Таким образом, изображенная на примере раскраска -
минимальна.

Алгоритмы нахождения подграфов

Циклом называется замкнутый маршрут в неориентированном графе. Для ориентированного графа определяется аналогично понятие контур - замкнутый путь.

Пример 3.3.1

Рассмотрим граф (рис.3.3.1,а), в котором каждому ребру присвоен свой номер. В графе можно выделить соответствующее ему число циклов. Для нашего примера циклами С_i являются замкнутые маршруты, образованные ребрами (рис.3.3.1,б): С₁ = {1,2,5,4}, C₂ = {5,6,7}, С₃ = {3,6,2}, С₄ = {1,2,6,7,4}.Среди этих циклов найдутся такие, которые включают в себя другие циклы. Так, цикл С₄ состоит из циклов C₁ и C₂, у которых имеется общее ребро 5, не вошедшее в цикл 4. Говорят, что цикл 4 получен линейной комбинацией циклов 1 и 2, т.е. является линейно зависимым от них.

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

Присвоим каждому ребру графа номер j, j = 1,m и поставим в соответствие каждому циклу C_i, двоичный m–разрядный ве­ктор V_i, компоненты v_ij которого определяются следующим об­разом: V_j = 0, если ребро j не входит в цикл С_i, V_j = 1 – в противном случае.

Тогда линейной комбинацией векторов V, является результат векторной операции сложения по модулю двух этих векторов.

Для рассмотренного выше примера имеем:

Поскольку V_i отношение принадлежности ребер графа циклу C_i, a C_i – это множество ребер, то в результате применения векторной операции Å получаем совокупность ребер, входящих в циклы, составляющих линейную комбинацию, за исключением общих для этих циклов ребер; на языке теории множеств это означает
объединение множеств C_i, без их пересечения, что соответствует операции
«симметрическая разность» для множеств.

В нашем примере общим является ребро 5, которое исключено из цикла 4.
Линейно независимым от совокупности других циклов называется цикл, который не может быть построен линейной комбинацией этих циклов.

Максимальное множество линейно независимых циклов образует систему независимых циклов, мощность g этого множества называется цикломатическим числом.