In dit artikel bespreken we de opspannende boom en de minimaal opspannende boom. Maar voordat we rechtstreeks naar de spanning tree gaan, bekijken we eerst een korte beschrijving van de grafiek en de typen ervan.

Grafiek

Een grafiek kan worden gedefinieerd als een groep hoekpunten en randen om deze hoekpunten met elkaar te verbinden. De soorten grafieken worden als volgt gegeven:

Ongerichte grafiek:Een ongerichte grafiek is een grafiek waarin alle randen niet naar een bepaalde richting wijzen, dat wil zeggen dat ze niet unidirectioneel zijn; ze zijn bidirectioneel. Het kan ook worden gedefinieerd als een grafiek met een reeks V-hoekpunten en een reeks E-randen, waarbij elke rand twee verschillende hoekpunten verbindt.Verbonden grafiek:Een verbonden graaf is een graaf waarin er altijd een pad bestaat van een hoekpunt naar een ander hoekpunt. Een grafiek is verbonden als we elk hoekpunt vanaf elk ander hoekpunt kunnen bereiken door randen in beide richtingen te volgen.Gerichte grafiek:Gerichte grafieken worden ook wel digraphs genoemd. Een grafiek is een gerichte grafiek (of digraph) als alle randen tussen hoekpunten of knooppunten van de grafiek gericht zijn of een gedefinieerde richting hebben.

Laten we nu naar het onderwerp overspannende boom gaan.

Wat is een opspannende boom?

Een spanning tree kan worden gedefinieerd als de subgraaf van een ongerichte verbonden graaf. Het omvat alle hoekpunten samen met het minst mogelijke aantal randen. Als er een hoekpunt wordt gemist, is het geen opspannende boom. Een spanning tree is een subset van de grafiek die geen cycli heeft, en kan ook niet worden losgekoppeld.

Een spanning tree bestaat uit (n-1) randen, waarbij 'n' het aantal hoekpunten (of knooppunten) is. Aan de randen van de opspannende boom kunnen al dan niet gewichten worden toegewezen. Alle mogelijke opspannende bomen die uit de gegeven grafiek G zijn gemaakt, zouden hetzelfde aantal hoekpunten hebben, maar het aantal randen in de opspannende boom zou gelijk zijn aan het aantal hoekpunten in de gegeven grafiek minus 1.

Een volledige ongerichte grafiek kan dit hebben N^n-2 aantal opspannende bomen waar N is het aantal hoekpunten in de grafiek. Stel, als n = 5 , zou het aantal maximaal mogelijke opspannende bomen zijn 5^5-2= 125.

Toepassingen van de spanningsboom

Kortom, een spanning tree wordt gebruikt om een ​​minimumpad te vinden om alle knooppunten van de grafiek met elkaar te verbinden. Enkele veel voorkomende toepassingen van de spanning tree worden als volgt opgesomd:

• Clusteranalyse
• Civiele netwerkplanning
• Routeringsprotocol voor computernetwerken

Laten we nu de spanningsboom begrijpen met behulp van een voorbeeld.

Voorbeeld van een spanningsboom

Stel dat de grafiek -

Zoals hierboven besproken bevat een spanning tree hetzelfde aantal hoekpunten als de grafiek; het aantal hoekpunten in de bovenstaande grafiek is 5; daarom zal de spanning tree 5 hoekpunten bevatten. De randen in de opspannende boom zijn gelijk aan het aantal hoekpunten in de grafiek min 1. Er zijn dus 4 randen in de opspannende boom.

Enkele van de mogelijke opspannende bomen die uit de bovenstaande grafiek zullen worden gemaakt, worden als volgt gegeven:

Eigenschappen van spanning-tree

Enkele eigenschappen van de opspannende boom worden als volgt gegeven:

• Er kan meer dan één opspannende boom van een verbonden graaf G zijn.
• Een opspannende boom heeft geen cycli of lus.
• Een opspannende boom is dat wel minimaal verbonden, dus als u één rand uit de boom verwijdert, wordt de grafiek verbroken.
• Een opspannende boom is dat wel maximaal acyclisch, dus als je één rand aan de boom toevoegt, ontstaat er een lus.
• Er kan een maximum zijn N^n-2 aantal opspannende bomen dat kan worden gemaakt op basis van een volledige grafiek.
• Een opspannende boom heeft dat wel n-1 randen, waarbij 'n' het aantal knooppunten is.
• Als de grafiek een volledige grafiek is, kan de opspannende boom worden geconstrueerd door de maximale (e-n+1) randen te verwijderen, waarbij 'e' het aantal randen is en 'n' het aantal hoekpunten.

Een opspannende boom is dus een deelverzameling van de verbonden graaf G, en er is geen opspannende boom van een niet-verbonden graaf.

Minimaal overspannende boom

Een minimaal opspannende boom kan worden gedefinieerd als de opspannende boom waarin de som van de gewichten van de rand minimaal is. Het gewicht van de opspannende boom is de som van de gewichten die aan de randen van de opspannende boom worden gegeven. In de echte wereld kan dit gewicht worden beschouwd als de afstand, verkeersbelasting, congestie of een willekeurige waarde.

Voorbeeld van een minimaal opspannende boom

Laten we de minimaal opspannende boom begrijpen met behulp van een voorbeeld.

De som van de randen van de bovenstaande grafiek is 16. Enkele van de mogelijke opspannende bomen die op basis van de bovenstaande grafiek zijn gemaakt, zijn -

Dus de minimaal opspannende boom die wordt geselecteerd uit de bovenstaande opspannende bomen voor de gegeven gewogen grafiek is -

Toepassingen van minimaal opspannende boom

De toepassingen van de minimaal opspannende boom worden als volgt gegeven:

• De minimaal opspannende boom kan worden gebruikt om watervoorzieningsnetwerken, telecommunicatienetwerken en elektriciteitsnetwerken te ontwerpen.
• Het kan worden gebruikt om paden op de kaart te vinden.

Algoritmen voor minimaal opspannende boom

Een minimaal opspannende boom kan worden gevonden uit een gewogen grafiek met behulp van de onderstaande algoritmen:

• Het algoritme van Prim
• Het algoritme van Kruskal

Laten we een korte beschrijving bekijken van beide hierboven genoemde algoritmen.

Prim's algoritme - Het is een hebzuchtig algoritme dat begint met een lege opspannende boom. Het wordt gebruikt om de minimaal opspannende boom uit de grafiek te vinden. Dit algoritme vindt de subset van randen die elk hoekpunt van de grafiek omvat, zodat de som van de gewichten van de randen kan worden geminimaliseerd.

postordertraject

Voor meer informatie over het algoritme van de prim kunt u op de onderstaande link klikken: https://www.javatpoint.com/prim-algorithm

Kruskal's algoritme - Dit algoritme wordt ook gebruikt om de minimaal opspannende boom voor een verbonden gewogen grafiek te vinden. Het algoritme van Kruskal volgt ook een hebzuchtige aanpak, die in elke fase een optimale oplossing vindt in plaats van zich te concentreren op een mondiaal optimale oplossing.

Voor meer informatie over het algoritme van de prim kunt u op de onderstaande link klikken: https://www.javatpoint.com/kruskal-algorithm

Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn. Hier hebben we de opspannende boom en de minimaal opspannende boom besproken, samen met hun eigenschappen, voorbeelden en toepassingen.