Vrcholové pokrytí: Porovnání verzí
Smazaný obsah Přidaný obsah
m link |
|||
Řádek 1:
V matematické disciplíně [[teorie grafů]] je '''vrcholové pokrytí''' [[graf (teorie grafů)|grafu]] taková podmnožina vrcholů
'''Minimální vrcholové pokrytí''' je klasický problém [[Teoretická informatika|teoretické informatiky]] a je příkladem [[NP-úplnost]]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]].
== 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í párování grafu|maximálního párování]] tvoří vrcholové pokrytí.
Řádek 14 ⟶ 12:
=== Vlastnosti ===
* Nějaká podmnožina vrcholů je vrcholovým pokrytím, právě když její [[doplněk (teorie grafů)|doplněk]] je [[nezávislá množina|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 ([[Tibor Gallai|Gallai]] 1959).
| |||