EXPONIENDO A ALVARITO
No respeta la propiedad privada de los artículos. Usen el formato físico, no confíen en el digital
Autor: maxsalvil
Girafa
La girafa és l'animal més alt del món, coneguda pel seu llarg coll i la seva capacitat per menjar fulles dels arbres més alts.
Autor: Antonio
GRAF
Un graf consta de dos conjunts: • Un conjunt V de punts anomenats nusos, nodes o vèrtexs. • Un conjunt E de línies que uneixen parelles de nusos i reben el nom d’arestes (si no són dirigides) o arcs (si són dirigides). Figura 1: Exemple de graf dirigit 2.4.TERMINOLOGIA Un graf és no dirigit o simètric si les línies que uneixen parelles de nusos no tenen direcció, mentre que és dirigit o digraf si les línies tenen una direcció definida. Successors d’un vèrtex són tots aquells vèrtexs als quals es pot accedir a través d’una aresta o d’un arc. A C D B E F Estructures de dades i algorítmica - 8 - Antecessors d’un vèrtex són tots aquells vèrtexs que poden accedir al node en qüestió a través d’una aresta o d’un arc. En grafs no dirigits s’utilitza el terme adjacents o veïns ja que no hi ha distinció entre antecessors i successors. Rep el nom de grau d’un nus, g(v), el nombre d’arestes que el contenen. Si el grau és 0 llavors es diu que el nus és aïllat. Reben el nom d’extrems d’una aresta e=[u, v] els nusos u i v. Un llaç és una aresta o un arc que comença i acaba en el mateix node. Si un graf no té llaços rep el nom de graf simple. En alguna bibliografia s’anomenen pseudo-grafs als grafs que contenen llaços. Un camí P = (v0 ,v1 ,v2 ,.......vn ) és una seqüència de vèrtexs que es troben enllaçats per arcs. En grafs no dirigits es parlarà de cadenes. Longitud o cardinalitat d’un camí o d’una cadena és el nombre d’arcs o arestes que el formen. Un camí de longitud n tindrà n+1 nusos. Un circuït és un camí tancat. En grafs no dirigits és parla de cicles. Un camí és simple si no repeteix arcs. Un camí és elemental si no repeteix vèrtexs. Un circuït és hamiltonià si passa un i només un cop per tots els vèrtexs del graf. Un circuït és eulerià si passa un i només un cop per tots els arcs del graf. Un graf és connex si existeix un camí entre qualsevol parella dels seus nusos. En els grafs, la informació es guarda normalment en els vèrtexs, mentre que les arestes representen relacions entre nusos. Si en un graf també es guarda informació en les arestes, llavors es diu que el graf està etiquetat, en cas contrari es diu que el graf no està etiquetat.
Autor: maxsalvil