Kostra grafu – definícia
Vidíme, že hoci definícia je pomerne krátka, sú v nej až tri kľúčové pojmy:
súvislý
,
acyklický
,
faktor
. Pre istotu si ich zopakujme.
Faktor grafu je špeciálnym typom podgrafu. Je to taký podgraf, ktorý má všetky vrcholy pôvodného grafu.
Graf je súvislý, ak existuje cesta medzi každými jeho dvoma vrcholmi.
Graf je acyklický, ak žiaden jeho podgraf nie je cyklus (kružnica).
