Árboles en Teoría de Grafos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Un árbol tiene siete definiciones, y todas son la misma

Pide a tres personas que definan un árbol y obtendrás tres respuestas. Una dice que es un grafo conexo sin ciclos. Otra dice que es un grafo con exactamente un camino entre dos vértices cualesquiera. Una tercera dice que es un grafo conexo con n - 1 aristas. Las tres tienen razón, y también otras cuatro definiciones más, porque estas condiciones son equivalentes: cualquier grafo que cumpla una las cumple todas.

Eso es inusual, y es la razón de que los árboles sean el caso particular más útil de la materia. Una estructura con siete caracterizaciones equivalentes te da siete maneras distintas de demostrar algo sobre ella, y en la práctica eliges la que haga más corta la demostración.

Empecemos por la definición estándar, la de Diestel y la de Bondy y Murty:

Un árbol es un grafo conexo acíclico. Un grafo cuyas componentes son todas árboles es un bosque. Un vértice de grado 1 en un árbol es una hoja.

Todo lo que sigue trata de un grafo finito, simpley no dirigido , que es el marco estándar. De todos modos, un árbol no puede tener bucles ni aristas paralelas, ya que cualquiera de las dos cosas es un ciclo.

Escrito explícitamente, el ejemplo recurrente es

V = {1, 2, 3, 4, 5, 6, 7, 8}
E = { {1,3}, {2,3}, {3,4}, {4,5}, {5,6}, {5,7}, {7,8} }

grados    1:1   2:1   3:3   4:2   5:3   6:1   7:2   8:1
n = 8     m = 7 = n - 1      suma de grados = 14 = 2m      hojas: 1, 2, 6, 8

2. El teorema de equivalencia y cómo funciona su demostración

Aquí está el resultado completo. Aparece esencialmente en esta forma en West, en Bondy y Murty y en Diestel, y vale la pena memorizarlo porque cada línea es una herramienta.

Teorema. Para un grafo G con n vértices, son equivalentes:
(1) G es un árbol, es decir, conexo y acíclico.
(2) Dos vértices cualesquiera de G están unidos por exactamente un camino.
(3) G es conexo y tiene n - 1 aristas.
(4) G es acíclico y tiene n - 1 aristas.
(5) G es conexo, y eliminar cualquier arista lo desconecta (minimalmente conexo).
(6) G es acíclico, y añadir cualquier arista crea un ciclo (maximalmente acíclico).
(7) G es conexo y toda arista es un puente.

La demostración no es un único argumento sino un ciclo de implicaciones, cada una de ellas breve. Vale la pena ver su forma, porque explica por qué las condiciones parecen tan distintas entre sí y aun así describen el mismo objeto.

Dos de ellos merecen énfasis porque son los que la gente usa de verdad.

«Conexo y con n - 1 aristas» es la prueba más barata. Contar aristas cuesta O(m) y comprobar la conexión cuesta O(n + m), así que puedes decidir si es un árbol en tiempo lineal sin buscar nunca un ciclo. Observa que ninguna de las dos mitades basta por sí sola: un triángulo más un vértice aislado tiene 4 vértices y 3 aristas pero no es un árbol, y tampoco lo es un 4-ciclo, que es conexo con 4 aristas.

«Minimalmente conexo» y «maximalmente acíclico» son el mismo objeto visto desde dos direcciones. Un árbol se sitúa exactamente en la frontera: tiene tan pocas aristas como permite la conexión y tantas como permite la aciclicidad. Por eso los árboles aparecen siempre que un problema pide la estructura de conexión más barata, que es precisamente el problema del árbol de expansión mínima .

Las siete condiciones se cumplen en el ejemplo recurrente, y cada una se comprobó directamente: es conexo, acíclico, tiene 7 aristas con 8 vértices, hay exactamente un camino entre cada uno de los 28 pares de vértices, cada una de sus 7 aristas es un puente, y cada una de las 21 aristas que faltan cierra un ciclo al añadirse.

3. El lema de las hojas

