Kostra grafu: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
dBez shrnutí editace |
súvislého |
||
Riadok 2:
[[Obrázok:Spanning tree.svg|thumb|Kostra (červene) grafu (čierne)]]
'''Kostra grafu''' súvislého G je taký jeho [[faktor grafu|faktor]], ktorý neobsahuje [[kružnica (graf)|kružnice]].
'''Kostra grafu''' je taká podmnožina T hrán grafu G, že platí: Medzi každými 2 vrcholmi grafu existuje cesta využívajúca len hrany kostry T. Odobratím ľubovoľnej hrany kostry už vlastnosť nebude platiť. „''Kostra''“ sú hrany, ktoré graf „držia po kope“.
| |||