Pokrycie wierzchołkowe

Pokrycie wierzchołkowe grafu

Pokrycie wierzchołkowe grafu G to zbiór wierzchołków, w którym każda krawędź grafu jest połączona przynajmniej z jednym wierzchołkiem z tego zbioru. Problem znajdowania najmniejszego pokrycia wierzchołkowego jest klasyfikowany jako problem NP-zupełny, co oznacza, że nie istnieje znany algorytm wielomianowy, który mógłby go rozwiązać w ogólności.

Definicja formalna

Formalnie, pokrycie wierzchołkowe grafu $G=(V,E)$ definiuje się jako zbiór $V’$, spełniający warunki:

• $V’\; subseteq\; V$
• $forall\; e\; in\; E,\; exists\; v\; in\; V’\; :\; v\; in\; e$