Content

• Gràfic de comparació
• Definició de Tree
• Propietats de l'arbre:
• Definició de gràfic
• Propietats d’un gràfic:
• Conclusió

L'arbre i el gràfic entren dins de la categoria d'estructura de dades no lineals on l'arbre ofereix una forma molt útil de representar una relació entre els nodes en una estructura jeràrquica i el gràfic segueix un model de xarxa. L'arbre i el gràfic es diferencien pel fet que una estructura de l'arbre s'ha de connectar i mai pot tenir bucles, mentre que al gràfic no hi ha restriccions.

Una estructura de dades no lineal consisteix en una col·lecció d’elements que es distribueixen en un pla que significa que no hi ha cap seqüència entre els elements ja que existeix en una estructura de dades lineal.

1. 1. Gràfic de comparació
   2. Definició
   3. Diferències claus
   4. Conclusió

Gràfic de comparació

Bases per a la comparació	Arbre	Gràfic
Camí	Només un entre dos vèrtexs.	Es permet més d'un camí.
Node arrel	Té exactament un node arrel.	El gràfic no té un node arrel.
Loops	No es permeten bucles.	El gràfic pot tenir bucles.
Complexitat	Menys complex	Més complexa comparativament
Tècniques transversals	Pre-comanda, comanda i comanda post.	Primera cerca d’amplada i primera cerca de profunditat.
Nombre de vores	n-1 (on n és el nombre de nodes)	Sense definir
Tipus de model	Jeràrquic	Xarxa

Definició de Tree

A arbre és una col·lecció finita d’elements de dades que normalment s’anomenen nodes. Com s'ha esmentat anteriorment, un arbre és una estructura de dades no lineal que organitza els elements de dades en un ordre ordenat. S'utilitza per mostrar una estructura jeràrquica entre els diversos elements de dades i organitzar les dades en branques que relacionen la informació. L'addició d'una nova vora en un arbre produeix una formació del bucle o circuit.

Hi ha diversos tipus d’arbres com un arbre binari, arbre de cerca binària, arbre AVL, arbre binari roscat, arbre B, etc. Compressió de dades, emmagatzematge d’arxius, manipulació de l’expressió aritmètica i arbres de jocs són algunes de l’aplicació de l’arbre. estructura de dades.

Propietats de l'arbre:

• Hi ha un node designat a la part superior de l'arbre conegut com a arrel de l'arbre.
• La resta de dades de dades es divideixen en subconjunts separats que es coneixen com a subarbres.
• L'arbre s'amplia en alçada cap al fons.
• S'ha de connectar un arbre, cosa que significa que hi ha d'haver una ruta des d'una arrel fins a tots els altres nodes.
• No conté cap bucle.
• Un arbre té n-1 arestes.

Hi ha diversos termes associats a arbres com ara node terminal, vora, nivell, grau, profunditat, bosc, etc. Entre aquests termes, alguns descrits a continuació.

• Vora - Línia que connecta dos nodes.
• Nivell - Un arbre es divideix en nivells de manera que el node arrel estigui al nivell 0. Aleshores, els seus fills immediats estan al nivell 1 i els fills immediats al nivell 2 i així fins al node terminal o full.
• Titulació - És el nombre de subtreus d'un node en un arbre determinat.
• Profunditat - És el nivell màxim de qualsevol node en un arbre determinat i també conegut com a alçada.
• Node terminal - El node de nivell més alt és el node terminal mentre que altres nodes excepte el terminal i el node arrel es coneixen com a nodes no terminals.

Definició de gràfic

A gràfic és també una estructura de dades matemàtica no lineal que pot representar diversos tipus d'estructura física. Consta d'un grup de vèrtexs (o nodes) i un conjunt d'arcs que connecten els dos vèrtexs. Els vèrtexs del gràfic es representen com a punt o cercles i les arestes es mostren com a arcs o segments de línia. Una vora està representada per E (v, w) on v i w són els parells de vèrtexs. L’eliminació d’una vora d’un circuit o gràfic connectat crea un subgraf que és un arbre.

Els gràfics es classifiquen en diverses categories com ara dirigits, no dirigits, connectats, no connectats, simples i múltiples gràfics. Algunes de les aplicacions de l'estructura de dades gràfiques són la xarxa d'informàtica, el sistema de transport, el gràfic de xarxa social, els circuits elèctrics i la planificació de projectes. També s'utilitza en la tècnica de gestió, anomenada com a PERT (tècnica d’avaluació i revisió del programa) i CPM (mètode de ruta crítica) en què s’analitza l’estructura gràfica.

Propietats d’un gràfic:

• Un vèrtex d'un gràfic es pot connectar a qualsevol nombre d'altres vèrtexs utilitzant vores.
• Una vora es pot dirigir o dirigir.
• Es pot ponderar una vora.

En el gràfic també utilitzem diversos termes com a vèrtex adjacents, ruta, cicle, grau, gràfic connectat, gràfic complet, gràfic ponderat, etc. Entenem alguns d'aquests termes.

• Vèrtexs adjacents - Un vèrtex a és adjacent al vèrtex b si hi ha una vora (a, b) o (b, a).
• Camí - Un camí des d'un vèrtex aleatori w és una seqüència contínua de vèrtexs.
• Cicle - És un camí on el primer i el darrer vèrtex són iguals.
• Titulació - És un número de vores incident en un vèrtex.
• Gràfic connectat - Si existeix un camí des d'un vèrtex aleatori a qualsevol altre vèrtex, aquest gràfic es coneix com a gràfic connectat.

1. En un arbre només hi ha un camí entre els dos vèrtexs mentre que un gràfic pot tenir vies unidireccionals i bidireccionals entre els nodes.
2. A l’arbre, hi ha exactament un node arrel i tots els fills poden tenir només un pare. En contraposició, en un gràfic, no hi ha cap concepte del node arrel.
3. Un arbre no pot tenir bucles i auto-loops mentre que el gràfic pot tenir bucles i auto-loops.
4. Els gràfics són més complicats, ja que pot tenir bucles i auto-bucles. En canvi, els arbres són simples en comparació amb el gràfic.
5. L’arbre es creua mitjançant tècniques de pre-comanda, ordre i post-comanda. D’altra banda, per al creuament de gràfics, utilitzem BFS (Breadth First Search) i DFS (Profund First Search).
6. Un arbre pot tenir n-1 arestes. Per contra, al gràfic, no hi ha un nombre d'arcs predefinit, i depèn del gràfic.
7. Un arbre té una estructura jeràrquica mentre que el gràfic té un model de xarxa.

Conclusió

El gràfic i l'arbre són l'estructura de dades no lineal que s'utilitza per resoldre diversos problemes complexos. Un gràfic és un grup de vèrtexs i arestes on una vora connecta un parell de vèrtexs mentre que un arbre es considera un gràfic mínimament connectat que ha d'estar connectat i lliure de bucles.