SPÆNDENDE TRÆ

I denne artikel vil vi diskutere spændingstræet og minimumspændingstræet. Men før vi bevæger os direkte mod spændingstræet, lad os først se en kort beskrivelse af grafen og dens typer.

Kurve

En graf kan defineres som en gruppe af toppunkter og kanter for at forbinde disse toppunkter. Typerne af grafer er angivet som følger -

Urettet graf:En urettet graf er en graf, hvor alle kanterne ikke peger i nogen bestemt retning, dvs. de er ikke ensrettede; de er tovejs. Det kan også defineres som en graf med et sæt V-spidser og et sæt E-kanter, hvor hver kant forbinder to forskellige spidser.Forbundet graf:En forbundet graf er en graf, hvor der altid eksisterer en sti fra et toppunkt til et hvilket som helst andet toppunkt. En graf er forbundet, hvis vi kan nå et hvilket som helst toppunkt fra et hvilket som helst andet toppunkt ved at følge kanter i begge retninger.Instrueret graf:Direkte grafer er også kendt som digrafer. En graf er en rettet graf (eller digraf), hvis alle kanterne, der findes mellem grafens toppunkter eller knuder, er rettet eller har en defineret retning.

Lad os nu bevæge os mod emnet, der spænder over træet.

Hvad er et spændingstræ?

Et spændingstræ kan defineres som undergrafen af en urettet forbundet graf. Det inkluderer alle hjørnerne sammen med det mindst mulige antal kanter. Hvis et toppunkt savnes, er det ikke et spændingstræ. Et spændingstræ er en delmængde af grafen, der ikke har cyklusser, og den kan heller ikke afbrydes.

Et spændingstræ består af (n-1) kanter, hvor 'n' er antallet af hjørner (eller noder). Kanterne af det spændende træ kan have vægte tildelt dem eller ikke. Alle de mulige spændingstræer skabt ud fra den givne graf G ville have det samme antal hjørner, men antallet af kanter i spændingstræet ville være lig med antallet af hjørner i den givne graf minus 1.

En komplet urettet graf kan have n^n-2 antal spændende træer hvor n er antallet af hjørner i grafen. Antag, hvis n = 5 , ville antallet af maksimalt mulige spændende træer være 5^5-2= 125.

Anvendelser af spændingstræet

Grundlæggende bruges et spændingstræ til at finde en minimumssti til at forbinde alle knudepunkter i grafen. Nogle af de almindelige anvendelser af spændingstræet er angivet som følger -

Klyngeanalyse
Planlægning af civilt netværk
Computernetværk routing protokol

Lad os nu forstå spændingstræet ved hjælp af et eksempel.

Eksempel på Spanning tree

Antag at grafen er -

Som diskuteret ovenfor indeholder et spændingstræ det samme antal toppunkter som grafen, antallet af toppunkter i ovenstående graf er 5; derfor vil spændingstræet indeholde 5 toppunkter. Kanterne i spændingstræet vil være lig med antallet af toppunkter i grafen minus 1. Så der vil være 4 kanter i spændingstræet.

Nogle af de mulige spændingstræer, der vil blive skabt ud fra ovenstående graf, er givet som følger -

Egenskaber for spændingstræ

Nogle af egenskaberne for spændingstræet er givet som følger -

Der kan være mere end ét spændingstræ i en forbundet graf G.
Et spændingstræ har ingen cyklusser eller sløjfe.
Et spændingstræ er minimalt forbundet, så fjernelse af en kant fra træet vil gøre grafen afbrudt.
Et spændingstræ er maksimalt acyklisk, så tilføjelse af en kant til træet vil skabe en løkke.
Der kan være et maksimum n^n-2 antal spændende træer, der kan oprettes ud fra en komplet graf.
Et spændingstræ har n-1 kanter, hvor 'n' er antallet af noder.
Hvis grafen er en komplet graf, kan spændingstræet konstrueres ved at fjerne maksimale (e-n+1) kanter, hvor 'e' er antallet af kanter og 'n' er antallet af hjørner.

Så et spændingstræ er en delmængde af forbundet graf G, og der er ikke noget spændingstræ i en afbrudt graf.

Minimumsspændende træ

Et minimum spændingstræ kan defineres som spændingstræet, hvor summen af kantens vægte er minimum. Vægten af spændingstræet er summen af vægtene givet til kanterne af spændingstræet. I den virkelige verden kan denne vægt betragtes som afstand, trafikbelastning, overbelastning eller enhver tilfældig værdi.

Eksempel på minimumspændingstræ

Lad os forstå minimumspændingstræet ved hjælp af et eksempel.

Summen af kanterne på ovenstående graf er 16. Nu er nogle af de mulige spændingstræer skabt ud fra ovenstående graf -

Så det mindste spændingstræ, der er valgt fra ovenstående spændingstræer for den givne vægtede graf, er -

Anvendelser af minimum spændingstræ

Anvendelserne af minimumspændingstræet er givet som følger -

Minimum spanning tree kan bruges til at designe vandforsyningsnetværk, telekommunikationsnetværk og elektriske net.
Det kan bruges til at finde stier på kortet.

Algoritmer for minimum spændingstræ

Et minimum spændingstræ kan findes fra en vægtet graf ved at bruge algoritmerne nedenfor -

Prims algoritme
Kruskals algoritme

Lad os se en kort beskrivelse af begge ovenstående algoritmer.

Prims algoritme - Det er en grådig algoritme, der starter med et tomt træ. Det bruges til at finde minimumspændingstræet fra grafen. Denne algoritme finder den delmængde af kanter, der inkluderer hvert hjørne af grafen, således at summen af vægtene af kanterne kan minimeres.

websteder som coomeet

For at lære mere om prim's algoritme, kan du klikke på nedenstående link - https://www.javatpoint.com/prim-algorithm

Kruskals algoritme - Denne algoritme bruges også til at finde minimumspændingstræet for en forbundet vægtet graf. Kruskals algoritme følger også en grådig tilgang, som finder en optimal løsning på alle stadier i stedet for at fokusere på et globalt optimum.

For at lære mere om prim's algoritme, kan du klikke på nedenstående link - https://www.javatpoint.com/kruskal-algorithm

Så det handler om artiklen. Håber artiklen vil være nyttig og informativ for dig. Her har vi diskuteret spændingstræ og minimum spændingstræ sammen med deres egenskaber, eksempler og applikationer.

TechCodeview