Problem pokrycia wierzchołkowego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie G 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łkowego to problem stwierdzania, czy w danym grafie istnieje pokrycie wierzchołkowe o danym rozmiarze k.

Definicja formalna[edytuj | edytuj kod]

Problemy decyzyjne definiuje się formalnie jako języki formalne.

Problem pokrycia wierzchołkowego przedstawiony formalnie:

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, VG zbiorem wierzchołków grafu G, a EG zbiorem krawędzi grafu G.

Status[edytuj | edytuj kod]

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