A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Tento článok alebo jeho časť si vyžaduje úpravu, aby zodpovedal vyššiemu štandardu kvality. Prosím, pozrite si stránky pomocníka, odporúčanie pre encyklopedický štýl a článok vhodne upravte. |
Minimálna kostra grafu je kostra ohodnoteného grafu, ktorá má najmenšie ohodnotenie hrán, spomedzi všetkých kostier grafu. Ohodnotený graf je graf, ktorého hrany sú ohodnotené číslom, ktoré určujú výhodnosť prechodu danou hranou (cena, priepustnosť).
Definície
Definícia stromu: Strom je neprázdny súvislý graf, ktorý neobsahuje kružnice.
Definícia lesa: Les je graf, ktorého komponentmi sú stromy.
Definícia faktora: Podgraf H je faktor grafu G, ak množina vrcholov grafu H je totožná s množinou vrcholov grafu G. V(H) = V(G)
Definícia kostry grafu: Kostra grafu G = (V,H) je taký jeho faktor, ktorý je stromom. V grafe G = (V,H) existuje kostra práve vtedy, ak G je súvislý.
Maximálna kostra: Maximálna kostra je opakom minimálnej kostry.
Na určovanie minimálnej kostry grafu poznáme napríklad Kruskalov algoritmus alebo Primov algoritmus.
Príklad
Máme graf:
Použijeme Kruskalov algoritmus.
V grafe je 8 vrcholov, teda kostra bude mať 7 hrán.
Ohodnotenie hrán: 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6.
Postupne pridávame hrany od najmenšej hodnoty.
1. Keďže prvé tri hodnoty hrán sú rovnaké, dáme ich všetky naraz.
2. Pridanie hrán s hodnotou 2. Keďže sme už pridali 6 hrán, stačí pridať ešte jednu, aby sme dostali minimálnu kostru grafu.
3. Keďže sme mali na výber dve hrany s rovnakou hodnotou, tak sme dostali dve minimálne kostry grafu.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Hrana (teória grafov)
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Minimálna kostra grafu
Most (teória grafov)
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Párny graf
Petersenov graf
Podgraf
Priesečníkové číslo (teória grafov)
Problém obchodného cestujúceho
Problém siedmich mostov
Rovinný graf
Súvislý graf
Sled (teória grafov)
Spektrálna teória grafov
Strom (teória grafov)
Teória grafov
Teória grafov – grafová postupnosť
Topologická teória grafov
Vrchol (teória grafov)
Vzdialenosť (teória grafov)
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk