Kostra grafu: Rozdiel medzi revíziami

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áhleHneď 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“.