Árboles de Steiner

Como vimos la semana pasada, con dos puntos solo se puede formar un árbol elemental de un solo lado, y con tres puntos también es única la solución, mientras que con cuatro puntos hay dos posibilidades. Con cinco puntos hay tres posibilidades distintas, y seis con seis puntos, y con siete puntos se pueden formar once árboles diferentes, lo que da lugar a la secuencia: 1, 1, 2, 3, 6, 11…

¿Cuáles son los números siguientes? ¿Hay una fórmula que nos dé el enésimo término en función de n? ¿En qué se parece y en qué se diferencia esta secuencia “arbórea” de la famosa y omnipresente sucesión de Fibonacci?

En la naturaleza abundan los ejemplos de estructuras arborescentes, como las redes hidrográficas, en las que los nodos serían las fuentes de las distintas corrientes de agua y los puntos de confluencia de dos o más de ellas. Obviamente, en la naturaleza los nodos no son puntos; pero la red se puede esquematizar en forma de grafo arbóreo. Y lo mismo se puede decir de nuestro sistema circulatorio y nuestro sistema nervioso. O de las redes eléctricas e hidráulicas que abastecen nuestras ciudades.

En todo árbol de n nodos hay n-1 aristas. Es fácil verlo si imaginamos los árboles formados por n-1 nodos “con rabo” (que podemos visualizar como cerillas, e incluso usarlas para componer árboles sobre una mesa) y uno sin.

Dentro de los grafos arbóreos tienen especial relevancia los árboles binarios, que son aquellos en los que cada rama se bifurca en otras dos. Un ejemplo ilustre lo encontramos en el Árbol de Porfirio, mencionado la semana pasada: es un árbol filosófico que va de lo general a lo particular y en el que cada concepto se subdivide en dos. Así, el ser puede ser (valga la redundancia) corpóreo o incorpóreo; lo corpóreo puede ser animado o inanimado; lo animado puede ser sensible o insensible…

Árboles mínimos

Dado un conjunto de elementos, puede tener especial interés la forma de conectarlos en árbol de forma óptima, en el sentido de conseguir la interconexión global más corta, es decir, aquella en la que la suma de todos los lados es mínima; y esa interconexión de longitud mínima es un árbol de Steiner, denominado así en honor del matemático suizo Jakob Steiner, uno de los más grandes geómetras del siglo XIX. Con la particularidad de que para lograr un árbol mínimo se pueden añadir al conjunto inicial algunos puntos -llamados puntos de Steiner- que den lugar a aristas más cortas.

Un ejemplo sencillo es el de los vértices de un triángulo equilátero, A, B y C. Una forma evidente de conectarlos es trazar dos de los lados, por ejemplo, AB y BC. Pero si tomamos como punto de Steiner el centro del triángulo ABC, S, y lo unimos con los tres puntos iniciales, obtenemos un árbol de longitud menor que la suma de dos lados. ¿Cuál es la longitud global de este árbol? ¿Es mínima? ¿Cómo sería el árbol de Steiner de los vértices de un triángulo no equilátero? ¿Y el de los vértices de un cuadrado?

Carlo Frabetti es escritor y matemático, miembro de la Academia de Ciencias de Nueva York. Ha publicado más de 50 obras de divulgación científica para adultos, niños y jóvenes, entre ellos Maldita física, Malditas matemáticas o El gran juego. Fue guionista de La bola de cristal.