Pokrycie wierzchołkowe

Pokrycie wierzchołkowe grafu G – taki podzbiór jego wierzchołków, że każda krawędź G jest incydentna do jakiegoś wierzchołka z tego podzbioru.

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

• 
  Przykładowe pokrycie wierzchołkowe w grafie
• 
  Najmniejsze pokrycie wierzchołkowe w grafie

Definicja formalna

Pokryciem wierzchołkowym grafu $G=(V,E)$ nazywamy taki zbiór $V',$ że:

$V'\subseteq V\land (\forall e\in E,\exists v\in V':v\in e)$

Zobacz też

• skojarzenie
• zbiór dominujący
• zbiór niezależny