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

Задача о нахождении независимого множества размерности k явл. NP-полной. К ней сводится задача «Клика».

Алгоритм полного перебора. Зафиксируем вершину aV(G),

G₁ = G- a; G₂ = G – N(a) //окружение

Тогда Утв. (G) = max( (G₁), (G₂) ). //а – число независимости

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

Док-во следует из вашего рисунка. Жене было в лом рисовать его

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

1.Только удалять специально выбранные вершины до тех пор, пока не останется пустой граф (выбирать вершины наиб. степ.)

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

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