Árboles

Teoría

En teoría de gráficas, un árbol es una gráfica conexa que no tiene ciclos. Los árboles sirven como el "esqueleto" fundamental de gráficas más complejas; toda gráfica conexa tiene un árbol de expansión, que conecta todos los vértices usando el número mínimo posible de aristas. Como no tienen ciclos, los árboles representan la forma más simple de conectividad. Si quitas cualquier arista de un árbol, la gráfica se desconecta; por el contrario, si agregas cualquier arista entre dos vértices que ya existen en un árbol, vas a crear un ciclo inevitablemente.

La propiedad estructural más importante de un árbol es que existe un camino único entre cualesquiera dos vértices. Esta propiedad la puedes usar seguido en problemas de combinatoria que involucran distancia, flujo o diseño de redes. Como hay exactamente una forma de ir del punto $A$ al punto $B$ sin regresar sobre tus pasos, los árboles permiten un análisis más simple comparado con gráficas generales donde podrían existir varios caminos.

En matemáticas de competencia como el AMC 12 y el AIME, los árboles aparecen seguido en problemas de conteo (enumerar árboles etiquetados) o como la estructura base en problemas sobre sumas de grados y conectividad. Entender la relación entre el número de vértices, aristas y hojas (vértices de grado 1) es esencial. Los árboles también son gráficas bipartitas, lo que significa que puedes dividir sus vértices en dos conjuntos ajenos.