_
_
_
_

Árboles de Steiner

El matemático suizo dio nombre a los grafos arbóreos de longitud mínima

Carlo Frabetti
Jakob Steiner
Jakob 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.

Tu suscripción se está usando en otro dispositivo

¿Quieres añadir otro usuario a tu suscripción?

Si continúas leyendo en este dispositivo, no se podrá leer en el otro.

¿Por qué estás viendo esto?

Flecha

Tu suscripción se está usando en otro dispositivo y solo puedes acceder a EL PAÍS desde un dispositivo a la vez.

Si quieres compartir tu cuenta, cambia tu suscripción a la modalidad Premium, así podrás añadir otro usuario. Cada uno accederá con su propia cuenta de email, lo que os permitirá personalizar vuestra experiencia en EL PAÍS.

En el caso de no saber quién está usando tu cuenta, te recomendamos cambiar tu contraseña aquí.

Si decides continuar compartiendo tu cuenta, este mensaje se mostrará en tu dispositivo y en el de la otra persona que está usando tu cuenta de forma indefinida, afectando a tu experiencia de lectura. Puedes consultar aquí los términos y condiciones de la suscripción digital.

Sobre la firma

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’.

Más información

Archivado En

Recomendaciones EL PAÍS
Recomendaciones EL PAÍS
Recomendaciones EL PAÍS
_
_