Un pequeño resultado sostiene la mayoría de las demostraciones por inducción de la materia.

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

La demostración es una de las favoritas porque no usa nada más que la definición. Toma un camino más largo P en el árbol, digamos de u a v. Ese camino existe porque el árbol es finito. Considera ahora u. Si u tuviera un vecino w fuera de P, entonces P podría prolongarse con esa arista, lo que contradice la maximalidad. Si u tuviera un segundo vecino en P, eso cerraría un ciclo, lo que contradice la aciclicidad. Así que u tiene exactamente un vecino y es una hoja, y el mismo argumento vale para v.

De ahí se siguen de inmediato dos consecuencias, y ambas se usan constantemente:

• La inducción sobre árboles siempre tiene un caso base que quitar. Quita una hoja de un árbol y lo que queda es un árbol con un vértice menos. Ese único movimiento es el motor de la demostración de que un árbol tiene n - 1 aristas, de la codificación de Prüfer de la sección 7y del algoritmo para hallar el centro de la sección 10.
• La cota es ajustada. Un camino tiene exactamente dos hojas, así que «al menos dos» no puede mejorarse en general. En el otro extremo, la estrella K1,n-1 tiene n - 1 hojas.

El ejemplo recurrente tiene cuatro hojas, 1, 2, 6 y 8, holgadamente más que las dos garantizadas. Una comprobación útil al depurar código de árboles: si tu estructura dice ser un árbol y muestra menos de dos hojas, algo va mal, y el culpable habitual es un ciclo accidental.

El lema es además exactamente lo que falla en los grafos infinitos. El camino infinito en un sentido tiene una sola hoja y el camino infinito en ambos sentidos no tiene ninguna, una de las ilustraciones más limpias de lo que aporta la finitud, tratada en la guía de grafos finitos e infinitos.

4. Bosques, y contar componentes gratis

Un bosque es un grafo acíclico, conexo o no. Cada componente de un bosque es un árbol, y eso da una identidad de conteo que vale la pena saberse de memoria:

Un bosque con n vértices y k componentes tiene exactamente n - k aristas.

La demostración es una línea: cada componente es un árbol, así que una componente con ni vértices aporta ni - 1 aristas, y sumando sobre las k componentes se obtiene n - k. Tomando k = 1 se recupera el caso del árbol.

Léela al revés y la identidad pasa de ser un dato a ser una herramienta:

k = n - m        el número de componentes de un bosque,
                 calculado solo a partir de su tamaño, sin recorrerlo

Esto es realmente útil. Si sabes que un grafo es acíclico, contar sus vértices y aristas te dice en cuántos trozos está sin ejecutar una búsqueda. Es también la identidad que hay detrás de la invariante estándar de union-find : cada unión exitosa fusiona dos componentes y añade una arista, así que el contador n - (uniones hasta el momento) es el número de componentes en cualquier instante.

Una advertencia. La identidad supone aciclicidad. Para un grafo general siempre se cumple m ≥ n - k , con igualdad exactamente cuando el grafo es un bosque, así que un grafo con más de n - k aristas contiene necesariamente un ciclo. Esa desigualdad es la forma más rápida de demostrar que un grafo tiene un ciclo sin encontrarlo: si m ≥ n, hay un ciclo en alguna parte.

5. Árboles de expansión

Un árbol de expansión de un grafo conexo G es un subgrafo que es un árbol e incluye todos los vértices de G. Es el esqueleto mínimo que mantiene el grafo de una pieza.

Todo grafo finito conexo tiene uno, y vale la pena conocer la demostración constructiva porque también es un algoritmo: mientras exista un ciclo, elimina cualquiera de sus aristas. Eliminar una arista de un ciclo no puede desconectar el grafo, ya que el resto del ciclo sigue uniendo sus extremos, y el proceso termina porque cada paso elimina una arista. Lo que queda es conexo y acíclico. De forma equivalente, y más práctica, el árbol de aristas de descubrimiento que produce cualquier recorrido BFS o DFS ya es un árbol de expansión, obtenido en O(n + m).

