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