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^[1].

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 ${\displaystyle G=(V,E)}$ nazywamy taki zbiór ${\displaystyle V',}$ że:

${\displaystyle 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

Przypisy