Wikipedia

Pokrycie wierzchołkowe: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m ilustracja, źródła/przypisy
Angielska nazwa nie jest potrzebna. Nazwy w innych językach dodajemy w przypadku, gdy np. obiekt dotyczy historii innego państwa.
Linia 1:
{{Teoria grafów}}
'''Pokrycie wierzchołkowe''' ({{ang.|Vertex cover}}) [[Graf (matematyka)|grafu]] G to taki podzbiór jego wierzchołków, że każda krawędź G jest [[Incydencja|incydentna]] do jakiegoś wierzchołka z tego podzbioru.<ref>{{Cytuj stronę | url = http://mathworld.wolfram.com/VertexCover.html | tytuł = Vertex cover | opublikowany = mathworld.wolfram.com | data dostępu = 2016-01-03}}</ref>.
 
[[Problem pokrycia wierzchołkowego|Problem znajdowania najmniejszego pokrycia wierzchołkowego]] jest problemem [[NP-zupełność|NP-zupełnym]].
Źródło: „https://pl.wikipedia.org/wiki/Pokrycie_wierzchołkowe”