SPANNING TREE - VADNICA ZA DS

V tem članku bomo obravnavali vpeto drevo in minimalno vpeto drevo. Toda preden se premaknemo neposredno k vpetemu drevesu, si najprej oglejmo kratek opis grafa in njegovih vrst.

Graf

Graf je mogoče definirati kot skupino oglišč in robov, ki ta oglišča povezujejo. Vrste grafov so podane na naslednji način -

Neusmerjeni graf:Neusmerjeni graf je graf, v katerem vsi robovi ne kažejo v nobeno določeno smer, to pomeni, da niso enosmerni; so dvosmerni. Definiramo ga lahko tudi kot graf z nizom vozlišč V in nizom robov E, pri čemer vsak rob povezuje dve različni točki.Povezani graf:Povezani graf je graf, v katerem vedno obstaja pot od vozlišča do katerega koli drugega vozlišča. Graf je povezan, če lahko dosežemo katero koli oglišče iz katerega koli drugega oglišča tako, da sledimo robom v obe smeri.Usmerjeni graf:Usmerjeni grafi so znani tudi kot digrafi. Graf je usmerjen graf (ali digraf), če so vsi robovi med vsemi vozlišči ali vozlišči grafa usmerjeni ali imajo določeno smer.

Zdaj pa pojdimo k vpetemu drevesu tem.

Kaj je vpeto drevo?

Vpeto drevo lahko definiramo kot podgraf neusmerjenega povezanega grafa. Vključuje vsa oglišča skupaj z najmanjšim možnim številom robov. Če je katero koli vozlišče zgrešeno, to ni vpeto drevo. Vpeto drevo je podmnožica grafa, ki nima ciklov in ga tudi ni mogoče prekiniti.

Vpeto drevo je sestavljeno iz (n-1) robov, kjer je 'n' število oglišč (ali vozlišč). Robovi vpetega drevesa imajo lahko dodeljene uteži ali pa tudi ne. Vsa možna vpeta drevesa, ustvarjena iz danega grafa G, bi imela enako število vozlišč, vendar bi bilo število robov v vpetem drevesu enako številu vozlišč v danem grafu minus 1.

Popolni neusmerjeni graf ima lahko n^n-2 število vpetih dreves, kjer n je število vozlišč v grafu. Recimo, če n = 5 , bi bilo največje možno število vpetih dreves 5^5-2= 125.

Uporaba vpetega drevesa

V bistvu se vpeto drevo uporablja za iskanje minimalne poti za povezavo vseh vozlišč grafa. Nekaj pogostih aplikacij vpetega drevesa je navedenih v nadaljevanju -

Analiza grozdov
Načrtovanje civilnega omrežja
Protokol usmerjanja računalniškega omrežja

Zdaj pa poglejmo vpeto drevo s pomočjo primera.

Primer vpetega drevesa

Recimo, da je graf -

Kot je razloženo zgoraj, vpeto drevo vsebuje enako število točk kot graf, število točk v zgornjem grafu je 5; zato bo vpeto drevo vsebovalo 5 vozlišč. Robovi v vpetem drevesu bodo enaki številu vozlišč v grafu minus 1. Torej bodo v vpetem drevesu 4 robovi.

Nekatera možna vpeta drevesa, ki bodo ustvarjena iz zgornjega grafa, so podana takole -

Lastnosti vpetega drevesa

Nekatere lastnosti vpetega drevesa so podane na naslednji način -

V povezanem grafu G je lahko več kot eno vpeto drevo.
Vpeto drevo nima nobenih ciklov ali zank.
Vpeto drevo je minimalno povezan, tako bo odstranitev enega roba iz drevesa povzročila nepovezanost grafa.
Vpeto drevo je maksimalno aciklično, tako bo dodajanje enega roba drevesu ustvarilo zanko.
Lahko je največ n^n-2 število vpetih dreves, ki jih je mogoče ustvariti iz celotnega grafa.
Vpeto drevo ima n-1 robov, kjer je 'n' število vozlišč.
Če je graf popoln graf, se lahko vpeto drevo sestavi z odstranitvijo največjih (e-n+1) robov, kjer je 'e' število robov in 'n' število vozlišč.

Torej je vpeto drevo podmnožica povezanega grafa G in v nepovezanem grafu ni vpetega drevesa.

Najmanjše vpeto drevo

Minimalno vpeto drevo lahko definiramo kot vpeto drevo, v katerem je vsota uteži roba minimalna. Teža vpetega drevesa je vsota uteži robov vpetega drevesa. V resničnem svetu lahko to težo obravnavamo kot razdaljo, prometno obremenitev, zastoje ali katero koli naključno vrednost.

Primer minimalnega vpetega drevesa

Razumejmo minimalno vpeto drevo s pomočjo primera.

Vsota robov zgornjega grafa je 16. Nekatera možna vpeta drevesa, ustvarjena iz zgornjega grafa, so -

Najmanjše vpeto drevo, ki je izbrano izmed zgornjih vpetih dreves za dani uteženi graf, je torej -

Uporaba minimalnega vpetega drevesa

Uporabe minimalnega vpetega drevesa so podane na naslednji način:

Minimalno vpeto drevo se lahko uporablja za načrtovanje vodovodnih, telekomunikacijskih in električnih omrežij.
Uporablja se lahko za iskanje poti na zemljevidu.

Algoritmi za minimalno vpeto drevo

Najmanjše vpeto drevo je mogoče najti iz uteženega grafa z uporabo spodnjih algoritmov -

Primov algoritem
Kruskalov algoritem

Oglejmo si kratek opis obeh zgoraj navedenih algoritmov.

Primov algoritem - Je požrešen algoritem, ki se začne s praznim vpetim drevesom. Uporablja se za iskanje najmanjšega vpetega drevesa iz grafa. Ta algoritem najde podmnožico robov, ki vključuje vsako vozlišče grafa, tako da je mogoče minimizirati vsoto uteži robov.

pot nastavljena v Javi

Če želite izvedeti več o primovem algoritmu, lahko kliknete spodnjo povezavo - https://www.javatpoint.com/prim-algorithm

Kruskalov algoritem - Ta algoritem se uporablja tudi za iskanje najmanjšega vpetega drevesa za povezani uteženi graf. Kruskalov algoritem prav tako sledi pohlepnemu pristopu, ki najde optimalno rešitev na vsaki stopnji, namesto da bi se osredotočil na globalni optimum.

Če želite izvedeti več o primovem algoritmu, lahko kliknete spodnjo povezavo - https://www.javatpoint.com/kruskal-algorithm

Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen. Tukaj smo obravnavali vpeto drevo in minimalno vpeto drevo skupaj z njunimi lastnostmi, primeri in aplikacijami.