Wikipedie

Vrcholové pokrytí: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
m link
→‎Definice: Wikilink
značky: editace z mobilu editace z mobilního webu
Řádek 12:
 
=== Vlastnosti ===
* Nějaká podmnožina vrcholů je vrcholovým pokrytím, právě když její [[doplněkDoplněk (teorie grafů)množiny|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).
 
Citováno z „https://cs.wikipedia.org/wiki/Vrcholové_pokrytí“