Tres hechos sobre los árboles de expansión que aparecen una y otra vez:

• Todo árbol de expansión tiene exactamente n - 1 aristas, sea como sea el grafo. Así que en un grafo sin pesos todos los árboles de expansión empatan, y el problema del árbol de expansión mínima solo resulta interesante cuando las aristas llevan pesos.
• El número de árboles de expansión puede ser enorme. El grafo completo Kn tiene nn-2 de ellos, que es de nuevo la fórmula de Cayley , vista desde el lado de los árboles de expansión.
• Un árbol es su propio y único árbol de expansión. Obvio una vez dicho, y un caso degenerado útil para probar código: cualquier contador de árboles de expansión debería devolver exactamente 1 sobre un árbol, como confirma para el ejemplo recurrente el cálculo matriz-árbol de la sección 8 .

En los grafos infinitos, la afirmación «todo grafo conexo tiene un árbol de expansión» sigue siendo cierta, pero necesita el axioma de elección y de hecho es equivalente a él. Esa frontera se discute en la guía de grafos finitos e infinitos .

6. Contar árboles etiquetados: la fórmula de Cayley

¿Cuántos árboles distintos pueden construirse sobre un conjunto fijo de n vértices etiquetados? La respuesta es uno de los resultados más citables de la combinatoria, publicado por Arthur Cayley en 1889.

Fórmula de Cayley. El número de árboles etiquetados con n vértices es nn-2.

Los primeros valores crecen rápido, y vale la pena verlos porque los más pequeños pueden comprobarse a mano:

Los recuentos para n = 4 y n = 5 de arriba no se citan de un libro; se obtuvieron enumerando todos los subconjuntos de n - 1 aristas entre los C(n, 2) candidatos y quedándose con los conexos, lo que da exactamente 16 y 125.

Una palabra sobre qué significa «etiquetado», porque la distinción es todo el tema de la sección 9. Cayley cuenta árboles cuyos vértices son distinguibles, así que el camino 1 - 2 - 3 y el camino 2 - 1 - 3 son árboles distintos aunque tengan la misma forma. Quita las etiquetas y solo hay una forma de árbol con tres vértices.

Existen varias demostraciones de la fórmula, entre ellas un argumento de doble conteo sobre bosques con raíz y un argumento con determinantes mediante el teorema de la matriz-árbol. La más esclarecedora es una biyección, y es lo bastante breve como para desarrollarla por completo.

7. La biyección de Prüfer, paso a paso

Heinz Prüfer dio en 1918 una demostración de la fórmula de Cayley construyendo una biyección explícita entre los árboles etiquetados con n vértices y las sucesiones de longitud n - 2 con valores en {1, …, n}. Como hay exactamente nn-2 sucesiones así, la fórmula se sigue de inmediato.

Codificación. Mientras queden más de dos vértices, busca la hoja con la etiqueta más pequeña, anota la etiqueta de su único vecino y elimina la hoja. Detente cuando queden dos vértices. En el ejemplo recurrente esto produce, paso a paso:

quitar hoja 1  →  anotar 3      quedan: 2,3,4,5,6,7,8
quitar hoja 2  →  anotar 3      quedan: 3,4,5,6,7,8
quitar hoja 3  →  anotar 4      quedan: 4,5,6,7,8
quitar hoja 4  →  anotar 5      quedan: 5,6,7,8
quitar hoja 6  →  anotar 5      quedan: 5,7,8
quitar hoja 5  →  anotar 7      quedan: 7,8

sucesión de Prüfer:  (3, 3, 4, 5, 5, 7)        longitud 6 = n - 2

Decodificación. La inversa aplica la misma idea hacia atrás. Da a cada vértice un contador igual a uno más el número de veces que aparece en la sucesión, que será su grado. Después toma repetidamente el vértice más pequeño cuyo contador sea 1 y que aún no se haya usado, únelo a la primera entrada que quede de la sucesión y decrementa ambos contadores. Cuando se agote la sucesión, une los dos vértices que aún tengan contador 1. Aplicando esto a (3, 3, 4, 5, 5, 7) se recupera exactamente el conjunto de aristas original, que es lo que convierte la correspondencia en una biyección y no en un mero resumen.

