Problem pokrycia wierzchołkowego
Z Wikipedii
Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie pokrycia wierzchołkowego o najmniejszym rozmiarze, tj. zawierającego możliwie najmniejszą liczbę wierzchołków. Tak zdefiniowany problem pokrycia wierzchołkowego jest problemem optymalizacyjnym. W teorii złożoności obliczeniowej częściej rozważa się problemy decyzyjne. Decyzyjna wersja problemu pokrycia wierzchołówego to problem stwierdzania czy w danym grafie istnieje pokrycie wierzchołkowe o danym rozmiarze k.
[edytuj] Definicja formalna
Problemy decyzyjne definuje się formalnie jako języki formalne. Problem pokrycia wierzchołkowego definuje się formalnie jako:
gdzie GRAPHS jest zbiorem grafów, VG zbiorem wierzchołków grafu G, a EG zbiorem krawędzi grafu G.
[edytuj] Status
Problem pokrycia wierzchołkowego jest problemem NP-zupełnym.
