Pokrycie wierzchołkowe
Z Wikipedii, wolnej encyclopedia
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