TechCodeview

I den här artikeln kommer vi att diskutera spännträdet och det minsta spännträdet. Men innan vi går direkt mot spännträdet, låt oss först se en kort beskrivning av grafen och dess typer.

Graf

En graf kan definieras som en grupp av hörn och kanter för att koppla samman dessa hörn. Typerna av grafer ges enligt följande -

Oriktat diagram:En oriktad graf är en graf där alla kanter inte pekar i någon speciell riktning, dvs. de är inte enkelriktade; de är dubbelriktade. Det kan också definieras som en graf med en uppsättning V-hörn och en uppsättning E-kanter, där varje kant förbinder två olika hörn.Ansluten graf:En sammankopplad graf är en graf där det alltid finns en väg från en vertex till vilken annan vertex som helst. En graf är sammankopplad om vi kan nå vilken vertex som helst från vilken annan vertex som helst genom att följa kanter i endera riktningen.Riktad graf:Riktade grafer är också kända som digrafer. En graf är en riktad graf (eller digraf) om alla kanter som finns mellan några hörn eller noder i grafen är riktade eller har en definierad riktning.

Låt oss nu gå mot ämnet som spänner över trädet.

Vad är ett spannträd?

Ett spännträd kan definieras som subgrafen till en oriktad sammankopplad graf. Den inkluderar alla hörn tillsammans med minsta möjliga antal kanter. Om någon vertex missas är det inte ett spännträd. Ett spännträd är en delmängd av grafen som inte har cykler, och det kan inte heller kopplas bort.

Ett spännträd består av (n-1) kanter, där 'n' är antalet hörn (eller noder). Kanterna på det spännande trädet kan ha vikter tilldelade eller inte. Alla möjliga spännträd som skapas från den givna grafen G skulle ha samma antal hörn, men antalet kanter i trädet skulle vara lika med antalet hörn i den givna grafen minus 1.

En fullständig oriktad graf kan ha n^n-2 antal spännande träd var n är antalet hörn i grafen. Antag, om n = 5 , skulle antalet maximalt möjliga spännträd vara 5^5-2= 125.

Tillämpningar av spännträdet

I grund och botten används ett spännträd för att hitta en minimiväg för att ansluta alla noder i grafen. Några av de vanliga applikationerna för spännträdet listas enligt följande -

• Klusteranalys
• Planering av civila nätverk
• Routingprotokoll för datornätverk

Låt oss nu förstå spännträdet med hjälp av ett exempel.

Exempel på spannande träd

Antag att grafen är -

Som diskuterats ovan innehåller ett spännträd samma antal hörn som grafen, antalet hörn i ovanstående graf är 5; därför kommer spännträdet att innehålla 5 hörn. Kanterna i spännträdet kommer att vara lika med antalet hörn i grafen minus 1. Så det kommer att finnas 4 kanter i spännträdet.

Några av de möjliga spännträden som kommer att skapas från ovanstående graf ges enligt följande -

Egenskaper för spann-träd

Några av egenskaperna hos det spännande trädet ges enligt följande -

• Det kan finnas mer än ett spännträd i en sammankopplad graf G.
• Ett spännträd har inga cykler eller loopar.
• Ett spännträd är minimalt ansluten, så att ta bort en kant från trädet kommer att göra grafen bortkopplad.
• Ett spännträd är maximalt acyklisk, så att lägga till en kant till trädet kommer att skapa en loop.
• Det kan finnas ett maximum n^n-2 antal spännande träd som kan skapas från en komplett graf.
• Ett spännträd har n-1 kanter, där 'n' är antalet noder.
• Om grafen är en komplett graf, kan spännträdet konstrueras genom att ta bort maximala (e-n+1) kanter, där 'e' är antalet kanter och 'n' är antalet hörn.

Så, ett spännträd är en delmängd av ansluten graf G, och det finns inget spännträd i en frånkopplad graf.

Minsta spann träd

Ett minimum spännträd kan definieras som det spännträd där summan av kantens vikter är minimum. Vikten av spännträdet är summan av vikterna som ges till kanterna av spännträdet. I den verkliga världen kan denna vikt betraktas som avstånd, trafikbelastning, trängsel eller något slumpmässigt värde.

Exempel på minsta spännträd

Låt oss förstå det minsta spännträdet med hjälp av ett exempel.

Summan av kanterna på grafen ovan är 16. Nu är några av de möjliga spännträden som skapas från grafen ovan -

Så det minsta spännträdet som väljs från ovanstående spännträd för den givna viktade grafen är -

Tillämpningar av minsta spännträd

Tillämpningarna av det minsta spännträdet ges enligt följande -

• Minsta spännträd kan användas för att designa vattenförsörjningsnät, telekommunikationsnätverk och elnät.
• Den kan användas för att hitta stigar på kartan.

Algoritmer för Minimum spaning tree

Ett minsta spännträd kan hittas från en viktad graf genom att använda algoritmerna nedan -

• Prims algoritm
• Kruskals algoritm

Låt oss se en kort beskrivning av båda algoritmerna ovan.

Prims algoritm - Det är en girig algoritm som börjar med ett tomt träd. Den används för att hitta det minsta spännträdet från grafen. Denna algoritm hittar delmängden av kanter som inkluderar varje vertex i grafen så att summan av kanternas vikter kan minimeras.

grå kod

För att lära dig mer om prim:s algoritm kan du klicka på länken nedan - https://www.javatpoint.com/prim-algorithm

Kruskals algoritm - Denna algoritm används också för att hitta det minsta spännträdet för en sammankopplad vägd graf. Kruskals algoritm följer också girigt tillvägagångssätt, som hittar en optimal lösning i varje steg istället för att fokusera på ett globalt optimum.

För att lära dig mer om prim:s algoritm kan du klicka på länken nedan - https://www.javatpoint.com/kruskal-algorithm

Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig. Här har vi diskuterat spaning tree och minimum spaning tree tillsammans med deras egenskaper, exempel och tillämpningar.