Kostra grafu: Porovnání verzí

V [[teorie grafů|teorii grafů]] je '''kostra grafu ''G''''' takový [[podgraf]] [[graf]]u ''G'' na [[množina|množině]] všech jeho [[graf#základní pojmy|vrcholů]], který je [[strom (graf)|stromem]].

 

 

=== Minimální kostra ===

Je-li navíc definována funkce <math>w:\mathit{E}\rightarrow\mathbb{R}</math> (tzv. ''ohodnocení hran''), má smysl hledat '''minimální kostru''' – tedy takovou kostru <math>(\mathit{V}, \mathit{E}')</math>, že výraz

:<math>w(E') = \sum_{e \in \mathit{E}'} w(e)</math>