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 nazywamy taki zbiór że:
Zobacz też
- skojarzenie
- zbiór dominujący
- zbiór niezależny
Przypisy
- ↑ Eric W.E.W. Weisstein Eric W.E.W., Vertex cover, [w:] MathWorld, Wolfram Research [dostęp 2016-01-03] (ang.).
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów |
|
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |