SPANNING TREE - VODIČ ZA DS

U ovom članku raspravljat ćemo o razapinjućem stablu i minimalnom razapinjućem stablu. Ali prije nego što prijeđemo izravno na razapinjuće stablo, prvo ćemo pogledati kratak opis grafa i njegovih vrsta.

Grafikon

Graf se može definirati kao skupina vrhova i bridova koji povezuju te vrhove. Vrste grafova date su kako slijedi -

Neusmjereni graf:Neusmjereni graf je graf u kojem svi rubovi ne pokazuju niti jedan određeni smjer, tj. nisu jednosmjerni; dvosmjerni su. Također se može definirati kao graf sa skupom V vrhova i skupom E bridova, pri čemu svaki brid povezuje dva različita vrha.Povezani graf:Povezani graf je graf u kojem uvijek postoji put od vrha do bilo kojeg drugog vrha. Graf je povezan ako možemo doći do bilo kojeg vrha iz bilo kojeg drugog vrha prateći bridove u bilo kojem smjeru.Usmjereni graf:Usmjereni grafovi su također poznati kao digrafi. Graf je usmjereni graf (ili digraf) ako su svi bridovi prisutni između bilo kojih vrhova ili čvorova grafa usmjereni ili imaju definiran smjer.

Sada, idemo prema stablu koje se razapinje.

Što je razapinjuće stablo?

Razapinjuće stablo se može definirati kao podgraf neusmjerenog povezanog grafa. Uključuje sve vrhove zajedno s najmanjim mogućim brojem bridova. Ako je bilo koji vrh propušten, to nije razapinjuće stablo. Razapinjuće stablo je podskup grafa koji nema cikluse, a također se ne može odspojiti.

Razapinjuće stablo sastoji se od (n-1) bridova, gdje je 'n' broj vrhova (ili čvorova). Rubovi razapinjućeg stabla mogu, ali ne moraju imati dodijeljene težine. Sva moguća razapinjuća stabla stvorena iz danog grafa G imala bi isti broj vrhova, ali bi broj bridova u razapinjućem stablu bio jednak broju vrhova u danom grafu minus 1.

Kompletan neusmjereni graf može imati n^n-2 broj razapinjućih stabala gdje n je broj vrhova u grafu. Pretpostavimo, ako n = 5 , broj maksimalno mogućih razapinjućih stabala bio bi 5^5-2= 125.

Primjene razapinjućeg stabla

U osnovi, razapinjuće stablo se koristi za pronalaženje minimalnog puta za povezivanje svih čvorova grafa. Neke od uobičajenih primjena razapinjućeg stabla navedene su kako slijedi -

Klasterska analiza
Planiranje civilne mreže
Protokol usmjeravanja računalne mreže

Razmotrimo sada razapinjuće stablo uz pomoć primjera.

Primjer razapinjućeg stabla

Pretpostavimo da je graf -

Kao što je gore objašnjeno, razapinjuće stablo sadrži isti broj vrhova kao i graf, broj vrhova u gornjem grafu je 5; stoga će razapinjuće stablo sadržavati 5 vrhova. Bridovi u razapinjućem stablu bit će jednaki broju vrhova u grafu minus 1. Dakle, bit će 4 brida u razapinjućem stablu.

Neka od mogućih razapinjućih stabala koja će se stvoriti iz gornjeg grafa dana su kako slijedi -

Svojstva razapinjućeg stabla

Neka od svojstava razapinjućeg stabla data su kako slijedi -

Može postojati više od jednog razapinjućeg stabla povezanog grafa G.
Razapinjuće stablo nema cikluse niti petlje.
Razapinjuće stablo je minimalno povezani, tako da će uklanjanje jednog ruba iz stabla učiniti graf nepovezanim.
Razapinjuće stablo je maksimalno aciklički, tako da će dodavanje jednog ruba stablu stvoriti petlju.
Može biti maksimalno n^n-2 broj razapinjućih stabala koja se mogu stvoriti iz kompletnog grafa.
Razapinjuće stablo ima n-1 rubova, gdje je 'n' broj čvorova.
Ako je graf potpuni graf, tada se razapinjuće stablo može konstruirati uklanjanjem maksimalnih (e-n+1) bridova, gdje je 'e' broj bridova, a 'n' broj vrhova.

Dakle, razapinjuće stablo je podskup povezanog grafa G, a ne postoji razapinjuće stablo nepovezanog grafa.

Minimalno razapinjuće stablo

Minimalno razapinjuće stablo može se definirati kao razapinjuće stablo u kojem je zbroj težina ruba minimalan. Težina razapinjućeg stabla zbroj je težina dodijeljenih rubovima razapinjućeg stabla. U stvarnom svijetu, ova se težina može smatrati udaljenošću, prometnim opterećenjem, zakrčenjem ili bilo kojom slučajnom vrijednošću.

Primjer minimalnog razapinjućeg stabla

Razmotrimo minimalno razapinjuće stablo uz pomoć primjera.

Zbroj bridova gornjeg grafa je 16. Sada, neka od mogućih razapinjućih stabala stvorenih iz gornjeg grafa su -

Dakle, minimalno razapinjuće stablo koje je odabrano iz gornjih razapinjućih stabala za dati ponderirani graf je -

Primjene minimalnog razapinjućeg stabla

Primjene minimalnog razapinjućeg stabla date su kako slijedi -

Minimalno razapinjuće stablo može se koristiti za projektiranje vodoopskrbnih mreža, telekomunikacijskih mreža i električnih mreža.
Može se koristiti za pronalaženje staza na karti.

Algoritmi za minimalno razapinjuće stablo

Minimalno razapinjuće stablo može se pronaći iz ponderiranog grafa korištenjem dolje navedenih algoritama -

Primov algoritam
Kruskalov algoritam

Pogledajmo kratak opis oba gore navedena algoritma.

Primov algoritam - To je pohlepan algoritam koji počinje s praznim razapinjućim stablom. Koristi se za pronalaženje minimalnog razapinjućeg stabla iz grafa. Ovaj algoritam pronalazi podskup bridova koji uključuje svaki vrh grafa tako da se zbroj težina bridova može minimizirati.

rudarenje podataka

Da biste saznali više o prim algoritmu, možete kliknuti donju poveznicu - https://www.javatpoint.com/prim-algorithm

Kruskalov algoritam - Ovaj se algoritam također koristi za pronalaženje minimalnog razapinjućeg stabla za povezani ponderirani graf. Kruskalov algoritam također slijedi pohlepan pristup, koji pronalazi optimalno rješenje u svakoj fazi umjesto da se fokusira na globalni optimum.

Da biste saznali više o prim algoritmu, možete kliknuti donju poveznicu - https://www.javatpoint.com/kruskal-algorithm

Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan. Ovdje smo raspravljali o razapinjućem stablu i minimalnom razapinjućem stablu zajedno s njihovim svojstvima, primjerima i primjenama.