El sudoku arborícola

Piste verte Le 7 juillet 2019  - Ecrit par  Shalom Eliahou
Le 6 octobre 2019  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Le sudoku arboricole Voir les commentaires
Lire l'article en  

¿Son gráciles las langostas, las arañas y otros árboles matemáticos ? Según una conjetura semi-centenaria, debería ser el caso...

El objeto central de este artículo son los árboles matemáticos. Sin más espera, aquí hay un ejemplo típico :

Una definición precisa será dada más adelante. Pero primero, describamos informalmente el problema abordado aquí sobre estos árboles : se trata de enumerar los vértices (los grandes puntos) y las aristas (los segmentos) respetando algunas condiciones, como las del sudoku. La enumeración se dice que es grácil cuando dichas condiciones están satisfechas.

El sudoku

Antes de presentar su versión arborícola, recordemos brevemente lo que es el sudoku clásico. Se parte de una grilla cuadrada 9 x 9 parcialmente rellena con números entre 1 y 9. El objetivo del rompecabezas es completar la grilla respetando las condiciones siguientes :

  • cada casilla debe contener un número entre 1 y 9 ;
  • ninguna hilera -línea o columna- debe contener una repetición ;
  • ninguna de las nuevas sub-grillas 3 x 3 delimitadas en negrita sobre la figura debe contener una repetición.

Como se verá, la versión arborícola es también fácil de comprender. Y de nuevo, una de las condiciones principales será la no repetición de números. Una pequeña dificultad : esta versión es objeto de una conjetura abierta ¡desde hace medio siglo más o menos !

Mini diccionario de teoría de grafos

Una dosis —homeopática— de vocabulario técnico nos será útil para comenzar bien nuestro paseo campestre. Un grafo es una colección finita [1] de puntos y de pares de puntos. Los puntos son llamados vértices y los pares de puntos son llamados aristas. Se visualiza una arista por un segmento de recta o de curva que une sus dos vértices. Aquí hay un ejemplo de grafo :

Dos vértices unidos por una arista se dice que son vecinos. El grado de un vértice es el número de sus vecinos. En el ejemplo del frente, el vértice rojo es de grado 6.

Se dice que un grafo es conexo si, informalmente, está en un solo segmento ; más formalmente, si uno puede ir de un vértice a cualquier otro vértice avanzando a lo largo de las aristas. Es justo el caso del ejemplo presente.

Un ciclo es un camino cerrado, es decir, un grafo conexo cuyos vértices son todos grado 2. El sub-grafo marcado en azul en el ejemplo es un ciclo de longitud 4.

En este artículo, se considera solo los grafos dichos simples : ningún vértice es su propio vecino, y ningún par de vértices está ligado por más de una arista.

Los grafos son objetos matemáticos extremadamente útiles, tanto en lo teórico como en las aplicaciones. Son indispensables en numerosos campos como la informática, la química o la modelización del tráfico. Vea por ejemplo este artículo en ese sitio.

Vayamos ahora a los árboles, grafos muy particulares y fácilmente reconocibles.

Árboles

Un árbol es un grafo conexo y sin ciclos. ¡Esta es toda la definición formal de esos objetos matemáticos !

Los vértices extremos de un árbol son llamados sus hojas. Son por lo tanto sus vértices de grado 1, aquellos de color verde en nuestro ejemplo favorito :

Notemos que si un árbol contiene al menos tres vértices, entonces cada hoja está contenida en una única arista, que llamaremos entonces su ramita.

Los árboles gozan de una propiedad hereditaria muy útil, que es la afirmación siguiente.

Propiedad hereditaria Si, en un árbol, se suprime una hoja y su ramita, entonces el grafo resultante sigue siendo un árbol.

Eso se explica fácilmente : el grafo truncado de esta manera queda en un solo pedazo, es decir, sigue conexo, y queda evidentemente sin ciclo. Basta con dibujar un pequeño ejemplo para convencerse.

Aquí hay una primera consecuencia muy interesante. Procediendo al revés, uno puede construir cualquier árbol partiendo de un vértice inicial, y repitiendo después la operación siguiente : unir una nueva hoja a un vértice ya presente con una nueva ramita . Como en la sucesión de abajo :

Esta propiedad es muy útil si uno quiere hacer demostraciones por recurrencia con respecto a los árboles. Un lindo ejemplo es la prueba —facultativa, pero que vale la pena igual darle una mirada— de esta otra propiedad ineludible de los árboles.

