Vrcholové pokrytí
Author
Albert FloresV matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, ž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-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož duálním lin. +more programem je maximální párování grafu.
Definice
Formálně, vrcholové pokrytí grafu G je množina C jeho vrcholů taková, že každá hrana z G je incidentní aspoň s jedním vrcholem z C. Množina C se nazývá pokrytí hran grafu G.
Příklady vrcholového pokrytí
Množina všech vrcholů každého grafu. * Koncové vrcholy maximálního párování tvoří vrcholové pokrytí. +more * Úplný bipartitní graf K_{m,n} má minimální pokrytí velikosti \tau(K_{m,n})=\min(m,n).
Vlastnosti
Nějaká podmnožina vrcholů je vrcholovým pokrytím, právě když její doplněk je nezávislou množinou. Z toho rovněž plyne: * Počet vrcholů grafu je roven velikosti minimálního vrcholového pokrytí + velikost max. +more nezávislé množiny (Gallai 1959).