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^{\prime },$ że:

$V^{\prime }\subseteq V\wedge (\mathrm{\forall }e\in E,\mathrm{\exists }v\in V^{\prime }:v\in e)$

Zobacz też

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