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.
Definicja formalna Pokryciem wierzchołkowym grafu nazywamy taki zbiór że:
Zobacz też skojarzenie zbiór dominujący zbiór niezależny
Przypisy
Kategoria:Teoria grafów