Minimálna kostra grafu

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:

Obrázok:graf1201.jpg

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. 

Obrázok:graf1919.jpg

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.

Obrázok:graf1445.jpg

3. Keďže sme mali na výber dve hrany s rovnakou hodnotou, tak sme dostali dve minimálne kostry grafu.

Obrázok:graf4121.jpg

Obrázok:graf4324.jpg

Kategória:Teória grafov