Propiedad Si un árbol tiene $n$ aristas, entonces tiene $n+1$ vértices.

Demostración

La afirmación es verdad para $n=1$ : un árbol con una sola arista posee dos vértices.

Para el caso general con $n \ge 2$, se procede por inducción, un método de demostración muy potente. Grosso modo, este método dice que si uno quiere llegar al $n$-ésimo peldaño de una escalera, basta con llegar a su $(n-1)$-ésimo peldaño y subir uno más.

En el presente caso, se supone el resultado ya demostrado para los árboles con $n-1$ aristas y, partiendo de ahí, uno trata de demostrarlo para los árboles con $n$ aristas.

Tomemos ahora un árbol con $n$ aristas, y suprimamos una de sus hojas con su ramita. Dada la propiedad hereditaria de arriba, uno encuentra un árbol con $n-1$ aristas. Ahora bien, gracias a la hipótesis de inducción, uno sabe que este posee $(n-1)+1$ vértices, es decir, $n$ vértices.

Contando la hoja suprimida, se encuentra que el árbol del inicio posee $n+1$ vértices en total. $\Box$

Para diversos nexos entre grafos, árboles y literatura, vea en este sitio este artículo hermosamente ilustrado.

Enumeraciones gráciles

Armados de estos conocimientos sobre los árboles, podemos ahora abordar nuestro rompecabezas con reglas simples, pero sin embargo aún mal comprendidas. Démonos un árbol $A$ con $n$ aristas, y por lo tanto con $n+1$ vértices. Una enumeración grácil de $A$ es lo siguiente :

  • una enumeración de sus aristas de 1 a $n$, sin repetición ;
  • una enumeración de sus vértices de 0 a $n$, sin repetición ;
  • una regla de compatibilidad entre esas dos enumeraciones : el número de cada arista debe ser igual al valor absoluto de la diferencia entre los números de sus dos vértices.

Esta tercera condición está resumida por el dibujo siguiente, donde se ha supuesto que $b$ es más grande que $a$ :

Notemos que, tan pronto como los vértices son enumerados, la regla de compatibilidad provee automáticamente una enumeración de las aristas : basta con asignar a cada una la diferencia positiva de los números de sus extremos, como abajo. Pero falta aún asegurarse respecto a la restricción de no repetición para que esta enumeración pueda pretender el título de grácil.

Aquí hay un ejemplo de árbol con 9 aristas grácilmente enumeradas. Las aristas están enumeradas en azul de 1 a 9, los vértices en rojo de 0 a 9, sin repetición en los dos casos ; y finalmente, la regla de compatibilidad está bien satisfecha : cada número de arista azul es igual al valor absoluto de la diferencia entre los números rojos de sus extremos.

El sudoku arborícola

La semejanza entre las enumeraciones gráciles de un árbol y el sudoku es la siguiente : se trata de asignar números tomados de un conjunto preciso, respetando las reglas de no repetición. De ahí el término sudoku arborícola.

Ustedes pueden jugar de aquí en adelante, sin tener que esperar a que su diario preferido lo publique : dibujen un árbol, de preferencia pequeño al principio, y traten de enumerarlo grácilmente ; o inviten a alguien de su entorno al desafío de hacerlo.

Cual sea el árbol elegido, ¿el sudoku sobre él admite necesariamente una solución ? Es ahí cuando las cosas se complican : ¡no se sabe ! Pero se conjetura que siempre ocurre.

La conjetura

Reformulemos esto utilizando la terminología oficial : se dice que un árbol es grácil si admite al menos una enumeración grácil.

Conjetura. Todo árbol matemático es grácil.

En la literatura científica, este problema es conocido como la conjetura de los árboles gráciles, entre otras [2]. Fue formulada por Alex Rosa en 1967 como un enfoque posible de una conjetura anterior de Ringel y Kotzig, que databa de 1963, sobre la el análisis de grafos completos [3] como combinación de copias de un árbol dado.

Dejando de lado algunos resultados parciales evocados arriba, no se sabe cómo demostrar esta conjetura en general. Incluso los árboles de apariencia bastante anodina, como las langostas y las arañas [4] presentadas más lejos, son un gran problema para los investigadores. ¿Son gráciles ? ¡Uno desearía mucho poder afirmarlo ! [5]

