TRABAJO DE INVESTIGACIÓN
“ÁRBOLES”

꧁INTRODUCCIÓN꧂

Presentamos a continuación el informe solicitado, de dicho trabajo de investigación, definimos las consignas solicitadas, una por una; dicho trabajo fue realizado en grupo e integrado por "Ignacio Ibaigorria" y "Jose Ignacio Dominguez Ojeda".  El tema a tratar en el mismo, se trata de "Árboles y Grafos" de Matemática Discreta. Toda la información (Texto e Imágenes) fue recaudada  a través de paginas web, y libros digitales.

꧁Definición Árbol ꧂

 Árbol (Grafo). El árbol es una estructura grafoidea de gran aplicación dentro de varias ciencias dentro de las matemáticas y la computación, donde existen no pocas implementaciones de los mismos y usos; pero que sirve para modelar muchos otros aspectos en otros campos de la ciencia, la producción y la vida cotidiana.

Un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino

Sea un grafo G= <V,A> las siguientes propiedades son equivalentes entre sí:

·         G es un árbol.

·         G es simple, conexo y sin ciclos.

·         G es conexo y |V|=n entonces |A|=n-1.

Normalmente se identifica a un vértice como raíz o padre de la cual deriva aristas a otros nodos que se llaman hijos de dicho padre o raíz. A los nodos que no tienen descendencia se les llama hojas.

Referencias

 Grafo: Un grafo es un conjunto de objetos llamados nodos o vértices, que pueden estar unidos (conectados) por líneas llamada aristas. https://matematicasies.com/Grafos-Definicion 
Conexo: Un grafo G es conexo si dados cualesquiera dos vértices v y w en G, existe un camino de v a w. (https://www.monografias.com/trabajos98/arboles-y-grafos/arboles-y-grafos.shtml)

꧁ ¿Para qué se utilizan los Árboles?  ꧂

En ciencias de la computación los árboles son particularmente útiles. Por ejemplo se utilizan para organizar información de tal modo que sea posible efectuar eficientemente operaciones que atañan a esa información. Para construir algoritmos eficientes para localizar artículos en una lista. Para construir códigos eficientes para almacenar y transmitir datos. Para modelar procedimientos que son llevados a cabo al utilizar una secuencia de decisiones.

Los árboles son modelos de gran utilidad pues su representación normalmente alude a una estructura jerárquica y este es una de sus principales usos. También se usan mucho 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.

꧁Ejemplos de Árboles꧂

꧁Tipos de recorridos de los árboles꧂

Según el libro de T. Parajan nos dice que: El recorrido de un árbol es el proceso para recorrer (desplazarse a lo largo) un árbol de manera sistemática a fin de que cada vértice se visite y procese exactamente una vez. Hay tres métodos para recorrer un árbol binario a saber recorridos de preorden, de inorden y de posorden.

Recorrido preorden:

Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

1.  Visite la raíz

2. Atraviese el sub-árbol izquierdo

3. Atraviese el sub-árbol derecho

Preorden: ABDGEHICFJK

Recorrido inorden:

Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo.

2. Visite la raíz.                         

3. Atraviese el sub-árbol derecho.

Inorden: GDBHEIACJKF

Recorrido posorden:

Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo

2. Atraviese el sub-árbol derecho

3. Visite la raíz                                

Postorden: GDHIEBKJFCA

Árbol genérico

Para recorrer un árbol no vacío en orden de profundidad-primero, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.      Realice la operación pre-orden

2.      Para i=1 a n-1 haga

1.      Visite al hijo[i], si existe

2.      Realice la operación in-orden

3.      Visite al hijo[n], si existe

4.      Realice la operación post-orden

Referencias

Chavez, A. (2019). Árboles y grafos. [online] Es.slideshare.net. Available at: https://es.slideshare.net/AlexisChavez1/rboles-y-grafos [Accessed 31 May 2019].

Claverol, M., Simó, E. and Zaragozá, M. (1999). Matemática Discreta TEORIA DE GRAFOS. [online] Ocw.upc.edu. Available at: https://ocw.upc.edu/sites/all/modules/ocw/estadistiques/download.php?file=340370/2012/1/54137/grafos-teoria-4760.pdf [Accessed 31 May 2019].

Ecured.cu. (2019). Árbol (Grafo) - EcuRed. [online] Available at: https://www.ecured.cu/%C3%81rbol_(Grafo) [Accessed 31 May 2019].

Es.wikipedia.org. (2019). Recorrido de árboles. [online] Available at: https://es.wikipedia.org/wiki/Recorrido_de_%C3%A1rboles [Accessed 31 May 2019].

Llanos Tintaya, L. (2013). Recorrido y busqueda en árboles. [online] Profesorezequielruizgarcia.files.wordpress.com. Available at: https://profesorezequielruizgarcia.files.wordpress.com/2017/06/recorrido-y-busqueda-arboles.pdf [Accessed 31 May 2019].