ARBOLES

Arboles:

Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.

Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.

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.

Ejemplo de árbol raíz:

Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.

Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.

En cualquier árbol R= (V,A), |V| = |A| + 1.

Para cualquier árbol R = (V,A), si |A| >= 2, entonces R tiene al menos dos vértices colgantes.

Sea G un grafo simple con v vértices, entonces se puede decir:

• G es un árbol.
• G es conexo y no contiene circuitos.
• G es conexo y tiene (n-1) lados.
• G no contiene circuitos y tiene (n-1) lados.

Arboles con Raíz

Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.

Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, ..., vn), es un camino en G.

• V(n-1) es el padre de v(n).
• V0, v1, ..., v(n-1) son los antepasados de v(n).
• V(n) es el hijo de v(n-1).
• Si x es un antepasado de y, entonces y es un descendiente de x.
• Si x e y son hijos de z entonces x e y son hermanos.
• Si x no tiene hijos entonces x es un vértice terminal.
• Si x no es un vértice terminal, entonces x es un vértice interno.
• El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.

Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si |V| > 1, sean R1, R2, R3, ...., Rk los subarboles de R según se va de izquierda a derecha.

El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.

El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,...., Rk en orden simétrico.

El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,...., Rk en orden posterior y a continuación por la raíz.

Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.

Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.

Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.