La propiedad más útil de la codificación es esta:

El vértice v aparece en la sucesión de Prüfer exactamente deg(v) - 1 veces. En particular, las hojas son precisamente las etiquetas que nunca aparecen.

Compruébalo en el ejemplo recurrente. El vértice 3 tiene grado 3 y aparece dos veces; el vértice 5 tiene grado 3 y aparece dos veces; los vértices 4 y 7 tienen grado 2 y aparecen una vez cada uno; y las hojas 1, 2, 6 y 8 no aparecen en absoluto. Esa correspondencia convierte las preguntas sobre sucesiones de grados en preguntas sobre cuántas veces aparecen los símbolos en una cadena, y por eso las sucesiones de Prüfer son la herramienta estándar para contar árboles con grados prescritos y para muestrear un árbol etiquetado uniformemente al azar: genera una sucesión aleatoria de longitud n - 2 y decodifícala.

8. El teorema de la matriz-árbol

La fórmula de Cayley cuenta los árboles de expansión del grafo completo. El teorema de la matriz-árbol de Kirchhoff, que la precede en cuatro décadas y surgió de su trabajo sobre redes eléctricas en 1847, cuenta los árboles de expansión de cualquier grafo.

Construye la matriz laplaciana del grafo L = D - A, donde D es la matriz diagonal de los grados y A es la matriz de adyacencia. Entonces:

Teorema de la matriz-árbol. Elimina cualquier fila y la columna correspondiente de L. El determinante de la matriz (n-1) × (n-1) restante es el número de árboles de expansión del grafo. Da igual qué fila y qué columna elimines.

Tres cálculos hacen concreto el teorema, y los tres se realizaron en lugar de citarse:

El caso del ciclo es el que conviene retener como intuición: un ciclo con k vértices tiene exactamente k árboles de expansión, uno por cada arista que decidas quitar. El teorema explica también una observación de la guía sobre multigrafos: las aristas paralelas cambian de verdad el número de árboles de expansión, porque entran en el laplaciano como multiplicidades fuera de la diagonal, así que dos vértices unidos por dos aristas paralelas tienen dos árboles de expansión en lugar de uno.

9. Árboles no etiquetados: una pregunta mucho más difícil

La fórmula de Cayley es limpia porque las etiquetas hacen fácil distinguir los árboles. Pregunta en cambio cuántos árboles hay salvo isomorfismo, es decir, cuántas formas distintas existen, y el problema se vuelve genuinamente difícil.

Las dos columnas cuentan historias completamente distintas. El recuento etiquetado tiene una forma cerrada de una línea; el no etiquetado no tiene ninguna. No se conoce ninguna fórmula para el número de árboles con n vértices salvo isomorfismo, solo un tratamiento con funciones generatrices y un resultado asintótico de Richard Otter de 1948, que muestra que el recuento crece como C · αn n-5/2 para constantes calculadas numéricamente.

La razón de la diferencia es la simetría. Dividir el recuento etiquetado por n! solo sería correcto si todo árbol tuviera un grupo de automorfismos trivial, y la mayoría no lo tiene: un camino puede reflejarse, las hojas de una estrella pueden permutarse arbitrariamente, y cada simetría hace que varios etiquetados colapsen en la misma forma. Contar órbitas bajo el grupo simétrico es precisamente la parte difícil, y es la razón de que el problema necesite la maquinaria de enumeración de Pólya en lugar de una fórmula.

Para quien programa, la forma práctica de esta distinción es la prueba de isomorfismo de árboles: decidir si dos árboles tienen la misma forma. A diferencia del isomorfismo general de grafos, esto se resuelve en tiempo lineal, calculando un hash canónico de cada subárbol de abajo arriba desde las hojas y comparando los resultados en el centro. Que el problema general sea difícil mientras el caso de los árboles es fácil es un ejemplo más del patrón que recorre todo este artículo.

10. Centro, radio y diámetro

