I denne opplæringen vil du lære om å spenne tre og minimum spennende tre ved hjelp av eksempler og figurer.
Før vi lærer om spennende trær, må vi forstå to grafer: ikke-rettet grafer og sammenhengende grafer.
En ikke-rettet graf er en graf der kantene ikke peker i noen retning (dvs. kantene er toveis).
Udirigert graf
En tilkoblet graf er en graf der det alltid er en bane fra et toppunkt til et hvilket som helst annet toppunkt.
Tilkoblet graf
Spennende tre
Et spennende tre er en undergraf av en ikke-rettet tilkoblet graf, som inkluderer alle toppunktene i grafen med et minimum mulig antall kanter. Hvis et toppunkt blir savnet, er det ikke et spennende tre.
Kantene kan ha vekter tildelt eller ikke.
Totalt antall spennende trær med nhjørner som kan opprettes fra en komplett graf er lik .n(n-2)
Hvis vi har det n = 4, er det maksimale antallet mulige spennende trær lik . Dermed kan 16 spennende trær dannes fra en komplett graf med 4 hjørner.44-2 = 16
Eksempel på et spennende tre
La oss forstå det spennende treet med eksempler nedenfor:
La den opprinnelige grafen være:
Normal graf
Noen av de mulige spennende trærne som kan opprettes fra grafen ovenfor er:
Et spennende tre 
Et spennende tre 
Et spennende tre 
Et spennende tre 
Et spennende tre 
Et spennende tre
Minimum spennende tre
Et minimum spennende tre er et spennende tre hvor summen av vekten av kantene er minst mulig.
Eksempel på et spennende tre
La oss forstå definisjonen ovenfor ved hjelp av eksemplet nedenfor.
Den første grafen er:
Vektet graf
De mulige spennende trærne fra grafen ovenfor er:
Minimum spennende tre - 1 
Minimum spennende tre - 2 
Minimum spennende tre - 3 
Minimum spennende tre - 4
Det minste spennende treet fra ovennevnte spennende trær er:
Minimum spennende tre
Det minste spennende treet fra en graf er funnet ved hjelp av følgende algoritmer:
- Prims algoritme
- Kruskals algoritme
Spanning Tree Applications
- Computer Network Routing Protocol
- Klyngeanalyse
- Sivil nettverksplanlegging
Minimum Spanning Tree Applications
- For å finne stier på kartet
- Å designe nettverk som telekommunikasjonsnett, vannforsyningsnett og elektriske nett.
