SPANNING TREE - NÁVOD DS

V tomto článku budeme diskutovať o kostre a minimálnom kostre. Ale predtým, než sa presunieme priamo ku kostre, pozrime sa najprv na stručný popis grafu a jeho typov.

Graf

Graf môže byť definovaný ako skupina vrcholov a hrán na spojenie týchto vrcholov. Typy grafov sú uvedené nasledovne -

Neorientovaný graf:Neorientovaný graf je graf, v ktorom všetky hrany neukazujú žiadnym konkrétnym smerom, t.j. nie sú jednosmerné; sú obojsmerné. Môže byť tiež definovaný ako graf s množinou V vrcholov a množinou E hrán, pričom každá hrana spája dva rôzne vrcholy.Prepojený graf:Súvislý graf je graf, v ktorom vždy existuje cesta z vrcholu do akéhokoľvek iného vrcholu. Graf je spojený, ak môžeme dosiahnuť akýkoľvek vrchol z akéhokoľvek iného vrcholu sledovaním hrán v oboch smeroch.Orientovaný graf:Orientované grafy sú známe aj ako digrafy. Graf je orientovaný graf (alebo digraf), ak sú všetky hrany prítomné medzi akýmikoľvek vrcholmi alebo uzlami grafu smerované alebo majú definovaný smer.

Teraz prejdime k téme kostry.

Čo je to kostra?

Spanning tree možno definovať ako podgraf neorientovaného spojeného grafu. Zahŕňa všetky vrcholy spolu s najmenším možným počtom hrán. Ak niektorý vrchol chýba, nejde o kostru. Spanning tree je podmnožina grafu, ktorá nemá cykly a tiež sa nedá odpojiť.

Kostra sa skladá z (n-1) hrán, kde 'n' je počet vrcholov (alebo uzlov). Okraje kostry môžu alebo nemusia mať priradené váhy. Všetky možné kostry vytvorené z daného grafu G by mali rovnaký počet vrcholov, ale počet hrán kostry by sa rovnal počtu vrcholov v danom grafe mínus 1.

Môže mať úplný neorientovaný graf n^n-2 počet kostrových stromov kde n je počet vrcholov v grafe. Predpokladajme, že ak n = 5 , počet maximálnych možných kostrov by bol 5^5-2= 125.

Aplikácie kostry

V podstate sa kostra používa na nájdenie minimálnej cesty na spojenie všetkých uzlov grafu. Niektoré z bežných aplikácií kostry sú uvedené nasledovne -

Zhluková analýza
Plánovanie občianskej siete
Smerovací protokol počítačovej siete

Teraz pochopme kostru pomocou príkladu.

Príklad Spanning tree

Predpokladajme, že graf je -

Ako bolo uvedené vyššie, kostra obsahuje rovnaký počet vrcholov ako graf, počet vrcholov vo vyššie uvedenom grafe je 5; kostra teda bude obsahovať 5 vrcholov. Hrany v kostre sa budú rovnať počtu vrcholov v grafe mínus 1. Takže v kostre budú 4 hrany.

Niektoré z možných kostrov, ktoré budú vytvorené z vyššie uvedeného grafu, sú uvedené nasledovne -

Vlastnosti kostry

Niektoré z vlastností kostry sú uvedené nasledovne -

Prepojeného grafu G môže byť viac ako jedna kostra.
Spanning tree nemá žiadne cykly ani slučku.
Kosťový strom je minimálne pripojený, takže odstránením jednej hrany zo stromu sa graf odpojí.
Kosťový strom je maximálne acyklické, takže pridanie jedného okraja do stromu vytvorí slučku.
Môže tam byť maximum n^n-2 počet kostrových stromov, ktoré možno vytvoriť z kompletného grafu.
Kosť má n-1 hrany, kde 'n' je počet uzlov.
Ak je graf úplný graf, kostru možno zostaviť odstránením maximálnych (e-n+1) hrán, kde 'e' je počet hrán a 'n' je počet vrcholov.

Takže kostra je podmnožinou spojeného grafu G a neexistuje kostra nespojeného grafu.

Minimálny kostrový strom

Minimálny kostra môže byť definovaná ako kostra, v ktorej je súčet váh hrany minimálny. Hmotnosť kostry je súčet váh pridelených okrajom kostry. V reálnom svete môže byť táto hmotnosť považovaná za vzdialenosť, dopravnú záťaž, zápchu alebo akúkoľvek náhodnú hodnotu.

Príklad minimálneho kostry

Poďme pochopiť minimálnu kostru pomocou príkladu.

Súčet hrán vyššie uvedeného grafu je 16. Teraz, niektoré možné kostry vytvorené z vyššie uvedeného grafu sú -

Minimálny kostrový strom, ktorý je vybraný z vyššie uvedených kostrových stromov pre daný vážený graf je teda -

Aplikácie minimálneho kostry

Aplikácie minimálnej kostry sú uvedené nasledovne -

Minimálny kostra sa môže použiť na návrh vodovodných sietí, telekomunikačných sietí a elektrických sietí.
Dá sa použiť na nájdenie ciest na mape.

Algoritmy pre minimálny kostrový strom

Minimálny kostrový strom možno nájsť z váženého grafu pomocou nižšie uvedených algoritmov -

Primov algoritmus
Kruskalov algoritmus

Pozrime sa na stručný popis oboch vyššie uvedených algoritmov.

Primov algoritmus - Je to chamtivý algoritmus, ktorý začína prázdnym kostrou. Používa sa na nájdenie minimálneho kostry z grafu. Tento algoritmus nájde podmnožinu hrán, ktorá zahŕňa každý vrchol grafu, takže súčet váh hrán môže byť minimalizovaný.

trieda vs objekt java

Ak sa chcete dozvedieť viac o algoritme prim, môžete kliknúť na nižšie uvedený odkaz - https://www.javatpoint.com/prim-algorithm

Kruskalov algoritmus - Tento algoritmus sa tiež používa na nájdenie minimálneho kostry pre spojený vážený graf. Kruskalov algoritmus tiež sleduje chamtivý prístup, ktorý v každej fáze nachádza optimálne riešenie namiesto toho, aby sa zameriaval na globálne optimum.

Ak sa chcete dozvedieť viac o algoritme prim, môžete kliknúť na nižšie uvedený odkaz - https://www.javatpoint.com/kruskal-algorithm

Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný. Tu sme diskutovali o kostre a minimálnom kostre spolu s ich vlastnosťami, príkladmi a aplikáciami.