Logo
Úniapédia
Komunikácia
Teraz na Google Play
Nový! Na stiahnutie Úniapédia na Android ™!
Inštalovať
Rýchlejšie ako prehliadači!
 

Minimálna kostra grafu

Index 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.

8 vzťahy: Faktor grafu, Graf, Kruskalov algoritmus, Ohodnotený graf, Podgraf, Primov algoritmus, Súvislý graf, Strom (teória grafov).

Faktor grafu

Faktor grafu G alebo faktorový podgraf je taký podgraf grafu G, ktorý obsahuje všetky vrcholy grafu G. Podgraf H je faktor grafu G, ak množina vrcholov grafu H je totožná s množinou vrcholov grafu G. V(H).

Nový!!: Minimálna kostra grafu a Faktor grafu · Pozrieť viac »

Graf

Graf môže byť.

Nový!!: Minimálna kostra grafu a Graf · Pozrieť viac »

Kruskalov algoritmus

Kruskalov algoritmus, pomenovaný podľa Josepha Kruskala, je optimalizačný grafový algoritmus na hľadanie minimálnej kostry súvislého neorientovaného grafu s ohodnotením hrán, ktorý pri hľadaní riešenia uplatňuje pažravú stratégiu.

Nový!!: Minimálna kostra grafu a Kruskalov algoritmus · Pozrieť viac »

Ohodnotený graf

Ohodnotený graf alebo vážený graf je graf, ktorého prvky sú ohodnotené číslom (váhou), ktoré určujú výhodnosť prechodu daným prvkom (cena, priepustnosť, rýchlosť,...). Ohodnotený graf môže byť neorientovaný alebo orientovaný.

Nový!!: Minimálna kostra grafu a Ohodnotený graf · Pozrieť viac »

Podgraf

Podgraf je časť grafu, ktorá vznikne z pôvodného grafu vymazaním niektorých jeho vrcholov, všetkých hrán vedúcich do týchto vrcholov, poprípade vymazaním ďalších jeho hrán.

Nový!!: Minimálna kostra grafu a Podgraf · Pozrieť viac »

Primov algoritmus

Primov algoritmus (známy aj ako Jarníkov algoritmus, Primov-Jarníkov algoritmus alebo aj DJP algoritmus) je v informatike greedy algoritmus hľadajúci minimálnu kostru súvislého ohodnoteného grafu.

Nový!!: Minimálna kostra grafu a Primov algoritmus · Pozrieť viac »

Súvislý graf

Neorientovaný graf sa nazýva súvislý, ak medzi ľubovolnými dvoma jeho vrcholmi existuje cesta.

Nový!!: Minimálna kostra grafu a Súvislý graf · Pozrieť viac »

Strom (teória grafov)

right Strom alebo stromový graf je grafické vyjadrenie členenia určitej množiny na jej podmnožiny (napr. súbory na podsúbory, strojársky výrobok na podskupiny a súčiastky a pod.). Graf okrem členenia znázorňuje aj postupnosť členenia alebo zlučovania.

Nový!!: Minimálna kostra grafu a Strom (teória grafov) · Pozrieť viac »

VychádzajúcePrichádzajúce
Hej! Sme na Facebooku teraz! »