Tekst źródłowy strony Problem zbioru niezależnego

'''Problem zbioru niezależnego''' – przykład [[problem NP-zupełny|problemu NP-zupełnego]] z [[teoria grafów|teorii grafów]].

== Opis ==
Dla danego grafu ''G'', ''[[zbiór niezależny]]'' to zbiór wierzchołków niepołączonych żadnymi krawędziami. Innymi słowy, [[podgraf]] indukowany przez ten zbiór nie ma żadnych krawędzi, a jedynie izolowane wierzchołki. Problem zbioru niezależnego to pytanie czy dla danego grafu ''G'' i liczby ''k'', istnieje w ''G'' zbiór niezależny o ''k'' wierzchołkach. Odpowiadający mu problem optymalizacyjny to '''problem największego zbioru niezależnego''', polegający na znalezieniu zbioru niezależnego o największej liczbie wierzchołków. Mając rozwiązanie dla problemu decyzyjnego, można za pomocą [[wyszukiwanie binarne|wyszukiwania binarnego]] rozwiązać również problem optymalizacyjny, używając O(log ''|V|'') razy tamtego rozwiązania. Problem ten nie posiada [[algorytm aproksymacyjny|aproksymacji]] z czynnikiem stałym jeśli P≠NP.

== Dowód NP-zupełności ==

Łatwo stwierdzić, że problem ten należy do klasy [[problem NP|NP]], ponieważ mając podany zbiór wierzchołków możemy w czasie liniowym sprawdzić czy nie ma pomiędzy nimi żadnej krawędzi. Aby pokazać, że jest to [[problem NP-trudny]], możemy pokazać redukcję [[problem spełnialności|problemu spełnialności]] formuł logicznych (SAT) do niego.

Pierwszym krokiem jest przekształcenie formuły do [[koniunkcyjna postać normalna|postaci koniunkcyjnej]] (CNF). W tej postaci:
* formuła jest [[koniunkcja (matematyka)|koniunkcją]] (''i'') klauzul
* każda klauzula jest [[alternatywa|alternatywą]] (''lub'') literałów
* każdy literał jest zmienną lub jej negacją.
Przykładowo, poniższa formuła jest w postaci CNF (<math>\neg</math> oznacza negację):

:<math>(x_1 \vee \neg x_2 \vee \neg x_3) \wedge (x_1 \vee x_2 \vee x_4)</math>

Taka formuła jest ''spełnialna'' jeśli możemy przyporządkować zmiennym wartości ''prawda''/''fałsz'' tak żeby w każdej klauzuli przynajmniej jeden literał był prawdziwy. Przykładowo dla powyższej formuły możemy przyporządkować ''x''<sub>2</sub> [[fałsz]] i ''x''<sub>4</sub> prawdę. Problem stwierdzenia czy dana formuła CNF jest spełnialna jest również NP-zupełny i nazywa się CNF-SAT.

[[Image:CNF-SAT-independent-set-reduction.svg|right|thumb|200px|Graf skonstruowany dla przykładowej formuły powyżej]]
Opiszemy teraz [[algorytm wielomianowy]] przekształcający problem CNF-SAT w problem zbioru niezależnego. Na początku tworzymy wierzchołek dla każdego literału w formule, łącznie z jego powtórzeniami. Następnie łączymy krawędziami:
# Każdy literał z każdą jego negacją
# Każde dwa literały które należą do tej samej klauzuli

Twierdzimy, że powstały graf zawiera niezależny zbiór rozmiaru ''k'' wtedy i tylko wtedy gdy formuła od której zaczęliśmy była spełnialna.

Załóżmy, że znaleźliśmy wartościowanie które spełnia formułę. Możemy wtedy wybrać z każdej formuły po jednym literale, który jest prawdziwy w takim wartościowaniu. Ten zbiór jest niezależny ponieważ zawiera tylko po jednym literale z każdej klauzuli (nie ma krawędzi typu 2), i wartościowanie nie dopuszcza żeby literał i jego [[negacja]] były jednocześnie prawdziwe (nie ma krawędzi typu 1).

Z drugiej strony, załóżmy, że znaleźliśmy zbiór niezależny rozmiaru ''k''. Nie może on zawierać dwóch literałów w jednej klauzuli, ponieważ byłyby one połączone krawędzią. Zatem musi zawierać po jednym literale w każdej z ''k'' klauzul. Nie może zawierać też żadnego literału jednocześnie z jego negacją, ponieważ byłyby one też połączone krawędzią. Oznacza to że jeśli wybierzemy wartościowanie które nada tym ''k'' literałom wartość ''prawda'', to będzie ono spełniało początkową formułę.

[[Kategoria:Problemy obliczeniowe w teorii grafów|Z]]
[[Kategoria:Teoria obliczeń]]

[[en:Independent set problem]]
[[ja:最大独立集合問題]]
[[ru:Максимальное независимое множество вершин в дереве]]