Introduccion: ¿Que son los grafos?

Introducción:

Para poder hablar de Árboles, primero debemos saber lo que es un grafo: es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Su definición, de manera más teórica es la siguiente:

“Sea V un conjunto finito no vacío, y sea E C V x V. El par (V, E) es un grafo dirigido (sobre V), o dígrafo (sobre v), donde V es el conjunto de vértices, o nodos y E es subconjunto de aristas. Escribimos G = (V, E) para denotar tal dígrafo”.

Los mismos se representan gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas(aristas), y los mismos pueden ser:

  

• Dirigidos: Sea V un conjunto finito no vacío, y sea E C V x V, donde V es el conjunto de vértices, o nodos y £ es su conjunto de aristas. Lo escribimos G = (V, E)

• No Dirigidos: Cuando no importa la dirección de las aristas, la estructura G = (V, E), donde E es ahora un conjunto de pares no ordenados sobre V.

Los Arboles son un tipo especial de grafos no dirigidos.

Los Arboles:

Se define como árbol a un grafo no dirigido en el que cualesquiera dos vértices están conectados por exactamente un camino y cumple las siguientes propiedades:

•   Es simple, conexo y sin ciclos. 

•   Es conexo y |V|=n entonces |A|=n-1.

•   G no contiene ciclos y si a, b ∈ V con {a, b) ∉ E, entonces el grafo que se obtiene de añadir la arista {a, b] a G tiene precisamente un ciclo.

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 y la producción. En la informática se utiliza para, por ejemplo:

• Representar un dato jerárquicamente

• Almacenar un dato de tal modo que su búsqueda sea eficiente (ver búsqueda en árboles binarios y recorrido de árboles)

• Representar listas ordenadas de datos

•  Como un flujo de trabajo para la composición de imágenes digitales

•  Algoritmos de encaminamiento

Recorridos de los Arboles

Se conoce como recorrido al proceso de 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 3 formas de realizar este proceso:

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

• Visitar la raíz

• Atravesar el sub-arbol izquierdo

•  Atravesar el sub-arbol derecho

 

Pre-orden: ABDGEHICFJK

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

• Atravesar el sub-árbol izquierdo

• Visitar la raíz

• Atravesar el sub-árbol derecho

In-orden: GDBHEIACJKF

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

•  Atravesar el sub-árbol izquierdo

•  Atravesar el sub-árbol derecho

•  Visitar la raíz

Post-orden: GDHIEBKJFCA