Los árboles
corresponden a una de las subclases de grafos
de uso más amplio, particularmente en computación.
Los grafos se pueden clasificar
en dos grupos:
dirigidos y no dirigidos. Los arboles
forman parte de los no dirigidos.
Definición
En teoría de grafos, un árbol es un grafo
simple, conexo y que no
contiene ciclos en él, en donde dos vértices están conectados
por exactamente un
camino. Este impone una estructura jerárquica sobre una colección de objetos.
Además se compone de elementos llamados nodos,
de los cuales se distingue uno llamado raíz,
que es la base de los demás nodos. A los nodos
tambien se los suele llamar hojas
, y a las aristas que los unen, se las denomina ramas.
¿Para qué se
utilizan?
Estos sirven para organizar y relacionar
datos en una base de tipo jerárquica. Generalmente, suelen ser
utilizados para realizar escalas de orden jerárquico, en la modelación de
búsquedas o problemas que dependan de la representación de una búsqueda en un
espacio representable como un grafo.
Un ejemplo cotidiano puede ser la
utilización de este tipo de grafo para organizar un árbol genealógico. Donde la
raíz (dependiendo si es de la familia materna o paterna) serían nuestros abuelos,
en las hojas se encontrarían nuestros padres, tíos, hermanos y nosotros como
hijos, y las ramas serían las distintas uniones familiares.
Otro ejemplo se podría dar al momento de
organizar jerárquicamente una empresa. En la cima, estaría el jefe (o los
fundadores) como raíz, las hojas serían los distintos gerentes y empleados, y
las ramas serian la relación que tienen (de subordinado a superior).
Tipos de recorrido de un Árbol
Recorrido en preorden:
·
Visitar
la raíz
·
Recorrer
el subárbol izquierdo
·
Recorrer
el subárbol derecho
Recorrido en iroden:
·
Recorrer
el subárbol izquierdo
·
Visitar
la raíz
·
Recorrer
el subárbol derecho
Recorrido postden:
·
Recorrer
el subárbol izquierdo
·
Recorrer
el subárbol derecho
·
Visitar
la raíz
Bibliografía
·
Apuntes
del campus: Teoría de Grafos-Parte 1 y 2
Comentarios
Publicar un comentario