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