logo search
shpori (1) / shpori (1)

28.Задача о раскраске графа, точные и эвристические алгоритмы ее решения.

Алгоритм полного перебора

Определим операцию слияния 2-х вершин (a и f). G/{a,f}.

Граф G разбиваем на 2 графа по правилу:

Зафиксируем 2 несмежные вершины x,y из V(G)

G1 = G + xy, G2 = G/{x,y}

Утв. Χ(хи)(G) = min{X(G1), X(G2)}

Док-во: α – множество правильных раскрасок. Разделим α на два подмножества: 1) α(x) ≠ α(y), если добавим ребро xy, то α – правильная раскраска G1 ; 2) α(x) = α(y), сольем x и y, α – правильная раскраска в G2

Этот алгоритм экспоненциальный.

Улучшение

Пусть a,b из V(G). Будем говорить, что b несмежно поглощает a, если ab не принадлежит E(G) и N(a)€N(b).

Утв. Если вершина a несмежно поглощается какой-то вершиной, то X(G) = X(G-a).

Док-во: Пусть b поглощает a, α – правильная раскраска G-a. Положим α(a) = α(b) => любую раскраску графа G-a можно превратить в раскраску G.

Следствие. Задача о раскраске полиноминально разрешима в классе графов дополнительных к хордальным.

Эвристические алгоритмы

  1. Алгоритм DSATUR

Степень насыщения вершины v – число различных цветов, в которые окрашены соседи v.

while(не все вершины покрашены)

{

Выбирать неокрашенную вершину v с наибольшей степенью насыщения;

Если таких вершин несколько, то выбрать ту из них, степень которой максимальна;

Покрасить v в минимальный возможный цвет;

}

  1. Алгоритм GIS(жадное независимое множество)

Каждый шаг ищем независимое множество и красим эти вершины в один цвет. Затем удаляем эти вершины и снова ищем не зависимое множество.

c = 1;

while(не все вершины покрашены)

{

available = множество всех неокрашенных вершин

while(available ≠ пусто)

{

В графе порожденном вершинами из множества available выбрать вершину v минимальной степени;

Покрасить v в цвет c;

Удалить {v}U(объединение) N(v) из available;

с++;

}

}

29. Задача о вершинном покрытии, точные и эвристические алгоритмы ее решения.

x:=;

while (ребро ав такое, что {а,в}x=)

x:=х{а,в};

return x;

Th. Алгоритм имеет гарантир оценку точности 2.

Док-во: Пусть ,’- размер верш. покрытия, найденного алгоритмом. Пусть у алгоритма было к инстарий,на которых рассматр. ребра а1в1,...,аквк.

’=2к.

Ребра а1в1,...,аквк образуют паросочетание

а1............ ак

| |

в1............ вк

чтобы их покрыть надо min к вершин .

30. Задача о независимом множестве в классе хордальных графов.

Граф наз-ся хордальным, если он не содержит порожденных простых циклов длины ≥4.

Для любого простого цикла длины ≥ 4 имеется хорда, т.е. ребро, соединяющее две вершины цикла, но не принадлежащее циклу.

a, b V(G). Будем говорить, что b поглощает a, если abE(G) и N(a)\{b} явл-ся подмн-ом N(b)

Теорема. У любого непустого хордального графа есть поглощающая вершина.

Док-во. Пусть G – непустой граф, у которого нет поглощающей вершины. Докажем, что тогда G – не хордальный. Пусть P = x1, x2, …, xk – самый длинный в графе G путь без хорд, k 2. Т.к. xk-1 не поглощает xk, то сущ-т вершина y, смежная с xk, но не смежная с xk-1, у не совпадает не скакой вершиной xi , i = 1,…,k ,y P, т.к. иначе ребjhjро xky было хордой. Длина пути x1, x2, …, xk, у равна k+1 => у него должна быть хорда вида yxj. Пусть i – макс.индекс такой, что уxi - является хордой. По построению i <= k-2. Получаем цикл => исходный граф не хордальный - противоречие

Следствие. Задача «независимое мн-во» польномиально разрешима в классе хордальных графов.

Алгоритм.

Вход: хордальный граф G.

H:=G

while(E(H)≠0){найти в H поглощающую вершину v; H:=H-v;}

return |V(H)|