TechCodeview

I denne artikkelen vil vi diskutere spenntreet og minimumspenningtreet. Men før vi beveger oss direkte mot spenningstreet, la oss først se en kort beskrivelse av grafen og dens typer.

Kurve

En graf kan defineres som en gruppe toppunkter og kanter for å koble sammen disse toppunktene. Typene grafer er gitt som følger -

Urettet graf:En urettet graf er en graf der alle kantene ikke peker i noen bestemt retning, dvs. de er ikke ensrettet; de er toveis. Det kan også defineres som en graf med et sett med V-hjørner og et sett med E-kanter, der hver kant forbinder to forskjellige hjørner.Tilkoblet graf:En tilkoblet graf er en graf der det alltid eksisterer en bane fra et toppunkt til et hvilket som helst annet toppunkt. En graf er koblet sammen hvis vi kan nå et hvilket som helst toppunkt fra et hvilket som helst annet toppunkt ved å følge kanter i begge retninger.Rettet graf:Rettede grafer er også kjent som digrafer. En graf er en rettet graf (eller digraf) hvis alle kantene som er tilstede mellom noen toppunkter eller noder i grafen er rettet eller har en definert retning.

La oss nå gå mot emnet som strekker seg over treet.

Hva er et spenntre?

Et spenntre kan defineres som undergrafen til en urettet tilkoblet graf. Den inkluderer alle hjørnene sammen med minst mulig antall kanter. Hvis et toppunkt savnes, er det ikke et spenntre. Et spenntre er en undergruppe av grafen som ikke har sykluser, og den kan heller ikke kobles fra.

Et overspennende tre består av (n-1) kanter, der 'n' er antall toppunkter (eller noder). Kantene på det spennede treet kan ha vekter tildelt dem. Alle mulige spenntrær som er opprettet fra den gitte grafen G vil ha samme antall toppunkter, men antall kanter i spanntreet vil være lik antall toppunkter i den gitte grafen minus 1.

En fullstendig urettet graf kan ha n^n-2 antall spenntrær hvor n er antall toppunkter i grafen. Anta, hvis n = 5 , ville antallet maksimalt mulige spenntrær være 5^5-2= 125.

Anvendelser av spenntreet

I utgangspunktet brukes et spenntre for å finne en minimumsbane for å koble sammen alle noder i grafen. Noen av de vanlige bruksområdene til spenntreet er oppført som følger -

• Klyngeanalyse
• Sivilt nettverksplanlegging
• Rutingprotokoll for datanettverk

La oss nå forstå spenntreet ved hjelp av et eksempel.

Eksempel på Spanning-tre

Anta at grafen er -

Som diskutert ovenfor, inneholder et overspennende tre det samme antall toppunkter som grafen, antall toppunkter i grafen ovenfor er 5; derfor vil spenntreet inneholde 5 toppunkter. Kantene i spenntreet vil være lik antall toppunkter i grafen minus 1. Så det vil være 4 kanter i spenntreet.

Noen av de mulige spenntrærne som vil bli opprettet fra grafen ovenfor, er gitt som følger -

Egenskaper til span-tree

Noen av egenskapene til spenningstreet er gitt som følger -

• Det kan være mer enn ett overspennende tre i en tilkoblet graf G.
• Et spenntre har ingen sykluser eller løkker.
• Et spenntre er minimalt tilkoblet, så å fjerne en kant fra treet vil gjøre grafen frakoblet.
• Et spenntre er maksimalt asyklisk, så å legge til en kant til treet vil skape en løkke.
• Det kan være et maksimum n^n-2 antall spenntrær som kan opprettes fra en komplett graf.
• Et spenntre har n-1 kanter, der 'n' er antall noder.
• Hvis grafen er en komplett graf, kan spenntreet konstrueres ved å fjerne maksimale (e-n+1) kanter, der 'e' er antall kanter og 'n' er antall toppunkter.

Så et spenntre er en delmengde av tilkoblet graf G, og det er ikke noe spenntre i en frakoblet graf.

Minimum spannende tre

Et minimum spenntre kan defineres som spenntreet der summen av vektene til kanten er minimum. Vekten til spenntreet er summen av vektene gitt til kantene på spenntreet. I den virkelige verden kan denne vekten betraktes som avstand, trafikkbelastning, overbelastning eller en hvilken som helst tilfeldig verdi.

Eksempel på minimumspenningstre

La oss forstå minimumspenningstreet ved hjelp av et eksempel.

Summen av kantene på grafen ovenfor er 16. Nå er noen av de mulige spenntrærne opprettet fra grafen ovenfor -

Så, minimumspenningstreet som er valgt fra spenntrærne ovenfor for den gitte vektede grafen er -

Anvendelser av minimum spaning tree

Anvendelsene til minimumspenningstreet er gitt som følger -

• Minimum spanning tree kan brukes til å designe vannforsyningsnettverk, telekommunikasjonsnettverk og elektriske nett.
• Den kan brukes til å finne stier i kartet.

Algoritmer for Minimum spaning tree

Et minimum spenntre kan bli funnet fra en vektet graf ved å bruke algoritmene gitt nedenfor -

• Prims algoritme
• Kruskals algoritme

La oss se en kort beskrivelse av begge algoritmene som er oppført ovenfor.

Prims algoritme - Det er en grådig algoritme som starter med et tomt spenntre. Den brukes til å finne minimumspenningstreet fra grafen. Denne algoritmen finner delsettet av kanter som inkluderer hvert toppunkt i grafen, slik at summen av vektene til kantene kan minimeres.

de er sangere

For å lære mer om prim-algoritmen, kan du klikke på lenken nedenfor - https://www.javatpoint.com/prim-algorithm

Kruskals algoritme - Denne algoritmen brukes også til å finne minimumsspenningstreet for en tilkoblet vektet graf. Kruskals algoritme følger også grådig tilnærming, som finner en optimal løsning på alle trinn i stedet for å fokusere på et globalt optimum.

For å lære mer om prim-algoritmen, kan du klikke på lenken nedenfor - https://www.javatpoint.com/kruskal-algoritme

Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg. Her har vi diskutert spenntre og minimum spenntre sammen med deres egenskaper, eksempler og applikasjoner.