![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Spanning_tree.svg/langsk-640px-Spanning_tree.svg.png&w=640&q=50)
Kostra grafu
From Wikipedia, the free encyclopedia
V 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. Hneď ako 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“.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Spanning_tree.svg/320px-Spanning_tree.svg.png)