La excentricidad de un vértice es su mayor distancia a cualquier otro vértice. El radio es la menor excentricidad del grafo, el diámetro la mayor, y el centro es el conjunto de vértices que alcanzan el radio. En los árboles se comportan de forma inusualmente limpia, como estableció por primera vez Camille Jordan en 1869.

Teorema de Jordan. El centro de un árbol consta de un vértice o de dos vértices adyacentes.

Nunca tres, nunca dos no adyacentes. Compáralo con un ciclo, donde todos los vértices están en el centro, y queda clara la nitidez del caso de los árboles.

La demostración sirve a la vez de algoritmo. Elimina repetidamente todas las hojas actuales a la vez. Cada ronda reduce en exactamente 1 la excentricidad de cada vértice superviviente, así que conserva cuáles son mínimos, y el proceso termina con uno o dos vértices. En el ejemplo recurrente:

inicio                  1 2 3 4 5 6 7 8
quitar hojas 1, 2, 6, 8   →   quedan  3 4 5 7
quitar hojas 3, 7         →   quedan  4 5      ← el centro

excentricidades   1:5  2:5  3:4  4:3  5:3  6:4  7:4  8:5
radio 3     diámetro 5     centro {4, 5}, adyacentes como exige Jordan

El resultado de quitar hojas se contrastó con un cálculo directo de las ocho excentricidades, y ambos coinciden exactamente: los vértices de excentricidad mínima son precisamente 4 y 5. El algoritmo se ejecuta en O(n), y por eso es la forma estándar de enraizar un árbol «en el medio», por ejemplo antes del hash canónico en la prueba de isomorfismo.

Una identidad más se cumple en los árboles y vale la pena recordarla:

radio = ⌈diámetro / 2⌉        aquí: 3 = ⌈5 / 2⌉

Se sigue de que el diámetro de un árbol lo realiza un único camino, y el centro está en el punto medio de ese camino. En un grafo general solo se cumple la desigualdad más débil radius ≤ diameter ≤ 2 · radius .

11. Distancias en árboles y el truco del doble BFS

Como hay exactamente un camino entre dos vértices cualesquiera, la distancia en un árbol es más sencilla que en cualquier otra clase de grafos. No hay nada que optimizar: el único camino es el camino más corto, así que no hacen falta pesos, ni cola de prioridad, ni Dijkstra para encontrarlo.

Esa unicidad da un algoritmo elegante y muy usado para el diámetro:

Doble BFS. Ejecuta una búsqueda en anchura desde cualquier vértice y sea a un vértice más lejano encontrado. Ejecuta una segunda búsqueda desde a y sea b un vértice más lejano desde él. Entonces el camino de a a b es un diámetro, y dist(a, b) es la longitud del diámetro.

Dos pasadas lineales, sin pesos, sin ingenio. En el ejemplo recurrente, empezando en el vértice 1 la búsqueda alcanza el vértice 8 como vértice más lejano, y una segunda búsqueda desde 8 devuelve el vértice 1 a distancia 5, lo que coincide con el diámetro real calculado como el máximo de todas las excentricidades.

Vale la pena explicar por qué funciona, porque el truco falla en grafos generales y aun así la gente lo trasplanta. La afirmación clave es que un vértice más lejano desde cualquier punto de partida es siempre un extremo de algún diámetro. En un árbol esto se cumple porque los caminos únicos obligan al vértice más lejano a estar al final del camino más largo; en un grafo con ciclos la afirmación es simplemente falsa, y el método de dos pasadas puede devolver un valor por debajo del real. En un grafo general, calcular el diámetro requiere las distancias entre todos los pares.

Otros hechos sobre distancias que se cumplen en los árboles y, en general, en ningún otro sitio:

