Kostra grafu: Porovnání verzí
Smazaný obsah Přidaný obsah
Robot: Opravuji 1 zdrojů and označuji 0 zdrojů jako nefunkční #IABot (v2.0beta15) |
m Robot: oprava ISBN; kosmetické úpravy |
||
Řádek 1:
[[Soubor:Spanning tree.svg|
V [[teorie grafů|teorii grafů]] je '''kostra souvislého grafu ''G''''' takový [[podgraf]] [[Souvislý graf|souvislého grafu]] ''G'' na [[množina|množině]] všech jeho [[Graf (teorie grafů)#Základní pojmy|vrcholů]], který je [[strom (graf)|stromem]].
Řádek 18:
=== Minimální kostra ===
[[Soubor:Minimum spanning tree.svg|
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>
Řádek 48:
== Reference ==
* Jiří Matoušek, Jaroslav Nešetřil: ''Kapitoly z diskrétní matematiky'', nakladatelství Karolinum, Praha 2002, {{ISBN
* Jakub Černý: [https://web.archive.org/web/20071018060717/http://kam.mff.cuni.cz/~kuba/ka/ Základní grafové algoritmy] (texty v pdf)
| |||