Spanning Tree og Minimum Spanning Tree

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:

1. Prims algoritme
2. 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.