1. Què és Arbre i Bosc?
Arbre
- En teoria de grafs, a arbre és un graf no dirigit, connectat i acíclic . En altres paraules, un graf connectat que no conté ni un sol cicle s'anomena arbre.
- Un arbre representa una estructura jeràrquica en forma gràfica.
- Els elements dels arbres s'anomenen els seus nodes i les vores de l'arbre s'anomenen branques.
- Un arbre amb n vèrtexs té (n-1) arestes.
- Els arbres proporcionen moltes aplicacions útils tan simples com un arbre genealògic fins a tan complexes com els arbres en estructures de dades de la informàtica.
- A full en un arbre hi ha un vèrtex de grau 1 o qualsevol vèrtex que no tingui fills s'anomena fulla.
Exemple
En l'exemple anterior, tots són arbres amb menys de 6 vèrtexs.
Bosc
En teoria de grafs, a bosc és un graf acíclic no dirigit, desconnectat . En altres paraules, una col·lecció disjunta d'arbres es coneix com a bosc. Cada component d'un bosc és un arbre.
Exemple
El gràfic anterior sembla dos subgràfics, però és un únic gràfic desconnectat. No hi ha cicles al gràfic anterior. Per tant, és un bosc.
2. Propietats dels arbres
- Tot arbre que tingui almenys dos vèrtexs ha de tenir almenys dues fulles.
- Els arbres tenen moltes caracteritzacions:
Sigui T un gràfic amb n vèrtexs, aleshores les afirmacions següents són equivalents:- T és un arbre.
- T no conté cicles i té n-1 arestes.
- T està connectat i té (n -1) aresta.
- T és un gràfic connectat i cada aresta és una aresta tallada.
- Dos vèrtexs qualsevol del gràfic T estan connectats per exactament un camí.
- T no conté cicles, i per a qualsevol aresta nova e, el gràfic T+ e té exactament un cicle.
- Cada vora d'un arbre és tallada.
- Afegir una vora a un arbre defineix exactament un cicle.
- Cada gràfic connectat conté un arbre spanning.
- Cada arbre té almenys dos vèrtexs de grau dos.
3. Spanning Tree
A arbre allargat en un graf connectat G és un subgraf H de G que inclou tots els vèrtexs de G i també és un arbre.
Exemple
Considereu el següent gràfic G:
A partir del gràfic anterior G podem implementar els següents tres arbres H:
Mètodes per trobar l'arbre spanning
Podem trobar l'arbre spanning sistemàticament utilitzant qualsevol dels dos mètodes:
- Mètode de tall
- Mètode de construcció
1. Mètode de tall
- Comenceu a triar qualsevol cicle al gràfic G.
- Traieu una de les vores del cicle.
- Repetiu aquest procés fins que no quedin cicles.
Exemple
- Considereu un gràfic G,
- Si eliminem la vora ac que destrueix el cicle a-d-c-a del gràfic anterior, obtenim el gràfic següent:
- Traieu la vora cb, que destrueix el cicle a-d-c-b-a del gràfic anterior i obtenim el gràfic següent:
- Si eliminem l'aresta ec, que destrueix el cicle d-e-c-d del gràfic anterior, obtenim el següent arbre allargant:
2. Mètode de construcció
- Seleccioneu les vores del gràfic G d'una en una. Es creen de tal manera que no hi hagi cicles.
- Repetiu aquest procés fins que s'incloguin tots els vèrtexs.
Exemple
Considereu el següent gràfic G,
- Trieu la vora ab ,
- Trieu la vora de ,
- Després d'això, trieu la vora ec ,
- A continuació, trieu la vora cb , aleshores finalment obtenim el següent arbre spanning:
Rang del circuit
El nombre d'arestes que hem d'esborrar de G per obtenir un arbre allargant.
Arbre spanning G = m- (n-1) , que s'anomena el rang del circuit de G.
Where, m = No. of edges. n = No. of vertices.
Exemple
Al gràfic anterior, arestes m = 7 i vèrtexs n = 5
Aleshores el rang del circuit és,
G = m - (n - 1) = 7 - (5 - 1) = 3