Kostra grafu: Rozdiel medzi revíziami

Smazaný obsah Přidaný obsah
d poradie sekcií
Riadok 1:
[[ObrázokSúbor: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“.
Riadok 75:
* Jakub Černý: [http://kam.mff.cuni.cz/~kuba/ka/ Základní grafové algoritmy] (texty v pdf)
* Diskrétna matematika – Doc. RNDr. Michal Bučko, CSc. – RNDr. Marián Klešč
 
== Pozri aj ==
*[[Minimálna kostra grafu]]
 
== Externé odkazy ==
Řádek 80 ⟶ 83:
*{{Preklad|cs|Kostra grafu}}
* http://ics.upjs.sk/~galcik/files/progLS2008/grafy.ppt
 
==Pozri aj==
*[[Minimálna kostra grafu]]
 
[[Kategória:Teória grafov]]