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:

Gràfic no dirigit:Un gràfic no dirigit és un gràfic en què totes les arestes no apunten cap a cap direcció en particular, és a dir, no són unidireccionals; són bidireccionals. També es pot definir com un gràfic amb un conjunt de vèrtexs V i un conjunt d'arestes E, cada aresta connectant dos vèrtexs diferents.Gràfic connectat:Un graf connectat és un gràfic en el qual sempre existeix un camí des d'un vèrtex a qualsevol altre. Un gràfic està connectat si podem arribar a qualsevol vèrtex des de qualsevol altre vèrtex seguint arestes en qualsevol direcció.Gràfic dirigit:Els gràfics dirigits també es coneixen com a dígrafs. Un graf és un gràfic dirigit (o dígraf) si totes les arestes presents entre qualsevol vèrtex o node del gràfic estan dirigides o tenen una direcció definida.

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 n^n-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 5^5-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 n^n-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.