Árboles, árboles generadores y aplicaciones

Por qué los árboles aparecen en todas las olimpiadas

Imagina que $n$ ciudades deben ser conectadas por carreteras de modo que siempre haya un camino entre cualquier par de ciudades, pero usando la menor cantidad posible de carreteras para ahorrar costos. ¿Cuántas carreteras necesitas y qué forma tiene la red resultante? La respuesta es exactamente $n-1$ carreteras, y la estructura se llama árbol.

Los árboles son el "esqueleto" más económico de la conexidad: si quitamos cualquier arista, el grafo se desconecta; si añadimos cualquier arista, creamos un ciclo. Esta rigidez los hace extraordinariamente manejables en demostraciones: hay exactamente una forma de pasar de un vértice a otro, lo que elimina ambigüedades.

En competencias como la Olimpiada Iberoamericana y el Cono Sur, los árboles aparecen en tres familias de problemas: (1) problemas de existencia (demostrar que cierta subred económica puede construirse), (2) problemas de invariantes en procesos iterativos sobre grafos, y (3) problemas de conteo de estructuras arbóreas. Dominar los árboles significa dominar la "capa base" de la teoría de grafos.

Un ejemplo inmediato: si en una red de $n$ computadoras cada una está conectada directamente con exactamente otras dos, la red forma un ciclo o una colección de ciclos. Si queremos garantizar que la red sea conexa con el mínimo de conexiones, debemos construir un árbol generador de la red actual.

Definición y caracterizaciones equivalentes de árbol

Un árbol es un grafo $T = (V, E)$ que es simultáneamente conexo y acíclico (sin ciclos). Un grafo acíclico (con o sin conexidad) se llama bosque; cada componente conexa de un bosque es un árbol.

El siguiente teorema reúne las cinco caracterizaciones más importantes. Sea $G = (V, E)$ con $|V| = n$. Las siguientes afirmaciones son equivalentes:

(1) $G$ es un árbol (conexo y acíclico). (2) $G$ es conexo y $|E| = n-1$. (3) $G$ es acíclico y $|E| = n-1$. (4) Existe exactamente un camino simple entre todo par de vértices. (5) $G$ es acíclico y añadir cualquier arista crea exactamente un ciclo.

**Demostración de (1) $\Rightarrow$ (2):** Procedemos por inducción sobre $n$. Base $n=1$: árbol sin aristas, $0 = 1-1$. Para $n \geq 2$: como $T$ es finito y acíclico, tiene al menos una hoja (vértice de grado 1). Sea $v$ una hoja. El subgrafo $T-v$ sigue siendo conexo (sólo perdemos la hoja) y acíclico; por hipótesis inductiva tiene $n-2$ aristas. Entonces $T$ tiene $n-1$ aristas.

**Demostración de (2) $\Rightarrow$ (1):** Si $G$ es conexo con $n-1$ aristas, supongamos que tiene un ciclo $C$. Quitando una arista de $C$ el grafo sigue conexo pero ahora tiene $n-2$ aristas. Continuamos quitando aristas de ciclos hasta tener un árbol generador, que tiene $n-1$ aristas. Contradicción: ya teníamos exactamente $n-1$ aristas y quitamos al menos una. $\square$

Lema de la hoja: Todo árbol con $n \geq 2$ vértices tiene al menos dos hojas. Prueba: por el Lema del Apretón de Manos, $\sum d(v) = 2(n-1) = 2n-2$. Si hubiera a lo más una hoja, entonces todos salvo uno de los $n$ vértices tendrían grado $\geq 2$, luego $\sum d(v) \geq 2(n-1) + 1 = 2n-1 > 2n-2$, contradicción.

Árboles generadores: existencia y construcción

Un árbol generador (o spanning tree) de un grafo conexo $G$ es un subgrafo $T \subseteq G$ que contiene todos los vértices de $G$ y es un árbol. En otras palabras, $T$ "abarca" todo $G$ con el mínimo de aristas que mantienen la conexidad.

Teorema: Todo grafo conexo $G$ tiene al menos un árbol generador.

Prueba constructiva: Si $G$ no tiene ciclos, ya es un árbol generador de sí mismo. Si tiene un ciclo $C$, eliminamos una arista de $C$: el grafo resultante sigue siendo conexo (cualquier camino que usara esa arista puede rodear el ciclo). Repetimos este proceso; como $|E|$ decrece en cada paso y el proceso termina cuando no hay ciclos, obtenemos un árbol generador.

Número de aristas eliminadas: Partimos con $m = |E|$ aristas y terminamos con $n-1$. Luego eliminamos exactamente $m - (n-1)$ aristas, lo que define el número de circuitos $\gamma(G) = m - n + 1$ (también llamado primer número de Betti del grafo). Este invariante mide cuán "lejos" está $G$ de ser un árbol.

Aplicación olímpica (Cono Sur 2005, P1, adaptado): Se tienen $n$ computadoras conectadas por cables (algunas directas, otras a través de ruteadores) formando una red conexa. Se sabe que hay exactamente $n + 3$ cables. ¿Cuántos cables se pueden cortar de modo que la red siga siendo conexa? Respuesta: el número de circuitos es $\gamma = (n+3) - n + 1 = 4$, luego podemos cortar exactamente 4 cables manteniendo la conexidad (eliminamos uno de cada ciclo).

