Árboles
Árboles. Árboles enraizados I Búsqueda en profundidad. Búsqueda en anchura I Árboles de expansión mínimos

3.1. Árboles. Árboles enraizados.

Definición 3.1.1. Un árbol es un grafo conexo que no tiene ciclos.

Ejemplo 3.1.2

Los grafos  G1 y G2 son árboles, mientras que los grafos G3 y G4 no lo son.

Definición 3.1.3. Un bosque es un grafo donde cada componente conexa es un árbol.

Definición equivalente: Un bosque es un grafo acíclico.

El grafo G4 del ejemplo anterior es un bosque.

Caracterizaciones de los árboles

Proposición 3.1.4. El grafo T =(V, E) es un árbol si y solo si todo par de vértices de T están conectados por un único camino simple.

Demostración.

=> T es un árbol  =>T conexo => Dados  existe al menos un camino simple que los une. Supongamos que entre los vértices u y v existen dos caminos simples. Denotemos por x el vértice donde estos caminos divergen por primera vez y por w el vértice donde estos caminos convergen nuevamente. Por tanto los dos caminos diferentes entre los vértices x y w forman un ciclo, lo cual contradice la definición de árbol.

<=  Supongamos que para todo par existe un único camino simple que los une. Entonces T es conexo y acíclico, pues de existir un ciclo existirían dos vértices conectados por dos caminos.

Proposición 3.1.5. El grafo T =(V, E) es un árbol si y solo si T es acíclico y al agregar una arista aparece un ciclo único.

Demostración.

=> T es un árbol.  =>Sean y agreguemos una arista que los une. Caso 1. Si u y v son adyacentes, al agregar la arista se producen dos aristas paralelas produciendo un ciclo de longitud dos. Caso 2. Si u y v no son adyacentes existe un camino único que los une. Con la nueva arista este camino se cierra formando un ciclo.

<= T es acíclico y si se agrega una arista aparece un ciclo único. => Supongamos que T no es conexo. => existe al menos dos vértices  u, v que no son mutuamente alcanzables. Al agregar la arista (u, v) aparece un ciclo, lo cual implica la existencia de un camino entre u y v. Contradicción. T es conexo por tanto es un árbol.

Proposición 3.1.6. El grafo T =(V, E) es un árbol si y solo si T es conexo y toda arista es un puente.

Demostración.

=> T es un árbol.  => Sea a una arista que es no es puente. => a forma parte de un ciclo. => Contradicción.

<= T es conexo y toda arista es un puente. => No existen ciclos. => T es un árbol.

Proposición 3.1.7. Todo árbol tiene al menos dos vértices con grado 1 (hojas).

Demostración.

Sea v₁, v₂, ..., v_s un camino de longitud máxima en el árbol T. Supongamos que d(v₁)>1 . Pueden ocurrir dos casos:

a)      v₁ es adyacente a otro vértice de T que no pertenece al camino. El camino puede extenderse. Contradicción con camino de longitud máxima.

b)      v₁ es adyacente a otro vértice del camino diferente de v₂. Aparece un ciclo. Contradicción con definición de árbol.

Por tanto d(v₁)=1. Lo mismo ocurre para d(v_s)

Proposición 3.1.7.  Sea T =(V, E) un grafo con n vértices. Las siguientes afirmaciones son equivalentes:

1.         T es un árbol.

2.         T es acíclico y tiene exactamente m=n-1 aristas.

3.         T es conexo y tiene exactamente m=n-1 aristas.

Proposición 3.1.8. Sea T =(V, E) un grafo con n vértices y k componentes. G es un bosque si y solo si tiene  m=n-k aristas.

Proposición 3.1.9. (Fórmula de Cayley) El número de árboles etiquetados de n vértices es .

Código de Prüfer de un árbol T de orden n, etiquetado con {1,2,...,n}. Este código es una sucesión de n-2 números de {1,2,...,n}.

1.      Se busca la hoja u de T de menor etiqueta y se añade al código C, inicialmente vacío, la etiqueta de su vecino.

2.      Se borra de T el vértice u, T=T-{u}.

3.      Si T tiene más de dos vértices se vuelve al paso 1. En caso contrario el algoritmo termina.

Descodificación. Se parte ahora del código C, que es una sucesión de longitud n-2, de la lista L ={1,2,...,n} y del bosque trivial T de n vértices etiquetados con {1,2,...,n}

1.      Repetir lo siguiente n-2 veces lo siguiente. Sea j el primer elemento de C y sea k el menor número de L que no está en C. Añadir a T la arista (j, k). Borrar j de C y k de la lista L.

2.      Cuando sólo quedan dos elementos en L y ninguno en C, añadir a T la arista que une dichos elementos. Fin del algoritmo

Ejemplo 3.1.10. Construir el código Prüfer del siguiente árbol:

Ejemplo 3.1.11. Construir el árbol correspondiente al código [2,3,1,1,1,2,2,5].

Definición 3.1.12. Un árbol con raíz o árbol enraizado es un árbol en el cual un vértice en particular  se designa como raíz.

Los árboles con raíz se representan de forma tal, que el vértice raíz se coloca encima de los restantes, los cuales se sitúan por niveles según su distancia a la raíz.

Definición 3.1.13. Se llama altura (o profundidad) de un árbol con raíz a la máxima distancia de un vértice a la raíz.

 Definición 3.1.14. Sea T un árbol con raíz v₀. Sean x, y vértices de T y sea (v₀, v₁, ...,  v_n-1,v_n) un camino simple en T. Entonces:

a)      v_n-1 es el padre de v_n.

b)      v₀, ..., v_n-1 son ancestros de v_n.

c)      v_n es un hijo de v_n-1.

d)      Si x es un ancestro de y, entonces y es un descendiente de x.

e)      Si x no tiene hijos, entonces x se denomina hoja o vértice terminal .

f)        Si x no es una hoja, se denomina vértice interno.

g)      El nivel del vértice x es la longitud del camino simple de la raíz a x.

Ejemplo 3.1.15.

Los árboles con raíz  se utilizan para especificar relaciones jerárquicas, por ejemplo árboles genealógicos, relaciones lógicas entre los registros de una base de datos, relaciones entre los directorios y subdirectorios en un computador, etc.

Definición 3.1.16. Un árbol m-ario es un árbol con raíz en el que cada padre tiene, a lo sumo, m hijos.

Proposición 3.1.17. El número de hojas de un árbol m-ario es  a lo sumo mh.

Proposición 3.1.18. La altura de un árbol m-ario de l hojas es, al menos,