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:
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 Nn-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 55-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 Nn-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.