Construyendo árboles generadores en la práctica: Dos algoritmos clásicos son BFS (Breadth-First Search) y DFS (Depth-First Search). Aunque no los usamos computacionalmente en olimpiadas, sus ideas son útiles: BFS produce el árbol de caminos más cortos desde un vértice, y DFS clasifica las aristas en aristas del árbol y back edges (aristas que vuelven hacia un ancestro), siendo estas últimas exactamente las que crean ciclos.

Técnicas de demostración con árboles

La herramienta más poderosa para demostraciones con árboles es la inducción sobre el número de vértices, eliminando hojas en cada paso. La estrategia estándar: (a) identifica una hoja $v$, (b) aplica la hipótesis inductiva al árbol $T-v$, (c) re-agrega $v$ y su única arista, y (d) verifica que la propiedad deseada se preserva.

Ejemplo clásico: Todo árbol con $n$ vértices puede ser $2$-coloreado (es decir, es bipartito). Prueba por inducción: para $n=1$ es trivial. Para $n \geq 2$, sea $v$ una hoja con vecino $u$. Por hipótesis, $T-v$ es bipartito con bipartición $(A, B)$; digamos $u \in A$. Asignamos $v$ a $B$. Como $v$ sólo es adyacente a $u \in A$, la bipartición $(A, B \cup \{v\})$ funciona para $T$. $\square$

Problema de conteo de árboles generadores: El Teorema de Kirchhoff (también llamado Teorema Matricial de Árboles) establece que el número de árboles generadores de $G$ es cualquier cofactor de la matriz laplaciana $L = D - A$, donde $D$ es la matriz diagonal de grados y $A$ es la matriz de adyacencia. Para $K_n$, esto da $n^{n-2}$ árboles generadores (Fórmula de Cayley), resultado fundamental en combinatoria.

La Fórmula de Cayley dice que el número de árboles etiquetados con vértices $\{1, 2, \ldots, n\}$ es $n^{n-2}$. Prueba elegante (codificación de Prüfer): a cada árbol le asignamos una secuencia $(a_1, a_2, \ldots, a_{n-2})$ con $a_i \in \{1,\ldots,n\}$ iterativamente eliminando la hoja de menor etiqueta y registrando el label de su vecino. Esta asignación es una biyección entre árboles etiquetados y secuencias de $\{1,\ldots,n\}^{n-2}$, que tiene exactamente $n^{n-2}$ elementos.

Problema olímpico (IbAm 2010, P1, adaptado): En una red de $n$ nodos, cada par de nodos está directamente conectado o conectado a través de un camino. Se añaden aristas hasta que añadir cualquier arista más crearía un ciclo. ¿Cuántas aristas tiene la red al final? Solución: añadir aristas sin crear ciclos es exactamente construir un bosque maximal. Un bosque maximal en un grafo conexo es un árbol generador con $n-1$ aristas. Si el grafo tiene $k$ componentes conexas, el bosque maximal tiene $n-k$ aristas.

Aplicaciones en problemas de Cono Sur e Iberoamericana

Los árboles generadores son la herramienta clave cuando un problema pide demostrar que cierto conjunto de conexiones "minimales" tiene una propiedad. El argumento típico es: (1) muestra que cualquier árbol generador tiene la propiedad, o (2) construye un árbol generador específico que exhibe la propiedad deseada.

Problema representativo (Cono Sur 2015, P2): Sea $G$ un grafo conexo con $n$ vértices en el que cada arista tiene un peso (número real). Demuestra que existe un árbol generador cuya suma de pesos es mínima entre todos los árboles generadores. (Esto es el Árbol Generador Mínimo.) Además, si todos los pesos son distintos, el árbol generador mínimo es único.

Prueba de unicidad: Supongamos que hay dos árboles generadores mínimos $T_1$ y $T_2$ distintos. Existe una arista $e \in T_1 \setminus T_2$. Al añadir $e$ a $T_2$ se crea un ciclo $C$. Como $e \notin T_2$, existe en $C$ otra arista $f \in T_2 \setminus T_1$. El árbol $T_2 - f + e$ es también generador. Si $w(e) < w(f)$, entonces $T_2 - f + e$ tiene menor peso que $T_2$, contradiciendo que $T_2$ es mínimo. Si $w(e) > w(f)$, análogamente $T_1$ no es mínimo. Si $w(e) = w(f)$ y todos los pesos son distintos, imposible. $\square$

Técnica del "corte": Sea $S \subset V$ con $S \neq \emptyset, V$. El corte definido por $S$ es el conjunto de aristas con un extremo en $S$ y otro en $V \setminus S$. En todo árbol generador, exactamente una arista de cada corte "fundamental" está en el árbol. Esta observación permite demostrar propiedades de conectividad: si un corte tiene exactamente una arista, esa arista debe estar en todo árbol generador (es un puente).

Puentes y bloques: Una arista $e$ es un puente si $G - e$ es disconexo. Equivalentemente, $e$ es un puente si y solo si $e$ no pertenece a ningún ciclo. Esto conecta árboles con la estructura local del grafo. Problema frecuente en olimpiadas: "demuestra que existe una arista cuya eliminación desconecta el grafo" es equivalente a "el grafo tiene un puente", lo que a su vez equivale a "el árbol generador tiene una arista que no puede ser reemplazada por ninguna otra".

Estrategia de síntesis: Cuando veas un problema con grafos conexos y quieras demostrar algo sobre el número de aristas o la estructura de caminos, piensa en árbol generador. Cuando quieras demostrar algo sobre recubrimientos o particiones eficientes, busca hojas y usa inducción. Cuando el problema diga "mínimo" o "máximo" número de aristas con una propiedad, el árbol generador da el piso $n-1$.