Árboles

Sería lógico preguntarse por qué habría un artículo sobre árboles en la sección del blog dedicada a las matemáticas. Tal vez estéis pensando que pintaría más en la sección de biología, pero no os preocupéis, todo tiene un porqué. Y es que árbol es una palabra polisémica (tiene más de una acepción o significado): puede hacer referencia al ser vivo perteneciente al reino vegetal o a un tipo especial de grafo.

En la entrada anterior vimos una serie de conceptos básicos, además de que hay varios tipos de grafos según sus características. Hoy nos centraremos en los árboles.

¿Qué es un árbol? Definición

Como ya he mencionado al principio, un árbol es un tipo de grafo. En específico, se trata de un grafo conexo y que no tiene ciclos. Un momento…¿qué significa que un grafo es “conexo”?

Decimos que un grafo es conexo siempre y cuando podamos asegurar que se pueda llegar a todos los nodos del grafo desde cualquier otro a través de un camino. Si este no fuera el caso, se diría que el grafo no es conexo. Un grafo no conexo puede constar de varias componentes conexas, o ser un grafo trivial, si está compuesto sólo por nodos aislados.

Ejemplos de un grafo conexo, un grafo trivial y un grafo no conexo con dos componentes conexas respectivamente.

Retomando la definición de árbol, también hemos dicho que para ser considerado como tal debe carecer de ciclos. Aunque ya mencionamos lo que eran los ciclos en la entrada anterior, hagamos un repaso: un ciclo es un camino que empieza y acaba en el mismo vértice. Por lo tanto, dentro de un árbol todos los nodos estarán conectados y no habrá caminos cerrados.

¿Por qué son especiales los árboles?

Pues bien, si los grafos en general tienen de por sí montones de aplicaciones, los árboles son los reyes en este aspecto. Seguramente habréis oído hablar de los diagramas de árbol, pues se usan en estadística y probabilidad. Sin embargo, se utilizan en infinidad de problemas. A modo de curiosidad, un árbol genealógico se llama así porque el diagrama se trata precisamente de un árbol (a no ser que se trate de una familia endogámica, pues en ese caso habría ciclos en el grafo).

Ejemplo de utilidad: los problemas de decisiones y de genética pueden estudiarse con diagramas de árbol.

Bosques

Siguiendo un poco con la alegoría, existe un tipo de grafo denominado ‘bosque’, que está compuesto por varios árboles. Entonces, un bosque es un grafo inconexo sin ciclos (donde las componentes conexas son árboles).

Fuentes de información recomendadas

Como siempre, os voy dejando algún vídeo y enlaces de interés para aprender sobre Teoría de Grafos. Esta vez os propongo unos vídeos explicativos sobre árboles y un enlace de la página Monografías, junto a un episodio muy interesante del podcast Raíz de 5.

<iframe frameborder=’0′ allowfullscreen=” scrolling=’no’ height=’200′ style=’width:100%;’ src=’https://www.ivoox.com/player_ej_22935092_6_1.html?c1=953138′ loading=’lazy’></iframe>

¡Gracias por leer! Espero que os haya gustado y servido de ayuda, no sin incentivar vuestra curiosidad.