Problem pokrycia wierzchołkowego

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:

$VC = \{ (G, k) \in GRAPHS \times \mathbb{N} : \exist V \subseteq V_G, \forall e \in E_G, \exist v \in V : v \in e \ \and \ card V = k \}$

gdzie GRAPHS jest zbiorem grafów, V_G zbiorem wierzchołków grafu G, a E_G zbiorem krawędzi grafu G.

[edytuj] Status

Problem pokrycia wierzchołkowego jest problemem NP-zupełnym.

Ponieważ to hasło związane z informatyką ma formę zaledwie zalążkową, pomóż nam je rozbudować, o ile dysponujesz odpowiednimi źródłami.
Prosimy, zapoznaj się najpierw z zasadami oraz zaleceniami edytowania Wikipedii.

Źródło: "http://pl.wikipedia.org/wiki/Problem_pokrycia_wierzcho%C5%82kowego"