RECORRIDOS DE UN ÁRBOL

En ciencias de la computación, el recorrido de árboles refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles.

Comparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un método canónico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres pasos principales que pueden ser realizados y el orden en la cual son realizados define el tipo de recorrido. Estos pasos (en ningún orden particular) son: ejecución de una acción en el nodo actual (referido como “visitando” el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la derecha. Así el proceso más fácilmente descrito a través de la recursión.

Los nombres dados para un estilo particular de recorrido vienen de la posición del elemento de raíz con respecto a los nodos izquierdo y derecho. Imagine que los nodos izquierdo y derecho son constantes en espacio, entonces el nodo raíz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden).

Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre prioridad sobre los nodos derechos. Este ordenamiento puede ser invertido mientras el mismo orden sea asumido para todos los métodos de recorrido.

ARBOLES BINARIOS

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

En teoría de grafos, se usa la siguiente definición: Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3. De esta forma solo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque'.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

ARBOLES DE EXPANSIÓN MÍNIMA

Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.

El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).

ARBOLES DE EXPANSIÓN 

En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas de G. 

Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T.

Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.

En ciertos campos de la teoría de grafos es útil encontrar el mínimo árbol de expansión de un grafo ponderado. También se han abordado otros problemas de optimización relacionados con los árboles de expansión, como el máximo árbol de expansión, el máximo árbol que cubre al menos k vértices, el mínimo árbol de expansión con k aristas por vértice como máximo (árbol de expansión de mínimo grado, MDST por sus siglas en inglés), el árbol de expansión con el máximo número de hojas (estrechamente relacionado con el problema del menos conjunto dominante y conexo), el árbol de expansión con el menor número de hojas (relacionado con el problema del camino hamiltoniano), el árbol de expansión de mínimo diámetro o el árbol de expansión de la mínima dilación.

TERMINOLOGÍA Y CARACTERIZACIÓN

TERMINOLOGÍA 

Ademas del nodo raíz, existen muchos términos utilizados en la descripción  de los atributos de un árbol, por ejemplo un nodo que tiene arboletes se conoce como padre de ellos, y los nodos sucesores se llaman hijos. De este modo los hijos de un nodo y los hijos de este se denominan descendientes asi como el padre y los abuelos se conoce como ascendentes. Los nodos del mismo padre suelen llamarse hermanos y los nodos  que no tiene desentiendes de conocen como hojas.



CARACTERIZACIÓN

• Todo arbol que no es vacio, tiene un unico nodo raiz.
• Un nodo X es desendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y.
• En este caso es común utlilizar la expresión X es hijo de Y.
• Un nodo X es antecesor directo de un nodo Y, si en nodo apunta al nodo Y.

UNIDAD 5

ARBOLES

Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.

Ejemplo de árbol:

En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo.

Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R.

En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.

GRAFOS APLANABLES 

Este tipo de grafos, además de aparecer con mucha frecuencia también cuentan con muchas propiedades interesante. Se analizarán algunas de las más importantes.

Definición:
Diremos que un grafo es aplanable si puede ser dibujado sobre un plano de tal manera tal que ninguna arista se cruce con otra excepto, desde luego, en los vértices comunes. El siguiente es un grafo aplanable:

el grafo i) también es aplanable ya que puede dibujarse como se muestra en el grafo ii)

Ejemplo:
La siguiente figura es un grafo no aplanable que a decir verdad corresponde al problema de determinar si es posible conectar las casas 1, 2, 3 a los servicios de Luz, Agua y Drenaje, de tal manera que no haya 2 líneas de conexión que se crucen una con la otra.