18. Árboles y bosques

18.1 Introducción

Los árboles aparecen constantemente en programación: sistemas de archivos, jerarquías, árboles de búsqueda, interfaces, expresiones y decisiones.

Desde la teoría de grafos, un árbol no se define por su forma visual, sino por dos propiedades: debe estar conectado y no contener ciclos.

18.2 Definición de árbol

Un árbol es un grafo no dirigido, conectado y acíclico.

La definición no exige una raíz. La raíz se elige cuando queremos interpretar el árbol como una jerarquía.

18.3 Definición de bosque

Un bosque es un grafo no dirigido sin ciclos que puede estar desconectado. Cada una de sus componentes conexas es un árbol.

Todo árbol es también un bosque con una sola componente.

18.4 Propiedades equivalentes

Para un grafo no dirigido con n vértices, las siguientes afirmaciones caracterizan a un árbol:

• Es conectado y no contiene ciclos.
• Existe un único camino simple entre cada par de vértices.
• Es conectado y tiene n − 1 aristas.
• No contiene ciclos y tiene n − 1 aristas.
• Eliminar cualquier arista lo desconecta.
• Agregar una arista nueva crea exactamente un ciclo.

18.5 Simulación interactiva: árbol, bosque o ciclo

Selecciona dos vértices para agregar o quitar una arista. La aplicación comprobará conectividad y ciclos para clasificar la estructura.

Agrega A—D: como ya existía un camino entre ambos, aparece un ciclo. Reinicia y corta C—F: el árbol se divide en dos componentes y se convierte en bosque.

18.6 Cantidad de aristas

Todo árbol con n vértices posee exactamente n − 1 aristas.

Si tiene menos, no puede estar conectado. Si tiene más y sigue conectado, necesariamente contiene algún ciclo.

18.7 Fórmula para bosques

Un bosque con n vértices y c componentes posee n − c aristas.

Cada componente de tamaño nᵢ es un árbol con nᵢ − 1 aristas. Al sumar todas obtenemos la fórmula.

18.8 Hojas y vértices internos

En un árbol con al menos dos vértices, una hoja tiene grado 1. Los demás nodos se consideran internos.

Todo árbol finito con al menos dos vértices tiene al menos dos hojas.

18.9 Árboles con raíz

Al elegir una raíz aparecen relaciones jerárquicas: padre, hijo, ancestro, descendiente, nivel y profundidad.

La estructura no dirigida subyacente sigue siendo el mismo árbol; la raíz agrega una interpretación y una orientación conceptual.

18.10 Verificar un árbol con JavaScript

function esArbol(cantidadVertices, aristas, cantidadComponentes) {
  return cantidadComponentes === 1 &&
         aristas.length === cantidadVertices - 1;
}

console.log(esArbol(5, [
  ["A", "B"], ["A", "C"], ["C", "D"], ["C", "E"]
], 1));

La comprobación presupone un grafo simple no dirigido. La cantidad de componentes debe calcularse mediante una búsqueda.

18.11 Detectar ciclos con Union-Find

function tieneCiclo(aristas) {
  const padre = {};
  const buscar = x => padre[x] === x ? x : padre[x] = buscar(padre[x]);

  for (const [a, b] of aristas) {
    if (!(a in padre)) padre[a] = a;
    if (!(b in padre)) padre[b] = b;
    const raizA = buscar(a);
    const raizB = buscar(b);
    if (raizA === raizB) return true;
    padre[raizA] = raizB;
  }
  return false;
}

18.12 Errores comunes

• Identificar un árbol solo por su forma visual.
• Comprobar n − 1 aristas sin verificar conectividad.
• Suponer que todo grafo acíclico es un árbol aunque esté desconectado.
• Confundir una raíz elegida con una propiedad obligatoria del árbol.
• Olvidar que cada componente de un bosque es un árbol.
• Agregar una arista a un árbol sin reconocer el ciclo creado.

18.13 Qué debes recordar de este tema

• Un árbol es conectado y acíclico.
• Un bosque es acíclico y puede estar desconectado.
• Un árbol con n vértices tiene n − 1 aristas.
• Un bosque con c componentes tiene n − c aristas.
• Entre dos vértices de un árbol existe un único camino simple.
• Agregar una arista a un árbol crea un ciclo.

18.14 Conclusión

Árboles y bosques son las estructuras acíclicas fundamentales de la teoría de grafos. Ofrecen conectividad con la mínima cantidad de aristas y permiten representar jerarquías y relaciones sin redundancia.

En el próximo tema estudiaremos árboles generadores, que conservan todos los vértices de un grafo conectado utilizando solo las aristas necesarias.