Un árbol es un grafo simple G = (V, E) que cumple cualquiera de las siguientes condiciones equivalentes:
Conectividad y Ciclos: Es un grafo conexo y no contiene ciclos.
Caminos Únicos: Existe un único camino simple entre cualquier par de vértices u, v.
Relación Vértices-Aristas: Para un grafo de n vértices, es un árbol si es conexo y tiene n-1 aristas, o si no tiene ciclos y tiene n-1 aristas.
Propiedades Críticas:
Es conexo, pero deja de serlo si se prescinde de cualquier arista.
No contiene ciclos, pero se forma uno si se añade cualquier arista nueva.
Todo árbol es un grafo bipartito.
Ejercicio: Considera un grafo simple conexo G con 15 vértices. a) Si G es un árbol, ¿cuántas aristas debe tener? Justifica tu respuesta. b) Si G tiene 18 aristas, ¿puede ser un árbol? ¿Por qué? c) Si eliminamos 4 aristas de G y obtenemos un bosque con 3 componentes conexas (todas ellas árboles), ¿cuántas aristas tenía G originalmente?
Apartado a) Si G es un árbol con 15 vértices, ¿cuántas aristas debe tener?
Una de las propiedades fundamentales de los árboles establece que un árbol con \( n \) vértices tiene exactamente \( n-1 \) aristas.
En nuestro caso:
Número de vértices: \( n = 15 \)
Número de aristas: \( n – 1 = 15 – 1 = 14 \)
Por tanto, el grafo G debe tener exactamente 14 aristas.
Esta propiedad se cumple porque un árbol es un grafo conexo (necesitamos al menos 14 aristas para conectar 15 vértices) y sin ciclos (no podemos tener más de 14 aristas porque se formaría un ciclo). La única cantidad posible es exactamente \( n-1 \) aristas.
Apartado b) Si G tiene 18 aristas, ¿puede ser un árbol?
Como hemos visto en el apartado anterior, un árbol con 15 vértices debe tener exactamente 14 aristas.
Si G tiene 18 aristas, tenemos:
Aristas de G: 18
Aristas necesarias para ser árbol: 14
Aristas en exceso: \( 18 – 14 = 4 \)
Consecuentemente, G no puede ser un árbol.
Un grafo con 15 vértices y 18 aristas tiene 4 aristas más de las necesarias. Estas aristas adicionales necesariamente forman ciclos. Por tanto, G no cumple la definición de árbol (que debe ser conexo y sin ciclos).
Apartado c) Bosque con 3 componentes conexas
Partimos de un grafo G con 15 vértices. Al eliminar 4 aristas, obtenemos un bosque con 3 componentes conexas (tres árboles separados).
Paso 1: Calcular cuántas aristas tiene el bosque resultante.
Sea \( n_1, n_2, n_3 \) el número de vértices en cada componente. Sabemos que:
\( n_1 + n_2 + n_3 = 15 \) (los vértices se reparten entre las 3 componentes)
Paso 2: Calcular cuántas aristas tenía G originalmente.
Si al eliminar 4 aristas quedaron 12 aristas, entonces G tenía:
\[ 12 + 4 = 16 \text{ aristas} \]
Por tanto, G tenía originalmente 16 aristas.
Nota: Observa que G no era un árbol (tendría 14 aristas), sino un grafo con 2 aristas extra que formaban ciclos.
2. Tipos y Conceptos Relacionados
Bosque: Grafo simple sin ciclos donde sus componentes conexas son árboles.
Árbol Generador (o Recubridor): Subgrafo de un grafo G que es un árbol y contiene a todos los vértices de G. Un grafo tiene árbol generador si y solo si es conexo.
Árbol Generador Mínimo: En grafos ponderados, es el árbol generador cuyo peso total (suma de los pesos de sus aristas) es el mínimo posible.
Algoritmo de Prim: Procedimiento paso a paso para hallar este árbol partiendo de un vértice inicial y añadiendo la arista de menor peso que conecte con un vértice nuevo.
Ejercicio: Dado el siguiente grafo ponderado que representa conexiones entre servidores (los pesos indican el coste de cada enlace):
a) Dibuja al menos dos árboles generadores diferentes de este grafo.
b) Utilizando el algoritmo de Prim comenzando desde el vértice A, construye paso a paso el árbol generador mínimo. Indica en cada paso qué arista añades y por qué.
c) ¿Cuál es el coste total del árbol generador mínimo?
Apartado a) Dos árboles generadores diferentes.
Un árbol generador debe incluir todos los vértices (A, B, C, D, E, F) y exactamente \( 6 – 1 = 5 \) aristas, sin formar ciclos.
El algoritmo de Prim construye el árbol generador mínimo comenzando desde un vértice inicial y añadiendo en cada paso la arista de menor peso que conecte un vértice ya incluido con uno nuevo.
Apartado c) Coste total del árbol generador mínimo
Sumando los pesos de todas las aristas seleccionadas:
\[ 3 + 2 + 5 + 4 + 8 = 22 \]
El coste total del árbol generador mínimo es 22.
3. Árboles con Raíz
Estructura donde se destaca un vértice especial llamado raíz.
Jerarquía:
Niveles: La raíz está en el nivel 0; sus adyacentes en el nivel 1, y así sucesivamente.
Altura: Valor máximo del nivel de sus vértices, $h(G)$.
Relaciones: Se definen conceptos de padre (vértice anterior en el camino desde la raíz), hijo (vértice siguiente), ancestro y descendiente.
Tipos de Vértices:
Hoja: Vértice que no tiene hijos.
Vértice Interno: Vértice que no es una hoja.
Clasificación por Grado:
Árbol m-ario: Cada vértice interno tiene a lo sumo m hijos. Es «completo» si todos tienen exactamente m hijos.
Árbol Binario: Árbol 2-ario donde se distingue entre hijo derecho e hijo izquierdo.
Ejercicio: Considera el siguiente árbol con raíz en A:
a) Indica la altura del árbol.
b) Enumera todos los vértices hoja.
c) Para el vértice E, indica: su padre, sus hijos, sus ancestros y sus descendientes.
d) Determina el nivel de cada vértice.
e) ¿Es este árbol m-ario? En caso afirmativo, ¿qué valor tiene m? ¿Es completo?
Apartado a) Altura del árbol
La altura de un árbol es el nivel máximo de sus vértices (el nivel más alejado de la raíz).
Niveles en el árbol:
Nivel 0: A
Nivel 1: B, C, D
Nivel 2: E, F, G, H
Nivel 3: I
Luego, la altura del árbol es 3.
Apartado b) Vértices hoja
Un vértice hoja es aquel que no tiene hijos (es decir, no tiene descendientes).
Analizando cada vértice:
A tiene hijos (B, C, D) → NO es hoja
B tiene hijos (E, F) → NO es hoja
C no tiene hijos → SÍ es hoja
D tiene hijos (G, H) → NO es hoja
E tiene hijo (I) → NO es hoja
F no tiene hijos → SÍ es hoja
G no tiene hijos → SÍ es hoja
H no tiene hijos → SÍ es hoja
I no tiene hijos → SÍ es hoja
Los vértices hoja son: C, F, G, H, I (5 hojas en total).
Apartado c) Información sobre el vértice E
Padre de E: El vértice inmediatamente anterior en el camino desde la raíz hasta E.
Camino desde la raíz: A → B → E
Padre de E: B
Hijos de E: Los vértices directamente conectados a E y que están en el nivel siguiente.
Hijos de E: I
Ancestros de E: Todos los vértices en el camino desde la raíz hasta E (sin incluir a E).
Camino: A → B → E
Ancestros de E: A, B
Descendientes de E: Todos los vértices en los subárboles que cuelgan de E.
Descendientes de E: I
Apartado d) Nivel de cada vértice
El nivel de un vértice es la distancia (número de aristas) desde la raíz hasta ese vértice.
Vértice
Nivel
Camino desde la raíz
A
0
A
B
1
A → B
C
1
A → C
D
1
A → D
E
2
A → B → E
F
2
A → B → F
G
2
A → D → G
H
2
A → D → H
I
3
A → B → E → I
Apartado e) ¿Es m-ario? ¿Es completo?
Un árbol es m-ario si cada vértice interno tiene a lo sumo m hijos.
Analizando los vértices internos (no hojas):
A tiene 3 hijos (B, C, D)
B tiene 2 hijos (E, F)
D tiene 2 hijos (G, H)
E tiene 1 hijo (I)
El máximo número de hijos que tiene un vértice interno es 3 (el vértice A).
Vemos que sí, es un árbol 3-ario (ternario), porque ningún vértice interno tiene más de 3 hijos.
Un árbol m-ario es completo si todos los vértices internos tienen exactamente m hijos.
Verificando:
A tiene 3 hijos ✓
B tiene 2 hijos ✗ (debería tener 3)
D tiene 2 hijos ✗ (debería tener 3)
E tiene 1 hijo ✗ (debería tener 3)
Por tanto, no, no es un árbol 3-ario completo, porque no todos los vértices internos tienen exactamente 3 hijos.
4. Árboles Binarios de Búsqueda (ABB)
Es un tipo de árbol binario donde los vértices están ordenados.
Propiedad de Orden: Para cada vértice v, los elementos del subárbol izquierdo son menores (anteriores) a v, y los del subárbol derecho son mayores (posteriores).
Operaciones Principales:
Búsqueda: Localización de un elemento comparándolo con la raíz y descendiendo por la rama correspondiente.
Inserción: Añadir un nuevo vértice manteniendo la propiedad de orden.
Eliminación: Procedimiento para prescindir de un vértice considerando si es una hoja, si tiene un solo hijo o si tiene dos hijos.
Ejercicio: Dibuja un árbol binario que satisfaga las siguientes condiciones:
a) Tiene exactamente 7 vértices.
b) Tiene altura 3.
c) Tiene exactamente 3 hojas.
d) El vértice raíz tiene dos hijos, y al menos un vértice interno (no hoja, no raíz) tiene un solo hijo.
Pregunta adicional: ¿Cuántos árboles binarios distintos podemos construir con estas condiciones? (No es necesario dibujarlos todos, pero razona si hay más de uno posible)
Construcción del árbol con las condiciones dadas
Condiciones:
Exactamente 7 vértices
Altura 3
Exactamente 3 hojas
La raíz tiene dos hijos
Al menos un vértice interno (no hoja, no raíz) tiene un solo hijo
Vamos a construir el árbol paso a paso razonando las restricciones.
Paso 3: Cumplir la condición de «al menos un vértice interno con un solo hijo».
Si ambos vértices del nivel 1 tuvieran dos hijos, tendríamos 4 vértices en el nivel 2, y no podríamos alcanzar el nivel 3. Por tanto, uno de los vértices del nivel 1 debe tener un solo hijo (para que ese hijo esté en nivel 2 y pueda tener su propio hijo en nivel 3).
Hay múltiples árboles binarios distintos que cumplen estas condiciones (al menos en configuraciones similares), ya que podemos reorganizar los subárboles izquierdo y derecho en diferentes niveles. El número exacto requeriría enumeración exhaustiva.
Ejercicio: Considera la siguiente secuencia de números que se van insertando en un ABB inicialmente vacío:
\[(50,\, 30,\, 70,\, 20,\, 40,\, 60,\, 80,\, 10,\, 25)\]
a) Dibuja el árbol binario de búsqueda resultante tras insertar todos los elementos en el orden dado.
b) Describe el proceso paso a paso de búsqueda del elemento 25 en el árbol construido. Indica qué vértices se visitan.
c) Describe el proceso de eliminación del vértice 30 del árbol. Dibuja el árbol resultante.
d) Si hubiéramos insertado los mismos números pero en orden ascendente (10, 20, 25, 30, …), ¿qué forma tendría el árbol? ¿Qué problema observas?
Apartado a) Construcción del ABB
Veamos el proceso paso a paso:
Paso 1: Insertar 50
50
50 se convierte en la raíz (el árbol estaba vacío).
El árbol se convierte en una lista enlazada (o cadena lineal). Esto significa que:
Altura del árbol: \( n – 1 = 8 \) (muy alto para 9 elementos)
Tiempo de búsqueda: En el peor caso, \( O(n) \) en lugar de \( O(\log n) \)
Eficiencia perdida: Se pierde la principal ventaja de los ABB: búsqueda eficiente mediante división del espacio en mitades.
Por tanto, para evitar esta degradación, se usan árboles balanceados (como AVL o árboles rojo-negro) que garantizan altura logarítmica mediante rotaciones automáticas tras cada inserción/eliminación.
5. Árboles enraizados
Un árbol enraizado es un árbol conexo y acíclico (con \(n−1\) aristas para \(n\) vértices) donde se selecciona un vértice como raíz, y las aristas se orientan típicamente hacia abajo (hacia los hijos) o hacia la raíz. Esto genera una estructura jerárquica única: cada vértice, excepto la raíz, tiene exactamente un padre, y la raíz tiene grado de entrada 0 en su versión dirigida. En grafos dirigidos, se denomina arborescencia si las aristas apuntan lejos de la raíz, o anti-arborescencia si apuntan hacia ella. Lo que diferencia a los árboles enraizados de los árboles no dirigidos es que un árbol enraizado contiene un vértice distinguido, llamado raíz.
