Алгоритм раскраски графа с перекраской двуцветных компонент
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ми цвета . Поскольку , можно перекрасить в цвет , поэтому в новой раскраске вершины и будут в разных компонентах, что противоречит свойству 2.
Таким образом, является путем из вершины в вершину .
Свойство 4. и не имеют общих вершин, за исключением .
Пусть - общая вершина и . Тогда раскрашена в цвет и смежна по крайней мере с двумя вершинами цвета и двумя вершинами цвета . Так как , существует цветв который можно перекрасить . Но это разделит вершины и , что противоречит свойству 2.
Продолжим доказательство теоремы. Установим теперь противоречие со свойством4.
Поскольку - не полный граф на вершине, существуют две несмежные вершины, например и . Путь содержит вершину , смежную с вершиной . Допустим, что мы поменяли местами цвета 1 и 3 в пути (который присутствует, поскольку ), в результате чего в новой раскраске вершина получает цвет 3, а вершина - цвет 1. Но тогда новые компоненты а и содержат общую вершину , что противоречит свойству 4.
Это завершает доказательство теоремы.
Алгоритм с перекраской двуцветных компонент
Задача о минимальной раскраске графа, как было сказано выше, является NP - трудной[2], поэтому большой интерес представляют полиномиальные алгоритмы, решающие задачу приближенно. Одним из таких алгоритмов является алгоритм раскраски вершин графа с перекраской двуцветных компонент[3].
Основная идея этого алгоритма состоит в том, что вершины упорядочиваются произвольным образом и при раскраске очередной вершины графа G анализируется окрестность этой вершины.
Допустим, что подграф , порожденный вершинами , , … , окрашен цветами. Тогда, если в окрестности отсутствует один из цветов, то этот цвет приписываем . В противном случае, если в окрестности вершины не содержится клика мощности , возможна перекраска графа , такая, что на раскраску окрестности будет израсходовано менее чем цветов
Приведем псевдокод данного алгоритма.
Вход: Граф G с ПН - упорядоченными вершинами.
Выход: Субоптимальная раскраска вершин.
начало
1.;
.для от до шаг 1 цикл
.начало
4.m:= наименьший номер цвета, отсутствующего на вершинах, смежных с вершиной;
.если m<=j то
.окрасить вершину в цвет ;
.иначе начало
.К:= множество цветов, представленных ровно один раз на вершинах, смежных с вершиной ;
.Если найдется пара , такая, что вершины и , смежные с, и окрашенные в цвета , не соединены двуцветной цепью то
.начало
.перекрасить ту компоненту двуцветного графа , которая содержит вершину ;
.окрасить вершину в цвет ;
.конец
.иначеначало
15.;
.окрасить вершину в цвет ;
.конец
.конец
.конец цикла;
конец
Поясним некоторые термины, которые встречаются в алгоритме:
Двуцветная цепь - это цепь графаG, которая окрашена только в два цвета. Двуцветная компонента - это подграф графа G, который окрашен только в два цвета.
Рассмотрим работу данного алгоритма на примере.
Основные обозначения:
Вершины -
Цвета -
m - наименьший номер цвета, отсутствующего на вершинах, смежных с вершиной
Рисунок 2
1 шаг:
j = 1;
i = 1;
m=1;
Проверяем условие . Оно выполняется, поэтому мы окрашиваем вершину в цвет .
Переходим на следующую вершину.
шаг:
j = 1;
i = 2;
m=1;
Проверяем условие . Оно выполняется, поэтому мы окрашиваем вершину в цвет .
Переходим на 3-ю вершину.
шаг:
j = 1;
i = 3;
m=2;
Проверяем условие :. Оно не выполняется. Запишем множество цветовK={}. Это множество состоит из одного цвета, то есть, у нас нет пары .Поэтому мы данную вершину окрашиваем в минимальный свободный цвет, отсутствующий на соседних вершинах,:
Рисунок 3
шаг:
j = 2;
i = 4;
m=3;
Проверяем условие :. Оно не выполняется. Запишем множество K={}. Ищем пару , такую, что вершины и смежные и окрашенные в цвета , не соединены двуцветной цепью. Берем вершины и и рассмотрим эту пару. Она не соединена двуцветной цепью. По алгоритму, вершину окрашиваем в цвет вершины , то есть в . А вершину перекрашиваем в цвет .
Рисунок 4
5 шаг:
j = 2;
i = 5;
m=3;
Проверяем условие :. Оно не выполняется. Запишем множество . Ищем пару , такую, что вершины и смежные с и окрашенные в цвета , не соединены двуцветной цепью.Берем вершины и , которые окрашены в цвета и соответственно. Они соединены двуцветной цепью {}. Следовательно, и вершину окашиваем в цвет .
Рисунок 5
Граф окрашен.
Известно, что данный алгоритм раскраски вершин графа с перекраской двуцветных компонент, примененный для раскраски вершин графа с максимальной степенью вершин , гарантирует раскрашивание этого графа, при условии, что не содержит в качестве связных компонент и простых нечетных циклов при .
Существенным недостатком здесь является то, что , может быть намного меньше . Отметим, однако, что при , указанный алгоритм дает минимальную раскраску .
Действительно, пусть . Проверка того, является ли 2-раскрашиваемым, требует шагов, где - соответственно число вершин, ребер графа. Если - не двудольный, алгоритм находит минимальную раскраску этого графа за линейное от n число шагов.
Гэри, Джонсон и Стокмейер [2]доказали, что при даже проверка на 3-раскрашиваемоеть плоского графа является NP -полной задачей.
Рассмотрим теперь случай, когда алгоритм раскраски вершин графа с перекраской двухцветн