Minimálna kostra grafu
 |
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
[upraviť | upraviť zdroj]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
[upraviť | upraviť zdroj]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.
