Verzia z 09:12, 22. január 2010 upraviť JAnDbot (diskusia \| príspevky) Boti 139 628 editací d robot Zmenil: en:Spanning tree, ru:Остовное дерево ← Predchádzajúca úprava		Verzia z 14:29, 24. september 2010 upraviť vrátiť Byklop (diskusia \| príspevky) 16 editací Pôvodná úvodná definícia sa mi zdala málo zrozumiteľná a mýlivá. Preto som sa ju pokúsil vyjadriť lepšie. Ďalšia úprava →
Riadok 1: [[Obrázok:Spanning tree.svg\|thumb\|Kostra (červene) grafu (čierne)]] V [[Teória grafov\|teórii grafov]] je '''kostra grafu''' takým podgrafom grafu G na množine všetkých jeho vrcholov (súčasťou kostry grafu G musia byť všetky vrcholy grafu G), pre ktorý platí, že medzi každými dvoma vrcholmi existuje práve jedna cesta. Ináč povedané, kostra je graf, ktorý získame z pôvodného grafu G postupným rušením takých hrán, ktorých odstránením sa nenaruší súvislosť grafu. Akonáhle už neexistuje žiadna hrana, ktorú by sme mohli odstrániť, získaný graf je kostrou pôvodného grafu G. „''Kostra''“ je teda akýmsi hranovým minimom potrebným na to, aby graf „držal po kope“. '''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“. == Definície ==

Kostra grafu: Rozdiel medzi revíziami