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.

  • Przykładowe pokrycie wierzchołkowe w grafie

  • Najmniejsze pokrycie wierzchołkowe w grafie

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