Vrcholové pokrytí: Porovnání verzí
Smazaný obsah Přidaný obsah
Nová stránka: V matematické disciplíně teorie grafů je '''vrcholové pokrytí''' grafu podmnožina vrcholů taková, že každá hrana grafu je incidentní asp… |
(Žádný rozdíl)
|
Verze z 16. 9. 2012, 13:53
V matematické disciplíně teorie grafů je vrcholové pokrytí 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-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož duálním lin. programem je maximální párování grafu.
Definice
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.
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í.
- Úplný bipartitní graf má minimální pokrytí velikosti .
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. nezávislé množiny (Gallai 1959).