Spanning Tree och Minimum Spanning Tree

I den här handledningen lär du dig att spänna träd och minsta spännande träd med hjälp av exempel och figurer.

Innan vi lär oss om spännande träd måste vi förstå två grafer: oriktade grafer och anslutna grafer.

En oriktad graf är en graf i vilken kanterna inte pekar i någon riktning (dvs. kanterna är dubbelriktade).

Oriktad graf

En ansluten graf är en graf där det alltid finns en väg från ett toppunkt till något annat toppunkt.

Ansluten graf

Spanning Tree

Ett spännande träd är en underdiagram av en oriktad ansluten graf, som inkluderar alla hörn i diagrammet med ett minsta möjliga antal kanter. Om ett toppunkt saknas är det inte ett spännande träd.

I kanterna kan vikter tilldelas eller inte.

Det totala antalet spännande träd med nhörn som kan skapas från en komplett graf är lika med .n(n-2)

Om vi ​​har det n = 4är det maximala antalet möjliga spännande träd lika med . Således kan 16 spännande träd bildas från ett komplett diagram med fyra hörn.44-2 = 16

Exempel på ett spännande träd

Låt oss förstå det spännande trädet med exempel nedan:

Låt originalgrafen vara:

Normal graf

Några av de möjliga spännande träd som kan skapas från ovanstående diagram är:

Ett spännande träd Ett spännande träd Ett spännande träd Ett spännande träd Ett spännande träd Ett spännande träd

Minsta spännande träd

Ett minimalt spännande träd är ett spännande träd där summan av vikten på kanterna är så minimal som möjligt.

Exempel på ett spännande träd

Låt oss förstå definitionen ovan med hjälp av exemplet nedan.

Den ursprungliga grafen är:

Vägt diagram

De möjliga spännande träd från ovanstående diagram är:

Minsta spännande träd - 1 Minsta spännande träd - 2 Minsta spännande träd - 3 Minsta spännande träd - 4

Det minsta spännande trädet från ovanstående spännande träd är:

Minsta spännande träd

Det minsta spännande trädet från ett diagram hittas med följande algoritmer:

1. Prims algoritm
2. Kruskals algoritm

Spännande trädapplikationer

• Datornätverk Routing Protocol
• Klusteranalys
• Planering av civila nätverk

Minsta spännande träd

• För att hitta vägar på kartan
• Att utforma nätverk som telenät, vattenförsörjningsnät och elnät.