¿Unicidad ?

Dos palabras de gran importancia en matemáticas son existencia y unicidad. Cuando uno dispone de un sistema de restricciones matemáticas, cualquiera que sea, uno se pregunta siempre si las soluciones existen y, si existen, si acaso estas son únicas, generalmente sin contar las posibles simetrías.

De este modo, la conjetura de arriba concierne a la existencia de enumeraciones gráciles para todo árbol. ¿Pero qué pasa con la unicidad ?

Desde ya, el conjunto de enumeraciones gráciles de un árbol con $n$ aristas está dotado de una cierta simetría : si uno reemplaza, para cada vértice, su número $a$ por el número complementario $n-a$, y deja los números de las aristas sin cambiar, entonces la nueva enumeración sigue siendo grácil. Eso se deriva de la simple fórmula

\[ (n-a) - (n-b) \, = \, b-a. \]

Por lo tanto, todo árbol grácil que tenga más de una arista admite al menos dos enumeraciones gráciles. Pequeña ilustración de esta simetría :

Bueno, pero...¿y qué pasa con la unicidad sin contar las simetrías ? Eso depende del árbol, pero en general sus enumeraciones gráciles parecen por el contrario ser muy abundantes, como el caso de los caminos de más abajo. ¡Es aún más chocante siendo que uno no sabe demostrar que existe siempre al menos una !

Breve estado de los conocimientos

Este es el estatus —abierto o resuelto— de la conjetura para ciertas familias de árboles. Los términos consagrados para nombrar algunas de ellas son bastante graciosos, como se ha podido intuir desde el inicio de este artículo.


Los caminos. Estos árboles muy especiales, que uno puede caracterizar como aquellos que tienen exactamente dos hojas, están bien descritos por su propio nombre :

Es fácil enumerar grácilmente un camino de longitud $n$ dada. Partiendo de un extremo, uno enumera todas las aristas sucesivamente de $1$ a $n$, después enumera los vértices partiendo de la arista número $n$ y respetando la regla de compatibilidad :

Pero aquí hay otra enumeración grácil del mismo camino :

De hecho, cuando $n$ crece, la cantidad de enumeraciones gráciles del camino con $n$ aristas ¡crece de manera exponencial ! (a tal punto que uno no sabe describirlas todas).


Las orugas. Una oruga es un árbol obtenido partiendo de un camino y añadiéndole algunas ramitas a sus vértices :

Aún más, una receta simple —similar a la de los caminos— permite enumerar grácilmente las orugas. Uno la adivina en este ejemplo, observando cómo las aristas están enumeradas en orden :

Las orugas son muy útiles en teoría de grafos aplicada a la química, en particular para representar las moléculas de hidrocarbono benzenoide (gracias Wikipedia).


Las langostas. Una langosta se obtiene partiendo de una oruga y añadiéndole algunas ramitas suplementarias a sus vértices :

Catástrofe : ¡ya traspasamos las fronteras de lo conocido ! No se conoce ningún método sistemático para enumerar grácilmente una langosta, o de demostrar de manera abstracta que se puede hacer.

En resumen, se sabe que todos los caminos y que todas las orugas son gráciles. Pero se ignora si todos las langostas lo son.


Las arañas. He aquí un ejemplo típico de araña matemática, es decir, de un árbol con un vértice central desde donde parten varios caminos (sus patas) :

Uno sabe enumerar grácilmente las arañas con tres o cuatro patas. Pero para aquellas que tienen cinco o más ¡ya no se sabe en general !


Las estrellas. Las estrellas son un caso particular de araña, donde todas las patas son de longitud 1 :

Estos árboles son los más fáciles de enumerar grácilmente. ¿Sabrían ustedes hacerlo ? Sin la menor duda. ¡No vean la solución —única si no consideramos las simetrías— antes de haber tratado, incluso antes de haber acertado !

Solución

Basta con asignar 0 al vértice central, luego los números siguientes a las hojas y a sus ramitas respectivas ¡y eso es todo !


Otras familias. Para cerrar este breve sobrevuelo a los conocimientos, aquí está el estatus de la conjetura para algunas otras familias de árboles :

  • Los árboles con 4 hojas o menos son gráciles. A partir de 5 hojas, ya no se sabe en general.
  • Los árboles de diámetro 5 o menos son gráciles. El diámetro de un árbol es por definición la mayor longitud de un camino contenido en ese árbol. Por ejemplo, las estrellas son de diámetro 2.
  • Los árboles con 34 aristas o menos son gráciles, como ha sido verificado por computador.

