En aquest article, parlarem de l'arbre spanning i l'arbre spanning mínim. Però abans de moure's directament cap a l'arbre allargat, primer veiem una breu descripció del gràfic i els seus tipus.
Gràfic
Un gràfic es pot definir com un grup de vèrtexs i arestes per connectar aquests vèrtexs. Els tipus de gràfics es donen de la següent manera:
Ara, anem cap a l'arbre que abasta el tema.
Què és un arbre spanning?
Un arbre spanning es pot definir com el subgraf d'un graf connectat no dirigit. Inclou tots els vèrtexs juntament amb el menor nombre possible d'arestes. Si s'omet algun vèrtex, no és un arbre allargat. Un arbre spanning és un subconjunt del gràfic que no té cicles i tampoc no es pot desconnectar.
Un arbre spanning consta de (n-1) arestes, on 'n' és el nombre de vèrtexs (o nodes). Les vores de l'arbre spanning poden tenir o no pes assignats. Tots els possibles arbres abastants creats a partir del gràfic donat G tindrien el mateix nombre de vèrtexs, però el nombre d'arestes de l'arbre spanning seria igual al nombre de vèrtexs del gràfic donat menys 1.
Un gràfic complet no dirigit pot tenir nn-2 nombre d'arbres spanning on n és el nombre de vèrtexs del gràfic. Suposem, si n = 5 , seria el nombre màxim d'arbres allargats possibles 55-2= 125.
Aplicacions de l'arbre spanning
Bàsicament, s'utilitza un arbre spanning per trobar un camí mínim per connectar tots els nodes del gràfic. Algunes de les aplicacions habituals de l'arbre spanning s'enumeren a continuació:
- Anàlisi de clústers
- Planificació de la xarxa civil
- Protocol d'encaminament de la xarxa informàtica
Ara, anem a entendre l'arbre spanning amb l'ajuda d'un exemple.
Exemple de Spanning Tree
Suposem que el gràfic és -
Com s'ha comentat anteriorment, un arbre spanning conté el mateix nombre de vèrtexs que el gràfic, el nombre de vèrtexs del gràfic anterior és 5; per tant, l'arbre spanning contindrà 5 vèrtexs. Les arestes de l'arbre spanning seran iguals al nombre de vèrtexs del gràfic menys 1. Per tant, hi haurà 4 arestes a l'arbre spanning.
Alguns dels possibles arbres abastants que es crearan a partir del gràfic anterior es donen de la següent manera:
Propietats de spanning-tree
Algunes de les propietats de l'arbre spanning es donen de la següent manera:
- Hi pot haver més d'un arbre d'abast d'un gràfic connectat G.
- Un arbre spanning no té cicles ni bucles.
- Un arbre spanning és mínimament connectat, per tant, eliminar una vora de l'arbre farà que el gràfic es desconnecti.
- Un arbre spanning és màxim acíclic, així que afegir una vora a l'arbre crearà un bucle.
- Hi pot haver un màxim nn-2 nombre d'arbres que es poden crear a partir d'un gràfic complet.
- Un arbre spanning té n-1 vores, on 'n' és el nombre de nodes.
- Si el gràfic és un gràfic complet, aleshores es pot construir l'arbre que abasta eliminant les arestes màximes (e-n+1), on 'e' és el nombre d'arestes i 'n' és el nombre de vèrtexs.
Per tant, un arbre spanning és un subconjunt del graf connectat G, i no hi ha cap arbre spanning d'un graf desconnectat.
Arbre spanning mínim
Un arbre spanning mínim es pot definir com l'arbre spanning en el qual la suma dels pesos de la vora és mínima. El pes de l'arbre spanning és la suma dels pesos donats a les vores de l'arbre spanning. En el món real, aquest pes es pot considerar com la distància, la càrrega de trànsit, la congestió o qualsevol valor aleatori.
Exemple d'arbre spanning mínim
Anem a entendre l'arbre mínim amb l'ajuda d'un exemple.
La suma de les vores del gràfic anterior és 16. Ara, alguns dels possibles arbres abastants creats a partir del gràfic anterior són -
Per tant, l'arbre abastant mínim que es selecciona dels arbres abastants anteriors per al gràfic ponderat donat és -
Aplicacions de l'arbre spanning mínim
Les aplicacions de l'arbre spanning mínim es donen de la següent manera:
- L'arbre spanning mínim es pot utilitzar per dissenyar xarxes de subministrament d'aigua, xarxes de telecomunicacions i xarxes elèctriques.
- Es pot utilitzar per trobar camins al mapa.
Algorismes per a l'arbre d'abast mínim
Es pot trobar un arbre d'abast mínim a partir d'un gràfic ponderat utilitzant els algorismes que s'indiquen a continuació:
- Algoritme de Prim
- Algoritme de Kruskal
Vegem una breu descripció dels dos algorismes enumerats anteriorment.
algorisme de Prim - És un algorisme cobdiciós que comença amb un arbre allargat buit. S'utilitza per trobar l'arbre d'abast mínim del gràfic. Aquest algorisme troba el subconjunt d'arestes que inclou cada vèrtex del gràfic de manera que la suma dels pesos de les arestes es pugui minimitzar.
port d'escolta
Per obtenir més informació sobre l'algoritme del prim, podeu fer clic a l'enllaç següent: https://www.javatpoint.com/prim-algorithm
algorisme de Kruskal - Aquest algorisme també s'utilitza per trobar l'arbre d'abast mínim per a un gràfic ponderat connectat. L'algorisme de Kruskal també segueix un enfocament cobdiciós, que troba una solució òptima en cada etapa en lloc de centrar-se en un òptim global.
Per obtenir més informació sobre l'algoritme del prim, podeu fer clic a l'enllaç següent: https://www.javatpoint.com/kruskal-algorithm
Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu. Aquí, hem parlat de l'arbre spanning i l'arbre spanning mínim juntament amb les seves propietats, exemples i aplicacions.