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 edytuj
Pokryciem wierzchołkowym grafu nazywamy taki zbiór że:
Zobacz też edytuj
Przypisy edytuj
- ↑ Eric W. Weisstein , Vertex cover, [w:] MathWorld, Wolfram Research [dostęp 2016-01-03] (ang.).