• Eliminar cualquier arista divide el árbol en exactamente dos componentes, ya que toda arista es un puente. Eso es lo que hace que el divide y vencerás sobre árboles, como la descomposición por centroides, funcione tan limpiamente.
• El camino entre dos vértices puede recuperarse solo con punteros al padre una vez que el árbol tiene raíz, en tiempo proporcional a la longitud del camino, lo que sustenta las técnicas de ancestro común más bajo.
• Las distancias cumplen la condición de los cuatro puntos, una identidad métrica que caracteriza exactamente las matrices de distancias que provienen de árboles, y que es la base de la reconstrucción de árboles filogenéticos a partir de datos de distancia genética.

12. Árboles libres, con raíz y ordenados

Todo lo anterior trataba de árboles libres: grafos conexos acíclicos sin vértice distinguido y sin orden entre los vecinos de ningún vértice. La informática casi siempre trabaja con algo más estructurado, y el libro de Knuth The Art of Computer Programming separa con cuidado los tres niveles, porque los recuentos difieren en cada uno.

Poner una raíz no cambia el grafo, cambia la pregunta. El conjunto de aristas subyacente es idéntico; lo que añade una raíz es una dirección, y con ella todo el vocabulario de padre, hijo, ancestro, descendiente, profundidad y altura, que la guía complementaria sobre árboles con raíz trata en detalle junto con los recorridos estándar.

La diferencia en los recuentos es la forma más clara de ver que son objetos realmente distintos. Los árboles binarios ordenados con n nodos se cuentan con los números de Catalan, que dan 1, 1, 2, 5, 14, 42 para n = 0 hasta 5, mientras que los árboles libres con el mismo número de vértices son muchos menos. Cada pieza adicional de estructura que exiges multiplica el número de objetos distintos.

Una nota práctica que se deduce de la sección 10: cuando un algoritmo necesita una raíz y no se da ninguna, poner la raíz en el centro suele ser la opción por defecto correcta. Minimiza la altura, que acota la profundidad de cualquier recursión que ejecutes sobre el árbol.

13. Dónde aparecen los árboles en informática

Los árboles son la estructura más común en informática que es realmente un grafo, y vale la pena separar los casos en que el árbol son los datos de aquellos en que es un certificado producido por un algoritmo.

Árboles como datos. La jerarquía es lo esencial:

• Sistemas de archivos. Los directorios y archivos forman un árbol con raíz, al menos hasta que se permiten enlaces simbólicos y duros, momento en el que se convierte en un grafo general y se pierde la garantía de un camino único. Justo por eso los bucles de enlaces rompen los recorridos ingenuos de directorios.
• Árboles de análisis y árboles de sintaxis abstracta. Todo front-end de compilador produce uno. Ser un árbol es lo que hace que la evaluación recursiva esté bien fundada: una subexpresión no puede contenerse a sí misma.
• El DOM. Un documento HTML es un árbol con raíz ordenado, y los selectores CSS son consultas sobre relaciones de ancestro y hermano dentro de él.
• Árboles de búsqueda, tries y montículos. Los árboles binarios de búsqueda, los árboles B y los tries son árboles cuya forma se restringe para acotar la profundidad, que es exactamente la altura del árbol con raíz.
• Árboles de decisión. Cada nodo interno comprueba una característica y cada hoja lleva una predicción; el único camino de la raíz a la hoja es la explicación de la salida del modelo.

Árboles como certificados. Aquí el árbol es la salida de un algoritmo y codifica una demostración:

• Árboles BFS y DFS. Todo recorrido de un grafo conexo produce un árbol de expansión de aristas de descubrimiento. El árbol BFS certifica además las distancias más cortas en un grafo sin pesos, y las aristas de retroceso del árbol DFS son las que permiten detectar ciclos y encontrar puentes.
• Árboles de caminos más cortos. El algoritmo de Dijkstra produce uno: un árbol de expansión en el que el camino desde el origen hasta cualquier vértice es un camino más corto. Ten en cuenta que en general no es un árbol de expansión mínima, y confundir ambos es un error clásico.
• Árboles de expansión mínima. Kruskal, Prim y Borůvka certifican cada uno el subgrafo de conexión más barato, tratado en la guía de MST.
• Bosques de union-find. La estructura de conjuntos disjuntos es literalmente un bosque, y la compresión de caminos es una operación que aplana sus árboles para mantener la altura casi constante.
• Árboles de Merkle. Los árboles de hash del control de versiones y de los sistemas distribuidos usan la propiedad del camino único para que el cambio de una sola hoja se propague por exactamente un camino hasta la raíz, lo que hace logarítmica la verificación.

