I denne vejledning lærer du om spændende træ og minimum spændende træ ved hjælp af eksempler og figurer.
Før vi lærer at spænde over træer, er vi nødt til at forstå to grafer: ikke-rettede grafer og tilsluttede grafer.
En ikke-rettet graf er en graf, hvor kanterne ikke peger i nogen retning (dvs. kanterne er tovejs).
Udirigeret graf
En forbundet graf er en graf, hvor der altid er en sti fra et toppunkt til ethvert andet toppunkt.
Forbundet graf
Spændende træ
Et spændende træ er en undergraf af en ikke-rettet tilsluttet graf, som inkluderer alle hjørnerne i grafen med et mindst muligt antal kanter. Hvis et toppunkt savnes, er det ikke et spændende træ.
Kanterne har måske ikke vægte tildelt.
Det samlede antal spændende træer med nhjørner, der kan oprettes ud fra en komplet graf, er lig med .n(n-2)
Hvis vi har det n = 4, er det maksimale antal mulige spændende træer lig med . Således kan 16 spændende træer dannes ud fra en komplet graf med 4 hjørner.44-2 = 16
Eksempel på et spændende træ
Lad os forstå det spændende træ med eksemplerne nedenfor:
Lad den oprindelige graf være:
Normal graf
Nogle af de mulige spændende træer, der kan oprettes fra ovenstående graf, er:
Et spændende træ 
Et spændende træ 
Et spændende træ 
Et spændende træ 
Et spændende træ 
Et spændende træ
Minimum spændende træ
Et minimum spændende træ er et spændende træ, hvor summen af vægten af kanterne er mindst mulig.
Eksempel på et spændende træ
Lad os forstå ovenstående definition ved hjælp af eksemplet nedenfor.
Den oprindelige graf er:
Vægtet graf
De mulige spændende træer fra ovenstående graf er:
Minimum træ - 1 
Minimum træ - 2 
Minimum træ - 3 
Minimum træ - 4
Det mindste spændende træ fra ovenstående spændende træer er:
Minimum spændende træ
Det mindste spændende træ fra en graf findes ved hjælp af følgende algoritmer:
- Prims algoritme
- Kruskals algoritme
Spændende træapplikationer
- Computer Network Routing Protocol
- Klyngeanalyse
- Planlægning af civilt netværk
Minimum spændende træ applikationer
- For at finde stier på kortet
- At designe netværk som telekommunikationsnetværk, vandforsyningsnetværk og elektriske net.
