Spanning Tree en Minimum Spanning Tree

In deze tutorial leert u aan de hand van voorbeelden en figuren over spanning tree en minimum spanning tree.

Voordat we leren over spanning-trees, moeten we twee grafieken begrijpen: ongerichte grafieken en verbonden grafieken.

Een ongerichte graaf is een grafiek waarin de randen niet in een richting wijzen (dwz de randen zijn bidirectioneel).

Ongerichte grafiek

Een verbonden graaf is een graaf waarin er altijd een pad is van een hoekpunt naar een ander hoekpunt.

Verbonden grafiek

Boom overspannen

Een opspannende boom is een subgrafiek van een ongerichte verbonden graaf, die alle hoekpunten van de graaf omvat met een minimaal mogelijk aantal randen. Als een hoekpunt wordt gemist, is het geen opspannende boom.

Aan de randen kunnen al dan niet gewichten zijn toegewezen.

Het totale aantal opspannende bomen met nhoekpunten dat kan worden gemaakt op basis van een volledige grafiek is gelijk aan .n(n-2)

Als we dat hebben gedaan n = 4, is het maximale aantal mogelijke opspannende bomen gelijk aan . Zo kunnen 16 opspannende bomen worden gevormd uit een complete grafiek met 4 hoekpunten.44-2 = 16

Voorbeeld van een overspanningsboom

Laten we de spanning tree begrijpen met onderstaande voorbeelden:

Laat de originele grafiek zijn:

Normale grafiek

Enkele van de mogelijke opspannende bomen die kunnen worden gemaakt op basis van de bovenstaande grafiek zijn:

Een spanning tree A spanning tree A spanning tree A spanning tree A spanning tree A spanning tree

Minimale overspanningsboom

Een minimum spanning tree is een spanning tree waarbij de som van het gewicht van de randen zo min mogelijk is.

Voorbeeld van een overspanningsboom

Laten we de bovenstaande definitie begrijpen met behulp van het onderstaande voorbeeld.

De eerste grafiek is:

Gewogen grafiek

De mogelijke opspannende bomen uit de bovenstaande grafiek zijn:

Minimale spanning tree - 1 Minimale spanning tree - 2 Minimale spanning tree - 3 Minimale spanning tree - 4

De minimale opspannende boom van de bovenstaande opspannende bomen is:

Minimale opspannende boom

De minimale spanning tree uit een grafiek wordt gevonden met behulp van de volgende algoritmen:

1. Prim's algoritme
2. Het algoritme van Kruskal

Tree-toepassingen overspannen

• Computer Network Routing Protocol
• Clusteranalyse
• Planning van civiele netwerken

Minimale overspanningsboomtoepassingen

• Om paden op de kaart te vinden
• Om netwerken te ontwerpen zoals telecommunicatienetwerken, watervoorzieningsnetwerken en elektriciteitsnetten.