Posted on 13:33
Un árbol es un grafo simple en el cual existe un ún
ico 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.
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.
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
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.
Teorema:
Para cualquier árbol R = (V,A), si |A| >= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
· 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.
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.
1. 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.
2. 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.
3. 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.
Teorema:
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.
Publicar un comentario