Vrcholové pokrytí: Porovnání verzí

V matematické disciplíně [[teorie grafů]] je '''vrcholové pokrytí''' [[graf (teorie grafů)|grafu]] podmnožina vrcholů taková, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny.

'''Minimální vrcholové pokrytí''' je klasický problém teoretické informatiky a je příkladem [[NP-úplnost|NP-úplnosti]]i. Lze ho formulovat jako napůl celočíselný [[lineární program]] jehož [[duální lineární program|duálním lin. programem]] je [[maximální párování grafu]].

Formálně, vrcholové pokrytí grafu ''G'' je množina ''C'' jeho vrcholů taková, že ''G'' je incidentní aspoň s jednou hranou z ''C''. Množina ''C'' se nazývá ''pokrytí'' hran grafu ''G''.

* Koncové vrcholy [[maximální párování grafu | maximálního párování]] tvoří vrcholové pokrytí.