Pokrycie wierzchołkowe


Pokrycie wierzchołkowe w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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.

Definicja formalna | edytuj kod

Pokryciem wierzchołkowym grafu G = ( V , E ) {\displaystyle G=(V,E)} nazywamy taki zbiór V , {\displaystyle V',} że:

V V ( e E , v V : v e ) {\displaystyle V'\subseteq V\land (\forall e\in E,\exists v\in V':v\in e)}

Zobacz też | edytuj kod

Przypisy | edytuj kod

  1. Eric W.E.W. Weisstein Eric W.E.W., Vertex cover, [w:] MathWorld [online], Wolfram Research [dostęp 2016-01-03]  (ang.).
Na podstawie artykułu: "Pokrycie wierzchołkowe" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy