Árbol (Teoría de Grafos)
Un árbol es un grafo conexo sin ciclos, donde cualesquiera dos vértices están conectados por exactamente un camino.
Formula
|E| = |V| - 1
Definition
Un árbol es un grafo conexo sin lazos ni ciclos; como un árbol real o un árbol genealógico, se ramifica desde una raíz sin rutas circulares de regreso al punto de partida. Un árbol con $n$ vértices tiene exactamente $n-1$ aristas, es conexo, y no tiene ciclos, tres propiedades equivalentes donde cualesquiera dos implican la tercera; un árbol generador de un grafo conexo es un subgrafo que incluye todos los vértices y es un árbol. Caracterizaciones equivalentes de un árbol $T = (V,E)$: conexo con $|E|=|V|-1$; acíclico con $|E|=|V|-1$; o cualesquiera dos vértices conectados por un único camino; los números de Catalan cuentan los árboles binarios completos con $n+1$ hojas.
Example
Un árbol genealógico es un grafo donde cada persona es un vértice y las relaciones padre-hijo son aristas, sin ciclos porque no puedes ser tu propio ancestro. Los algoritmos de Kruskal y Prim encuentran el árbol generador mínimo (MST) de un grafo ponderado, el árbol generador con peso total de arista mínimo, usado en el diseño de redes para minimizar la longitud de cable. La fórmula de Cayley establece que el número de árboles generadores de $K_n$ (el grafo completo en $n$ vértices) es $n^{n-2}$; las secuencias de Prufer demuestran esto mediante una biyección entre árboles etiquetados y secuencias de longitud $n-2$.
Key Insight
Los árboles son los grafos conexos más simples, apareciendo en todas partes: sistemas de archivos, organigramas, árboles de análisis en compiladores, y árboles de decisión en el aprendizaje automático. En estructuras de datos, los árboles de búsqueda binarios balanceados (AVL, rojo-negro) mantienen una altura logarítmica, garantizando un tiempo de búsqueda O(log n), la razón por la cual la búsqueda binaria es eficiente.