¿Qué estrategia ?

¿Cómo progresar hacia una solución del problema ? Es muy difícil responder así nada más. Varias estrategias se ofrecen a los investigadores.

Un enfoque posible, ya vastamente practicado, consiste en concentrarse sobre las familias específicas de árboles tratando de resolver el problema para estas. Por ejemplo, se ignora si las langostas son gráciles. ¿Es una buena idea focalizarse en ellos, incluso en el caso aún más específico de aquellos obtenidos a partir de una oruga agregando solo una ramita, por ejemplo ?

Las matemáticas pueden tener sus desarrollos imprevistos. Así, uno podría creer que concentrar sus investigaciones en una clase restringida de objetos, como se sugiere aquí arriba, simplifica necesariamente las cosas. Ahora bien, este no es siempre el caso. Sucede que por el contrario, lo complica ; porque al restringirse demasiado, uno se arriesga a privarse de la posibilidad de usar métodos más generales y más abstractos y, por ende, más potentes.

Un enfoque alternativo, entre otros posibles, sería ensayar contando los árboles de $n$ aristas con enumeración grácil, y luego esperar a comprobar que uno encuentre el mismo número de árboles con $n$ aristas. Uno sabe contar los árboles suficientemente bien ; por ejemplo, hay exactamente 2.023.443.032 árboles de 27 aristas verdaderamente distintas [6]. Dicho eso, esta vía no se parece ser muy fácil...

Finalmente, uno no está nunca libre de una sorpresa : ¡podría ser que la conjetura sea falsa ! Es decir, podría existir, en alguna parte del paisaje matemático, un árbol perfectamente ’’sin gracia’’. Si ese fuese el caso, ¿cuántas aristas tendría ? ¿Cuarenta ? ¿Un millón de millares ? Cómo hacer, llegado el caso, para encontrarlo, construirlo, ¿o no sería que solo se puede probar abstractamente su existencia ?

Solo el futuro, forjado por las investigaciones de todos aquellas y aquellos que trabajarán en este tema —¿también lectoras y lectores de este artículo, quién sabe ?— nos dirá cuál enfoque habrá finalmente permitido superar este problema muy enigmático.

Un pequeño desafío

Para concluir con una nota lúdica, he aquí un árbol con 9 aristas que hay que enumerar grácilmente. Ustedes lo habrán reconocido : se trata de una langosta obtenida a partir de una oruga al agregar una sola ramita suplementaria. En la pestaña de la izquierda, dos vértices ya están enumerados, y como para el sudoku clásico, hay solo una posible forma de completarlo con una enumeración grácil (excepto permutación de los números de tres ramitas de la derecha). A modo de ayuda, en la pestaña de la derecha, tres vértices suplementarios están enumerados. No hacer click abajo a menos de quedarse sin ideas, ¡o haber encontrado la solución !

Podría ser que ocasionalmente nuevos desafíos sean propuestos aquí mismo. ¡Buena búsqueda !

Post-scriptum :

El autor agradece grácilmente a Roland Bacher y Bruno Martin, así como a las relectoras y relectores de seudónimos Thierry Viéville, Jean-Romain y P.Levallois, por su atenta lectura y sus muy constructivos comentarios .

Article original édité par Shalom Eliahou

Notes

[1La finitud es una convención muy frecuente, incluso si versiones infinitas son también interesantes y estudiadas.

[2Una noción análoga de enumeración grácil tiene de hecho un sentido para todos los grafos. Pero en ese contexto más general, se conoce numerosos casos no gráciles.

[3Es decir, cuyos vértices son todos vecinos unos de otros.

[4¡No es mi culpa ! : en teoría de grafos las langostas y las arañas —así como los caminos, las estrellas y las orugas— ¡son árboles !

[5La primera persona en el mundo que sea capaz de afirmarlo, con apoyo de pruebas y a pesar de la incredulidad pública, tiene la fama asegurada :-)

[6Se diría ’’no isomorfas’’, en lenguaje técnico.

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «El sudoku arborícola» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - Un árbol en Buenos Aires, el 5 de agosto de 2013.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?