Una aclaración que vale la pena hacer, porque la terminología confunde: un historial de commits de Git no es un árbol. Un commit de fusión tiene dos padres, así que el historial es un grafo acíclico dirigido. Los objetos «tree» de Git son algo completamente distinto, a saber, las instantáneas de directorios. La diferencia entre un DAG y un árbol es precisamente que un árbol tiene un único camino entre dos nodos cualesquiera, y una fusión destruye eso.

14. Errores comunes

• Comprobar solo la mitad de la definición. «Conexo» por sí solo admite ciclos; «n - 1 aristas» por sí solo admite un triángulo más un vértice aislado. Necesitas un par de condiciones del teorema de la sección 2, y conexo más n - 1 aristas es el más barato.
• Suponer que un árbol de caminos más cortos es un árbol de expansión mínima. Optimizan cosas distintas: uno minimiza cada distancia desde el origen, el otro minimiza el peso total de las aristas. Con frecuencia difieren.
• Usar el truco del doble BFS para el diámetro en un grafo con ciclos. Solo es válido en árboles, donde la propiedad del camino único hace que un vértice más lejano sea extremo de un diámetro. En grafos generales puede subestimar en silencio.
• Confundir los recuentos etiquetados y no etiquetados. Hay 125 árboles etiquetados con 5 vértices y solo 3 formas. Dividir por n! no convierte entre ellos, porque los árboles tienen simetrías.
• Olvidar que poner una raíz no cambia nada estructuralmente. Una raíz añade una pregunta, no una arista. El árbol libre subyacente no cambia, así que cualquier hecho estructural demostrado para árboles libres sigue siendo válido.
• Esperar el lema de las hojas en árboles infinitos. El camino infinito en ambos sentidos es acíclico y conexo, y no tiene ninguna hoja.
• Tratar un DAG como un árbol. Un DAG puede tener varios caminos entre dos nodos; un árbol no. Cualquier algoritmo que dependa de la unicidad de los caminos, incluida la memoización ingenua con un nodo como clave, se comportará mal.
• Construir un «árbol» que tiene un ciclo. La comprobación más rápida en tiempo de ejecución es el número de aristas: si un supuesto árbol con n vértices no tiene exactamente n - 1 aristas, detente y busca el error.

15. Glosario

17. Referencias

Fuentes de las definiciones, teoremas y atribuciones anteriores, junto con los textos estándar en los que se desarrolla este material, listadas en orden cronológico.

1. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 a 508. El teorema de la matriz-árbol.
2. Jordan, C. (1869). "Sur les assemblages de lignes." Journal für die reine und angewandte Mathematik 70, 185 a 190. El centro de un árbol es un vértice o dos vértices adyacentes.
3. Cayley, A. (1889). "A Theorem on Trees." Quarterly Journal of Pure and Applied Mathematics 23, 376 a 378.
4. Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen." Archiv der Mathematik und Physik 27, 142 a 144. La biyección de la sección 7.
5. Borůvka, O. (1926). "O jistém problému minimálním." Práce Moravské Přírodovědecké Společnosti 3, 37 a 58.
6. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft.
7. Otter, R. (1948). "The Number of Trees." Annals of Mathematics 49(3), 583 a 599. Asintótica de los árboles no etiquetados.
8. Kruskal, J. B. (1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1), 48 a 50.
9. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6), 1389 a 1401.
10. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley.
11. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3.ª edición, sección 2.3. Reading, Massachusetts: Addison-Wesley. La distinción entre árboles libres, con raíz y ordenados.
12. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River: Prentice Hall. El capítulo 2 desarrolla los árboles y las distancias.
13. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Cambridge, Massachusetts: MIT Press.
15. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer. La sección 1.5 trata árboles y bosques.